# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
342898 | 2021-01-03T07:52:42 Z | urd05 | Graph (BOI20_graph) | C++14 | 2 ms | 2668 KB |
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; vector<P> adj[100000]; P arr[100000]; bool visited[100000]; int ret[100000]; int chosen=-1e9; //두 배를 저장 const int nn=-1e9; vector<int> save; void dfs(int v,int x,int y) { if (visited[v]) { if (chosen==nn) { if (arr[v].first==x) { if (arr[v].second!=y) { printf("NO"); exit(0); } } else { chosen=(2*(arr[v].second-y))/(x-arr[v].first); } } else { if (x*chosen+y*2!=arr[v].first*chosen+arr[v].second*2) { printf("NO"); exit(0); } } return; } visited[v]=true; save.push_back(v); arr[v].first=x; arr[v].second=y; for(int i=0;i<adj[v].size();i++) { dfs(adj[v][i].first,-x,-y+adj[v][i].second); } } int main(void) { int n,m; scanf("%d %d",&n,&m); for(int i=0;i<m;i++) { int u,v,c; scanf("%d %d %d",&u,&v,&c); u--; v--; adj[u].push_back(P(v,c)); adj[v].push_back(P(u,c)); } for(int v=0;v<n;v++) { if (!visited[v]) { arr[v]=P(1,0); dfs(v,1,0); if (chosen==nn) { vector<int> vec; for(int i=0;i<save.size();i++) { int now=save[i]; if (arr[now].first==1) { vec.push_back(-arr[now].second); } else if (arr[now].first==-1) { vec.push_back(arr[now].second); } } sort(vec.begin(),vec.end()); chosen=vec[vec.size()/2]*2; } for(int i=0;i<save.size();i++) { int now=save[i]; ret[now]=arr[now].first*chosen+arr[now].second*2; } save.clear(); } } printf("YES\n"); for(int i=0;i<n;i++) { if (ret[i]>=0) printf("%d.%d ",ret[i]/2,(ret[i]%2)*5); else printf("-%d.%d",(-ret[i])/2,((-ret[i])%2)*5); } }
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 | participant answer is larger than the answer of jury |
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 | participant answer is larger than the answer of jury |
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 | participant answer is larger than the answer of jury |
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 | participant answer is larger than the answer of jury |
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 | participant answer is larger than the answer of jury |
6 | Halted | 0 ms | 0 KB | - |