# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
958129 | 2024-04-05T01:51:12 Z | kanpham | Graph (BOI20_graph) | C++14 | 2 ms | 4188 KB |
#include <bits/stdc++.h> #define endl "\n" using namespace std; const int MAX = 1e5+2; const double err = 1e-6; int n; vector<array<int,2>> g[MAX]; bool vis[MAX]; double ans[MAX]; complex<int> linear[MAX]; void sakujo(){ cout << "NO"; exit(0); } vector<int> hist; double key; void dfs(int s){ vis[s] = true; hist.push_back(s); for (auto e:g[s]){ int v = e[0]; complex<int> sum = {e[1], 0}; if (vis[v]){ int a1 = linear[v].real(), a2 = linear[s].real(), b1 = linear[v].imag(), b2 = linear[s].imag(); if (b1 + b2 == 0){ if (a1 + a2 == e[1]) continue; sakujo(); } key = ((double)e[1] - a1 - a2) / ((double)b1 + b2); continue; } linear[v] = sum - linear[s]; dfs(v); } } void calc(int s, double val){ vis[s] = true; ans[s] = linear[s].real() + linear[s].imag() * val; for (auto e:g[s]){ int v = e[0]; if (!vis[v]) calc(v, val); } } void verify(int s){ vis[s] = true; for (auto e:g[s]){ int v = e[0]; double sum = e[1]; if (abs(ans[s] + ans[v] - sum) > err) sakujo(); if (!vis[v]) verify(v); } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); #define FILENAME "graph" if (fopen(FILENAME".inp","r")){ freopen(FILENAME".inp","r",stdin); freopen(FILENAME".out","w",stdout); } int m; cin >> n >> m; while (m--){ int u, v, c; cin >> u >> v >> c; g[u].push_back({v, c}); g[v].push_back({u, c}); } for (int i=1; i<=n; ++i){ if (!vis[i]){ hist.clear(); linear[i] = {0, 1}; dfs(i); for (int v:hist) vis[v] = false; calc(i, key); for (int v:hist) vis[v] = false; verify(i); } } cout << "YES\n" << setprecision(6); for (int i=1; i<=n; ++i) cout << ans[i] << ' '; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4184 KB | answer = YES |
2 | Correct | 2 ms | 4188 KB | answer = YES |
3 | Correct | 2 ms | 4188 KB | answer = YES |
4 | Correct | 1 ms | 4184 KB | answer = NO |
5 | Correct | 1 ms | 4188 KB | answer = YES |
6 | Incorrect | 2 ms | 4184 KB | participant answer is larger than the answer of jury |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4184 KB | answer = YES |
2 | Correct | 2 ms | 4188 KB | answer = YES |
3 | Correct | 2 ms | 4188 KB | answer = YES |
4 | Correct | 1 ms | 4184 KB | answer = NO |
5 | Correct | 1 ms | 4188 KB | answer = YES |
6 | Incorrect | 2 ms | 4184 KB | participant answer is larger than the answer of jury |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4184 KB | answer = YES |
2 | Correct | 2 ms | 4188 KB | answer = YES |
3 | Correct | 2 ms | 4188 KB | answer = YES |
4 | Correct | 1 ms | 4184 KB | answer = NO |
5 | Correct | 1 ms | 4188 KB | answer = YES |
6 | Incorrect | 2 ms | 4184 KB | participant answer is larger than the answer of jury |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4184 KB | answer = YES |
2 | Correct | 2 ms | 4188 KB | answer = YES |
3 | Correct | 2 ms | 4188 KB | answer = YES |
4 | Correct | 1 ms | 4184 KB | answer = NO |
5 | Correct | 1 ms | 4188 KB | answer = YES |
6 | Incorrect | 2 ms | 4184 KB | participant answer is larger than the answer of jury |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4184 KB | answer = YES |
2 | Correct | 2 ms | 4188 KB | answer = YES |
3 | Correct | 2 ms | 4188 KB | answer = YES |
4 | Correct | 1 ms | 4184 KB | answer = NO |
5 | Correct | 1 ms | 4188 KB | answer = YES |
6 | Incorrect | 2 ms | 4184 KB | participant answer is larger than the answer of jury |
7 | Halted | 0 ms | 0 KB | - |