Saratov State University :: Online Contester


::Go
- home
- news
- register
- update personal info
- problemset archive
- submit
- status online
- standing
- contests
- virtual contests
- forum
- statistic
- FAQ
- links
- projects

::Poll
Are you registered on Codeforces?
Yes
No
What is it???

[results]

::webboard

103 - Traffice Light : WA on test case 12
Author: AmirAz
ID: 063360
Problem: 103
Contest: 0
Date: 2015-01-25 20:39:14

I've written a code using Dijkstra's Algorithm for problem 103. But, it gets WA on test case 12. Here is a brief information about my code :

get_color(cur, u); returns the color of vertex u at time cur
next_change(cur, u); returns the time before the next change in color of vertex u
next_same(cur, u, v); returns the time before the next momment u and v get the same color
relax(u, v, l); is also known as update() in Dijkstra's Algorithm

Here is my code :

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;

#define ull unsigned long long
#define ll long long
#define INF 10000000000LL
#define pii pair<ll, ll>

vector < vector < pii > > G;
vector < ll > r, tp, tb, c, par;
vector < ll > dis;
ll dep, des, n, m;

priority_queue<pii, vector<pii>, greater<pii> > q;

ll get_color(ll cur, ll u){
ll col = c[u];
if (cur - r[u] < 0)
return col;
else if (cur - r[u] == 0)
return 1 - col;

cur -= r[u]; if (r[u]) col = 1 - col;
cur %= (tb[u] + tp[u]);

if (cur == 0)
return 1-col;

if (col == 0){
if (cur >= tb[u]) {cur -= tb[u]; col = 1 - col;}
return col;
}else{
if (cur >= tp[u]) {cur -= tp[u]; col = 1 - col;}
return col;
}
}

ll next_change (ll cur, ll u){
cur++;
if (cur <= r[u]) return r[u] - cur + 1;

cur -= r[u];
ll col = 1-c[u];
cur %= (tp[u] + tb[u]);

if (col == 0)
if (cur >= tb[u])
return tp[u] - (cur - tb[u]) + 1;
else
return tb[u] + 1 - cur;

if (col == 1)
if (cur >= tp[u])
return tb[u] - (cur -tp[u]) + 1;
else
return tp[u] + 1 - cur;


}

ll next_same(ll cur, ll u, ll v){
ll colu = get_color(cur, u);
ll colv = get_color(cur, v);

if (colu == colv) return 0;

ll step = 0, ans = 0, delta, nextu, nextv;
while (colu != colv && step < 10){

nextu = next_change(cur, u);
nextv = next_change(cur, v);
delta = min(nextu, nextv);

ans += delta;
cur += delta;

if (nextu != nextv)
return ans;
step++;
}
return INF;
}

void relax(ll u, ll v, ll l){

//cout << v << " was called from " << u << " : " << dis[u] << " + " << l << " ? " << dis[v]<< endl;
if (l >= INF) return;
if (dis[u] + l < dis[v]){
dis[v] = dis[u] + l;
par[v] = u;
q.push(pii(dis[v], v));
//cout << "t" << v << " was relaxed at " << dis[v] << endl;
}
}

void write(ll u){
if (u != dep)
write(par[u]);
cout << u+1 << " ";
}

int main(){
cin >> dep >> des >> n >> m; dep--; des--;

par = r = tp = tb = c = vector<ll>(n, INF);
dis = vector<ll>(n, INF);
G = vector< vector < pii > > (n);

char ch;
for (ll i = 0; i < n; i++){
cin >> ch >> r[i] >> tb[i] >> tp[i];
if (ch == 'B') c[i] = 0; else c[i] = 1;
}

ll u, v, l;

for (ll i = 0; i < m; i++){
cin >> u >> v >> l; u--; v--;
G[u].push_back(pii(v, l));
G[v].push_back(pii(u, l));
}

// cout << next_change(38, 3);
// cout << next_same(0, 0, 1);
// return 0;
dis[dep] = 0;
q.push(pii(dis[dep], dep));

ll ex;
while (q.size()){
u = q.top().second; ex = q.top().first; q.pop();
//if (ex > dis[u]) continue;
//cout << u << " began :n" ;
for (ll i = 0; i < G[u].size(); i++){
v = G[u][i].first; l = G[u][i].second;
// cout << "for " << u << " to "<< v << " : " << l << " + " << next_same(dis[u],u,v)<<endl;
relax(u, v, l + next_same(dis[u], u, v));
}
//cout << u << " endedn";
}

if (par[des] >= n || dis[des] >= INF)
cout << 0;
else{
cout << dis[des] << endl;
write(des);
}
}


see sub-tree reply to that message


::Login
Forgot password?

::News
22.10.12 - The problems from the Southern Subregional Programming Contest 2012 added to the problemset archive (542 - 553).
22.10.12 - After the start of the contest the statements in PDF will be available by the link.
23.10.11 - The problems from the Southern Subregional Programming Contest 2011 added to the problemset archive (530 - 541).

::Counter

Server time: 2017-11-21 07:11:29Online Contester Team © 2002 - 2016. All rights reserved.