# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
272336 | 2020-08-18T11:26:33 Z | arnold518 | Graph (BOI20_graph) | C++14 | 2 ms | 2688 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e5; int N, M; vector<pii> adj[MAXN+10]; bool vis[MAXN+10]; pii A[MAXN+10]; pii operator + (const pii &p, const pii &q) { return {p.first+q.first, p.second+q.second}; } pii operator - (const pii &p, const pii &q) { return {p.first-q.first, p.second-q.second}; } bool flag=true, chk; double val, ans[MAXN+10]; vector<int> V; void dfs(int now) { vis[now]=true; V.push_back(now); for(auto nxt : adj[now]) { if(vis[nxt.first]) { pii t=A[now]+A[nxt.first]; if(t.first==0) { if(t.second!=nxt.second) flag=false; } else { double p=(double)t.second/t.first; if(!chk) chk=true, val=p; else if(fabs(p-val)>1e-6) flag=false; } } else { A[nxt.first]=pii(0, nxt.second)-A[now]; dfs(nxt.first); } } } double f(double x) { double ret=0; for(auto it : V) ret+=fabs(A[it].first*x+A[it].second); return ret; } int main() { scanf("%d%d", &N, &M); for(int i=1; i<=M; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); adj[u].push_back({v, w}); adj[v].push_back({u, w}); } for(int i=1; i<=N; i++) { if(vis[i]) continue; V.clear(); chk=false; A[i]=pii(1, 0); dfs(i); if(chk) { for(auto it : V) ans[it]=A[it].first*val+A[it].second; } else { double lo=-1e6, hi=1e6; for(int j=0; j<100; j++) { double m1=(lo*2+hi)/3, m2=(lo+hi*2)/3; if(f(m1)<=f(m2)) hi=m2; else lo=m1; } for(auto it : V) ans[it]=A[it].first*lo+A[it].second; } } if(!flag) printf("NO\n"); else { printf("YES\n"); for(int i=1; i<=N; i++) printf("%.10f ", ans[i]); printf("\n"); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2688 KB | answer = YES |
2 | Correct | 2 ms | 2688 KB | answer = YES |
3 | Correct | 2 ms | 2688 KB | answer = YES |
4 | Correct | 2 ms | 2688 KB | answer = NO |
5 | Correct | 2 ms | 2688 KB | answer = YES |
6 | Correct | 2 ms | 2688 KB | answer = YES |
7 | Incorrect | 2 ms | 2688 KB | Sum of endpoints for edge (1; 3) differs from the expected value 1. |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2688 KB | answer = YES |
2 | Correct | 2 ms | 2688 KB | answer = YES |
3 | Correct | 2 ms | 2688 KB | answer = YES |
4 | Correct | 2 ms | 2688 KB | answer = NO |
5 | Correct | 2 ms | 2688 KB | answer = YES |
6 | Correct | 2 ms | 2688 KB | answer = YES |
7 | Incorrect | 2 ms | 2688 KB | Sum of endpoints for edge (1; 3) differs from the expected value 1. |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2688 KB | answer = YES |
2 | Correct | 2 ms | 2688 KB | answer = YES |
3 | Correct | 2 ms | 2688 KB | answer = YES |
4 | Correct | 2 ms | 2688 KB | answer = NO |
5 | Correct | 2 ms | 2688 KB | answer = YES |
6 | Correct | 2 ms | 2688 KB | answer = YES |
7 | Incorrect | 2 ms | 2688 KB | Sum of endpoints for edge (1; 3) differs from the expected value 1. |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2688 KB | answer = YES |
2 | Correct | 2 ms | 2688 KB | answer = YES |
3 | Correct | 2 ms | 2688 KB | answer = YES |
4 | Correct | 2 ms | 2688 KB | answer = NO |
5 | Correct | 2 ms | 2688 KB | answer = YES |
6 | Correct | 2 ms | 2688 KB | answer = YES |
7 | Incorrect | 2 ms | 2688 KB | Sum of endpoints for edge (1; 3) differs from the expected value 1. |
8 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2688 KB | answer = YES |
2 | Correct | 2 ms | 2688 KB | answer = YES |
3 | Correct | 2 ms | 2688 KB | answer = YES |
4 | Correct | 2 ms | 2688 KB | answer = NO |
5 | Correct | 2 ms | 2688 KB | answer = YES |
6 | Correct | 2 ms | 2688 KB | answer = YES |
7 | Incorrect | 2 ms | 2688 KB | Sum of endpoints for edge (1; 3) differs from the expected value 1. |
8 | Halted | 0 ms | 0 KB | - |