# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
342937 | 2021-01-03T08:48:29 Z | mjhmjh1104 | Graph (BOI20_graph) | C++14 | 2 ms | 2668 KB |
#include <cstdio> #include <vector> #include <algorithm> using namespace std; int n, m; bool a[100006]; long long c[100006]; bool visited[100006]; vector<pair<int, int>> adj[100006]; vector<double> v; int sg(bool x) { if (x) return 1; else return -1; } void dfs(int x) { visited[x] = true; for (auto &i: adj[x]) { if (!visited[i.first]) { a[i.first] = !a[x]; c[i.first] = i.second - c[x]; dfs(i.first); } else { if (a[i.first] != a[x]) { if (c[i.first] + c[x] != i.second) { puts("NO"); exit(0); } } else v.push_back((double)(i.second - c[i.first] - c[x]) / (sg(a[i.first]) + sg(a[x]))); } } } int main() { scanf("%d%d", &n, &m); while (m--) { int u, v, c; scanf("%d%d%d", &u, &v, &c); u--, v--; adj[u].push_back({ v, c }); adj[v].push_back({ u, c }); } a[0] = 1, c[0] = 0; dfs(0); if (v.empty()) { puts("YES"); vector<long long> _a; for (int i = 0; i < n; i++) if (a[i]) _a.push_back(-c[i] * sg(a[i])); sort(_a.begin(), _a.end()); long long l = 0; if (!_a.empty()) l = _a[(int)_a.size() / 2]; for (int i = 0; i < n; i++) printf("%lld ", sg(a[i]) * l + c[i]); } else { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); if (v.size() != 1) puts("NO"); else { puts("YES"); for (int i = 0; i < n; i++) printf("%.10f ", sg(a[i]) * v[0] + c[i]); } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2668 KB | answer = YES |
2 | Correct | 2 ms | 2668 KB | answer = YES |
3 | Correct | 2 ms | 2668 KB | answer = YES |
4 | Correct | 2 ms | 2668 KB | answer = NO |
5 | Incorrect | 2 ms | 2668 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 | 2668 KB | answer = YES |
2 | Correct | 2 ms | 2668 KB | answer = YES |
3 | Correct | 2 ms | 2668 KB | answer = YES |
4 | Correct | 2 ms | 2668 KB | answer = NO |
5 | Incorrect | 2 ms | 2668 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 | 2668 KB | answer = YES |
2 | Correct | 2 ms | 2668 KB | answer = YES |
3 | Correct | 2 ms | 2668 KB | answer = YES |
4 | Correct | 2 ms | 2668 KB | answer = NO |
5 | Incorrect | 2 ms | 2668 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 | 2668 KB | answer = YES |
2 | Correct | 2 ms | 2668 KB | answer = YES |
3 | Correct | 2 ms | 2668 KB | answer = YES |
4 | Correct | 2 ms | 2668 KB | answer = NO |
5 | Incorrect | 2 ms | 2668 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 | 2668 KB | answer = YES |
2 | Correct | 2 ms | 2668 KB | answer = YES |
3 | Correct | 2 ms | 2668 KB | answer = YES |
4 | Correct | 2 ms | 2668 KB | answer = NO |
5 | Incorrect | 2 ms | 2668 KB | Sum of endpoints for edge (5; 3) differs from the expected value 2. |
6 | Halted | 0 ms | 0 KB | - |