# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
411500 | 2021-05-25T12:34:31 Z | Ruxandra985 | Graph (BOI20_graph) | C++14 | 2 ms | 2636 KB |
#include <bits/stdc++.h> #define DIMN 100010 using namespace std; double sol[DIMN]; int f[DIMN]; vector <pair <int , int> > v[DIMN]; pair <int , int> cod[DIMN]; deque <int> dq; int main() { FILE *fin = stdin; FILE *fout = stdout; int n , m , i , a , y , z , found , nod , vecin , tip; double x; fscanf (fin,"%d%d",&n,&m); for (i = 1 ; i <= m ; i++){ fscanf (fin,"%d%d%d",&a,&y,&z); v[a].push_back(make_pair(y , z)); v[y].push_back(make_pair(a , z)); } cod[1] = make_pair(0 , 1); dq.push_back(1); f[1] = 1; found = 0; while (!dq.empty() && !found){ nod = dq.front(); dq.pop_front(); for (i = 0 ; i < v[nod].size() ; i++){ vecin = v[nod][i].first; tip = v[nod][i].second; if (!f[vecin]){ dq.push_back(vecin); f[vecin] = 1; cod[vecin] = make_pair(tip - cod[nod].first , -cod[nod].second); } else { /// momentul sa vezi daca relatiile sunt echivalente, contradictorii /// sau daca sau solutia x if (cod[vecin] == make_pair(tip - cod[nod].first , -cod[nod].second)) continue; /// echivalent if (cod[vecin].second == -cod[nod].second && cod[vecin].first != tip - cod[nod].first){ fprintf (fout,"NO"); /// contradictorii return 0; } if (cod[vecin].second != -cod[nod].second){ if (cod[vecin].second == 1){ x = 1.0 * (tip - cod[nod].first - cod[vecin].first) / 2; found = 1; break; /// ai aflat x } else { x = 1.0 * (cod[vecin].first - tip + cod[nod].first) / 2; found = 1; break; } } } } } if (!found){ x = 0; found = 1; } if (found){ dq.clear(); dq.push_back(1); f[1] = 2; sol[1] = x; while (!dq.empty()){ nod = dq.front(); dq.pop_front(); for (i = 0 ; i < v[nod].size() ; i++){ vecin = v[nod][i].first; tip = v[nod][i].second; if (f[vecin] != 2){ dq.push_back(vecin); f[vecin] = 2; sol[vecin] = tip - sol[nod]; } else { if (sol[vecin] != tip - sol[nod]){ fprintf (fout,"NO"); return 0; } } } } cout << "YES\n"; for (i = 1 ; i <= n ; i++){ cout << sol[i] << " "; } return 0; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2636 KB | answer = YES |
2 | Correct | 2 ms | 2636 KB | answer = YES |
3 | Correct | 2 ms | 2636 KB | answer = YES |
4 | Correct | 2 ms | 2636 KB | answer = NO |
5 | Incorrect | 2 ms | 2636 KB | Sum of endpoints for edge (5; 3) differs from the expected value 2. |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2636 KB | answer = YES |
2 | Correct | 2 ms | 2636 KB | answer = YES |
3 | Correct | 2 ms | 2636 KB | answer = YES |
4 | Correct | 2 ms | 2636 KB | answer = NO |
5 | Incorrect | 2 ms | 2636 KB | Sum of endpoints for edge (5; 3) differs from the expected value 2. |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2636 KB | answer = YES |
2 | Correct | 2 ms | 2636 KB | answer = YES |
3 | Correct | 2 ms | 2636 KB | answer = YES |
4 | Correct | 2 ms | 2636 KB | answer = NO |
5 | Incorrect | 2 ms | 2636 KB | Sum of endpoints for edge (5; 3) differs from the expected value 2. |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2636 KB | answer = YES |
2 | Correct | 2 ms | 2636 KB | answer = YES |
3 | Correct | 2 ms | 2636 KB | answer = YES |
4 | Correct | 2 ms | 2636 KB | answer = NO |
5 | Incorrect | 2 ms | 2636 KB | Sum of endpoints for edge (5; 3) differs from the expected value 2. |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2636 KB | answer = YES |
2 | Correct | 2 ms | 2636 KB | answer = YES |
3 | Correct | 2 ms | 2636 KB | answer = YES |
4 | Correct | 2 ms | 2636 KB | answer = NO |
5 | Incorrect | 2 ms | 2636 KB | Sum of endpoints for edge (5; 3) differs from the expected value 2. |
6 | Halted | 0 ms | 0 KB | - |