# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
342899 | 2021-01-03T07:53:18 Z | urd05 | Graph (BOI20_graph) | C++14 | 3 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]) { chosen=nn; 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2668 KB | answer = YES |
2 | Correct | 3 ms | 2668 KB | answer = YES |
3 | Correct | 3 ms | 2668 KB | answer = YES |
4 | Correct | 2 ms | 2668 KB | answer = NO |
5 | Correct | 2 ms | 2668 KB | answer = YES |
6 | Correct | 2 ms | 2668 KB | answer = YES |
7 | Correct | 2 ms | 2668 KB | answer = YES |
8 | Correct | 2 ms | 2668 KB | answer = YES |
9 | Correct | 2 ms | 2668 KB | answer = NO |
10 | Correct | 2 ms | 2668 KB | answer = YES |
11 | Correct | 2 ms | 2668 KB | answer = YES |
12 | Correct | 2 ms | 2668 KB | answer = NO |
13 | Correct | 2 ms | 2668 KB | answer = YES |
14 | Correct | 2 ms | 2668 KB | answer = YES |
15 | Correct | 2 ms | 2668 KB | answer = YES |
16 | Correct | 2 ms | 2668 KB | answer = YES |
17 | Correct | 2 ms | 2668 KB | answer = YES |
18 | Correct | 2 ms | 2668 KB | answer = YES |
19 | Correct | 2 ms | 2668 KB | answer = YES |
20 | Correct | 2 ms | 2668 KB | answer = YES |
21 | Correct | 2 ms | 2668 KB | answer = YES |
22 | Correct | 2 ms | 2668 KB | answer = NO |
23 | Correct | 2 ms | 2668 KB | answer = NO |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2668 KB | answer = YES |
2 | Correct | 3 ms | 2668 KB | answer = YES |
3 | Correct | 3 ms | 2668 KB | answer = YES |
4 | Correct | 2 ms | 2668 KB | answer = NO |
5 | Correct | 2 ms | 2668 KB | answer = YES |
6 | Correct | 2 ms | 2668 KB | answer = YES |
7 | Correct | 2 ms | 2668 KB | answer = YES |
8 | Correct | 2 ms | 2668 KB | answer = YES |
9 | Correct | 2 ms | 2668 KB | answer = NO |
10 | Correct | 2 ms | 2668 KB | answer = YES |
11 | Correct | 2 ms | 2668 KB | answer = YES |
12 | Correct | 2 ms | 2668 KB | answer = NO |
13 | Correct | 2 ms | 2668 KB | answer = YES |
14 | Correct | 2 ms | 2668 KB | answer = YES |
15 | Correct | 2 ms | 2668 KB | answer = YES |
16 | Correct | 2 ms | 2668 KB | answer = YES |
17 | Correct | 2 ms | 2668 KB | answer = YES |
18 | Correct | 2 ms | 2668 KB | answer = YES |
19 | Correct | 2 ms | 2668 KB | answer = YES |
20 | Correct | 2 ms | 2668 KB | answer = YES |
21 | Correct | 2 ms | 2668 KB | answer = YES |
22 | Correct | 2 ms | 2668 KB | answer = NO |
23 | Correct | 2 ms | 2668 KB | answer = NO |
24 | Incorrect | 2 ms | 2668 KB | Expected double, but "-1.0-1.01.0" found |
25 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2668 KB | answer = YES |
2 | Correct | 3 ms | 2668 KB | answer = YES |
3 | Correct | 3 ms | 2668 KB | answer = YES |
4 | Correct | 2 ms | 2668 KB | answer = NO |
5 | Correct | 2 ms | 2668 KB | answer = YES |
6 | Correct | 2 ms | 2668 KB | answer = YES |
7 | Correct | 2 ms | 2668 KB | answer = YES |
8 | Correct | 2 ms | 2668 KB | answer = YES |
9 | Correct | 2 ms | 2668 KB | answer = NO |
10 | Correct | 2 ms | 2668 KB | answer = YES |
11 | Correct | 2 ms | 2668 KB | answer = YES |
12 | Correct | 2 ms | 2668 KB | answer = NO |
13 | Correct | 2 ms | 2668 KB | answer = YES |
14 | Correct | 2 ms | 2668 KB | answer = YES |
15 | Correct | 2 ms | 2668 KB | answer = YES |
16 | Correct | 2 ms | 2668 KB | answer = YES |
17 | Correct | 2 ms | 2668 KB | answer = YES |
18 | Correct | 2 ms | 2668 KB | answer = YES |
19 | Correct | 2 ms | 2668 KB | answer = YES |
20 | Correct | 2 ms | 2668 KB | answer = YES |
21 | Correct | 2 ms | 2668 KB | answer = YES |
22 | Correct | 2 ms | 2668 KB | answer = NO |
23 | Correct | 2 ms | 2668 KB | answer = NO |
24 | Incorrect | 2 ms | 2668 KB | Expected double, but "-1.0-1.01.0" found |
25 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2668 KB | answer = YES |
2 | Correct | 3 ms | 2668 KB | answer = YES |
3 | Correct | 3 ms | 2668 KB | answer = YES |
4 | Correct | 2 ms | 2668 KB | answer = NO |
5 | Correct | 2 ms | 2668 KB | answer = YES |
6 | Correct | 2 ms | 2668 KB | answer = YES |
7 | Correct | 2 ms | 2668 KB | answer = YES |
8 | Correct | 2 ms | 2668 KB | answer = YES |
9 | Correct | 2 ms | 2668 KB | answer = NO |
10 | Correct | 2 ms | 2668 KB | answer = YES |
11 | Correct | 2 ms | 2668 KB | answer = YES |
12 | Correct | 2 ms | 2668 KB | answer = NO |
13 | Correct | 2 ms | 2668 KB | answer = YES |
14 | Correct | 2 ms | 2668 KB | answer = YES |
15 | Correct | 2 ms | 2668 KB | answer = YES |
16 | Correct | 2 ms | 2668 KB | answer = YES |
17 | Correct | 2 ms | 2668 KB | answer = YES |
18 | Correct | 2 ms | 2668 KB | answer = YES |
19 | Correct | 2 ms | 2668 KB | answer = YES |
20 | Correct | 2 ms | 2668 KB | answer = YES |
21 | Correct | 2 ms | 2668 KB | answer = YES |
22 | Correct | 2 ms | 2668 KB | answer = NO |
23 | Correct | 2 ms | 2668 KB | answer = NO |
24 | Incorrect | 2 ms | 2668 KB | Expected double, but "-1.0-1.01.0" found |
25 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2668 KB | answer = YES |
2 | Correct | 3 ms | 2668 KB | answer = YES |
3 | Correct | 3 ms | 2668 KB | answer = YES |
4 | Correct | 2 ms | 2668 KB | answer = NO |
5 | Correct | 2 ms | 2668 KB | answer = YES |
6 | Correct | 2 ms | 2668 KB | answer = YES |
7 | Correct | 2 ms | 2668 KB | answer = YES |
8 | Correct | 2 ms | 2668 KB | answer = YES |
9 | Correct | 2 ms | 2668 KB | answer = NO |
10 | Correct | 2 ms | 2668 KB | answer = YES |
11 | Correct | 2 ms | 2668 KB | answer = YES |
12 | Correct | 2 ms | 2668 KB | answer = NO |
13 | Correct | 2 ms | 2668 KB | answer = YES |
14 | Correct | 2 ms | 2668 KB | answer = YES |
15 | Correct | 2 ms | 2668 KB | answer = YES |
16 | Correct | 2 ms | 2668 KB | answer = YES |
17 | Correct | 2 ms | 2668 KB | answer = YES |
18 | Correct | 2 ms | 2668 KB | answer = YES |
19 | Correct | 2 ms | 2668 KB | answer = YES |
20 | Correct | 2 ms | 2668 KB | answer = YES |
21 | Correct | 2 ms | 2668 KB | answer = YES |
22 | Correct | 2 ms | 2668 KB | answer = NO |
23 | Correct | 2 ms | 2668 KB | answer = NO |
24 | Incorrect | 2 ms | 2668 KB | Expected double, but "-1.0-1.01.0" found |
25 | Halted | 0 ms | 0 KB | - |