# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
272380 | 2020-08-18T11:37:32 Z | arnold518 | Graph (BOI20_graph) | C++14 | 700 ms | 21572 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; long double val, ans[MAXN+10]; vector<int> V; long double ffabs(long double x) { if(x<0) return -x; return x; } 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 { long double p=((long double)nxt.second-(long double)t.second)/t.first; if(!chk) chk=true, val=p; else if(ffabs(p-val)>1e-10) flag=false; } } else { A[nxt.first]=pii(0, nxt.second)-A[now]; dfs(nxt.first); } } } long double f(long double x) { long double ret=0; for(auto it : V) ret+=ffabs(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 { long double lo=-1e6, hi=1e6; for(int j=0; j<600; j++) { long 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("%.20f ", (double)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 | 3 ms | 2688 KB | answer = NO |
5 | Correct | 2 ms | 2688 KB | answer = YES |
6 | Correct | 2 ms | 2688 KB | answer = YES |
7 | Correct | 6 ms | 2688 KB | answer = YES |
8 | Correct | 2 ms | 2816 KB | answer = YES |
9 | Correct | 3 ms | 2816 KB | answer = NO |
10 | Correct | 2 ms | 2688 KB | answer = YES |
11 | Correct | 3 ms | 2688 KB | answer = YES |
12 | Correct | 2 ms | 2688 KB | answer = NO |
13 | Correct | 2 ms | 2688 KB | answer = YES |
14 | Correct | 2 ms | 2688 KB | answer = YES |
15 | Correct | 2 ms | 2688 KB | answer = YES |
16 | Correct | 2 ms | 2688 KB | answer = YES |
17 | Correct | 2 ms | 2612 KB | answer = YES |
18 | Correct | 2 ms | 2688 KB | answer = YES |
19 | Correct | 2 ms | 2688 KB | answer = YES |
20 | Correct | 2 ms | 2688 KB | answer = YES |
21 | Correct | 2 ms | 2688 KB | answer = YES |
22 | Correct | 2 ms | 2688 KB | answer = NO |
23 | Correct | 2 ms | 2688 KB | answer = NO |
# | 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 | 3 ms | 2688 KB | answer = NO |
5 | Correct | 2 ms | 2688 KB | answer = YES |
6 | Correct | 2 ms | 2688 KB | answer = YES |
7 | Correct | 6 ms | 2688 KB | answer = YES |
8 | Correct | 2 ms | 2816 KB | answer = YES |
9 | Correct | 3 ms | 2816 KB | answer = NO |
10 | Correct | 2 ms | 2688 KB | answer = YES |
11 | Correct | 3 ms | 2688 KB | answer = YES |
12 | Correct | 2 ms | 2688 KB | answer = NO |
13 | Correct | 2 ms | 2688 KB | answer = YES |
14 | Correct | 2 ms | 2688 KB | answer = YES |
15 | Correct | 2 ms | 2688 KB | answer = YES |
16 | Correct | 2 ms | 2688 KB | answer = YES |
17 | Correct | 2 ms | 2612 KB | answer = YES |
18 | Correct | 2 ms | 2688 KB | answer = YES |
19 | Correct | 2 ms | 2688 KB | answer = YES |
20 | Correct | 2 ms | 2688 KB | answer = YES |
21 | Correct | 2 ms | 2688 KB | answer = YES |
22 | Correct | 2 ms | 2688 KB | answer = NO |
23 | Correct | 2 ms | 2688 KB | answer = NO |
24 | Correct | 3 ms | 2688 KB | answer = YES |
25 | Correct | 2 ms | 2688 KB | answer = YES |
26 | Correct | 2 ms | 2688 KB | answer = YES |
27 | Correct | 2 ms | 2688 KB | answer = YES |
28 | Correct | 2 ms | 2688 KB | answer = YES |
29 | Correct | 2 ms | 2688 KB | answer = YES |
30 | Correct | 2 ms | 2688 KB | answer = NO |
31 | Correct | 2 ms | 2688 KB | answer = YES |
32 | Correct | 2 ms | 2688 KB | answer = YES |
33 | Correct | 3 ms | 2688 KB | answer = YES |
34 | Correct | 2 ms | 2688 KB | answer = YES |
35 | Correct | 2 ms | 2688 KB | answer = YES |
36 | Correct | 2 ms | 2688 KB | answer = YES |
# | 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 | 3 ms | 2688 KB | answer = NO |
5 | Correct | 2 ms | 2688 KB | answer = YES |
6 | Correct | 2 ms | 2688 KB | answer = YES |
7 | Correct | 6 ms | 2688 KB | answer = YES |
8 | Correct | 2 ms | 2816 KB | answer = YES |
9 | Correct | 3 ms | 2816 KB | answer = NO |
10 | Correct | 2 ms | 2688 KB | answer = YES |
11 | Correct | 3 ms | 2688 KB | answer = YES |
12 | Correct | 2 ms | 2688 KB | answer = NO |
13 | Correct | 2 ms | 2688 KB | answer = YES |
14 | Correct | 2 ms | 2688 KB | answer = YES |
15 | Correct | 2 ms | 2688 KB | answer = YES |
16 | Correct | 2 ms | 2688 KB | answer = YES |
17 | Correct | 2 ms | 2612 KB | answer = YES |
18 | Correct | 2 ms | 2688 KB | answer = YES |
19 | Correct | 2 ms | 2688 KB | answer = YES |
20 | Correct | 2 ms | 2688 KB | answer = YES |
21 | Correct | 2 ms | 2688 KB | answer = YES |
22 | Correct | 2 ms | 2688 KB | answer = NO |
23 | Correct | 2 ms | 2688 KB | answer = NO |
24 | Correct | 3 ms | 2688 KB | answer = YES |
25 | Correct | 2 ms | 2688 KB | answer = YES |
26 | Correct | 2 ms | 2688 KB | answer = YES |
27 | Correct | 2 ms | 2688 KB | answer = YES |
28 | Correct | 2 ms | 2688 KB | answer = YES |
29 | Correct | 2 ms | 2688 KB | answer = YES |
30 | Correct | 2 ms | 2688 KB | answer = NO |
31 | Correct | 2 ms | 2688 KB | answer = YES |
32 | Correct | 2 ms | 2688 KB | answer = YES |
33 | Correct | 3 ms | 2688 KB | answer = YES |
34 | Correct | 2 ms | 2688 KB | answer = YES |
35 | Correct | 2 ms | 2688 KB | answer = YES |
36 | Correct | 2 ms | 2688 KB | answer = YES |
37 | Correct | 3 ms | 2688 KB | answer = YES |
38 | Correct | 2 ms | 2688 KB | answer = YES |
39 | Correct | 4 ms | 2688 KB | answer = YES |
40 | Correct | 3 ms | 2816 KB | answer = YES |
41 | Correct | 5 ms | 2688 KB | answer = NO |
42 | Correct | 6 ms | 2816 KB | answer = YES |
43 | Correct | 6 ms | 2816 KB | answer = YES |
44 | Correct | 6 ms | 2816 KB | answer = YES |
45 | Correct | 3 ms | 2816 KB | answer = YES |
46 | Correct | 4 ms | 2688 KB | answer = YES |
47 | Correct | 3 ms | 2816 KB | answer = YES |
48 | Correct | 3 ms | 2816 KB | answer = YES |
# | 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 | 3 ms | 2688 KB | answer = NO |
5 | Correct | 2 ms | 2688 KB | answer = YES |
6 | Correct | 2 ms | 2688 KB | answer = YES |
7 | Correct | 6 ms | 2688 KB | answer = YES |
8 | Correct | 2 ms | 2816 KB | answer = YES |
9 | Correct | 3 ms | 2816 KB | answer = NO |
10 | Correct | 2 ms | 2688 KB | answer = YES |
11 | Correct | 3 ms | 2688 KB | answer = YES |
12 | Correct | 2 ms | 2688 KB | answer = NO |
13 | Correct | 2 ms | 2688 KB | answer = YES |
14 | Correct | 2 ms | 2688 KB | answer = YES |
15 | Correct | 2 ms | 2688 KB | answer = YES |
16 | Correct | 2 ms | 2688 KB | answer = YES |
17 | Correct | 2 ms | 2612 KB | answer = YES |
18 | Correct | 2 ms | 2688 KB | answer = YES |
19 | Correct | 2 ms | 2688 KB | answer = YES |
20 | Correct | 2 ms | 2688 KB | answer = YES |
21 | Correct | 2 ms | 2688 KB | answer = YES |
22 | Correct | 2 ms | 2688 KB | answer = NO |
23 | Correct | 2 ms | 2688 KB | answer = NO |
24 | Correct | 3 ms | 2688 KB | answer = YES |
25 | Correct | 2 ms | 2688 KB | answer = YES |
26 | Correct | 2 ms | 2688 KB | answer = YES |
27 | Correct | 2 ms | 2688 KB | answer = YES |
28 | Correct | 2 ms | 2688 KB | answer = YES |
29 | Correct | 2 ms | 2688 KB | answer = YES |
30 | Correct | 2 ms | 2688 KB | answer = NO |
31 | Correct | 2 ms | 2688 KB | answer = YES |
32 | Correct | 2 ms | 2688 KB | answer = YES |
33 | Correct | 3 ms | 2688 KB | answer = YES |
34 | Correct | 2 ms | 2688 KB | answer = YES |
35 | Correct | 2 ms | 2688 KB | answer = YES |
36 | Correct | 2 ms | 2688 KB | answer = YES |
37 | Correct | 3 ms | 2688 KB | answer = YES |
38 | Correct | 2 ms | 2688 KB | answer = YES |
39 | Correct | 4 ms | 2688 KB | answer = YES |
40 | Correct | 3 ms | 2816 KB | answer = YES |
41 | Correct | 5 ms | 2688 KB | answer = NO |
42 | Correct | 6 ms | 2816 KB | answer = YES |
43 | Correct | 6 ms | 2816 KB | answer = YES |
44 | Correct | 6 ms | 2816 KB | answer = YES |
45 | Correct | 3 ms | 2816 KB | answer = YES |
46 | Correct | 4 ms | 2688 KB | answer = YES |
47 | Correct | 3 ms | 2816 KB | answer = YES |
48 | Correct | 3 ms | 2816 KB | answer = YES |
49 | Correct | 77 ms | 3580 KB | answer = YES |
50 | Correct | 12 ms | 3840 KB | answer = YES |
51 | Correct | 46 ms | 3832 KB | answer = YES |
52 | Correct | 40 ms | 3580 KB | answer = NO |
53 | Correct | 6 ms | 2816 KB | answer = YES |
54 | Correct | 13 ms | 2944 KB | answer = YES |
55 | Correct | 32 ms | 3192 KB | answer = YES |
56 | Correct | 73 ms | 3576 KB | answer = YES |
57 | Correct | 58 ms | 3576 KB | answer = YES |
58 | Correct | 52 ms | 3448 KB | answer = YES |
59 | Correct | 10 ms | 3456 KB | answer = YES |
60 | Correct | 62 ms | 3704 KB | answer = YES |
61 | Correct | 7 ms | 3200 KB | answer = YES |
62 | Correct | 88 ms | 7932 KB | answer = NO |
63 | Correct | 89 ms | 8060 KB | answer = YES |
64 | Correct | 90 ms | 7928 KB | answer = NO |
65 | Correct | 96 ms | 8132 KB | answer = YES |
66 | Correct | 10 ms | 2816 KB | answer = YES |
# | 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 | 3 ms | 2688 KB | answer = NO |
5 | Correct | 2 ms | 2688 KB | answer = YES |
6 | Correct | 2 ms | 2688 KB | answer = YES |
7 | Correct | 6 ms | 2688 KB | answer = YES |
8 | Correct | 2 ms | 2816 KB | answer = YES |
9 | Correct | 3 ms | 2816 KB | answer = NO |
10 | Correct | 2 ms | 2688 KB | answer = YES |
11 | Correct | 3 ms | 2688 KB | answer = YES |
12 | Correct | 2 ms | 2688 KB | answer = NO |
13 | Correct | 2 ms | 2688 KB | answer = YES |
14 | Correct | 2 ms | 2688 KB | answer = YES |
15 | Correct | 2 ms | 2688 KB | answer = YES |
16 | Correct | 2 ms | 2688 KB | answer = YES |
17 | Correct | 2 ms | 2612 KB | answer = YES |
18 | Correct | 2 ms | 2688 KB | answer = YES |
19 | Correct | 2 ms | 2688 KB | answer = YES |
20 | Correct | 2 ms | 2688 KB | answer = YES |
21 | Correct | 2 ms | 2688 KB | answer = YES |
22 | Correct | 2 ms | 2688 KB | answer = NO |
23 | Correct | 2 ms | 2688 KB | answer = NO |
24 | Correct | 3 ms | 2688 KB | answer = YES |
25 | Correct | 2 ms | 2688 KB | answer = YES |
26 | Correct | 2 ms | 2688 KB | answer = YES |
27 | Correct | 2 ms | 2688 KB | answer = YES |
28 | Correct | 2 ms | 2688 KB | answer = YES |
29 | Correct | 2 ms | 2688 KB | answer = YES |
30 | Correct | 2 ms | 2688 KB | answer = NO |
31 | Correct | 2 ms | 2688 KB | answer = YES |
32 | Correct | 2 ms | 2688 KB | answer = YES |
33 | Correct | 3 ms | 2688 KB | answer = YES |
34 | Correct | 2 ms | 2688 KB | answer = YES |
35 | Correct | 2 ms | 2688 KB | answer = YES |
36 | Correct | 2 ms | 2688 KB | answer = YES |
37 | Correct | 3 ms | 2688 KB | answer = YES |
38 | Correct | 2 ms | 2688 KB | answer = YES |
39 | Correct | 4 ms | 2688 KB | answer = YES |
40 | Correct | 3 ms | 2816 KB | answer = YES |
41 | Correct | 5 ms | 2688 KB | answer = NO |
42 | Correct | 6 ms | 2816 KB | answer = YES |
43 | Correct | 6 ms | 2816 KB | answer = YES |
44 | Correct | 6 ms | 2816 KB | answer = YES |
45 | Correct | 3 ms | 2816 KB | answer = YES |
46 | Correct | 4 ms | 2688 KB | answer = YES |
47 | Correct | 3 ms | 2816 KB | answer = YES |
48 | Correct | 3 ms | 2816 KB | answer = YES |
49 | Correct | 77 ms | 3580 KB | answer = YES |
50 | Correct | 12 ms | 3840 KB | answer = YES |
51 | Correct | 46 ms | 3832 KB | answer = YES |
52 | Correct | 40 ms | 3580 KB | answer = NO |
53 | Correct | 6 ms | 2816 KB | answer = YES |
54 | Correct | 13 ms | 2944 KB | answer = YES |
55 | Correct | 32 ms | 3192 KB | answer = YES |
56 | Correct | 73 ms | 3576 KB | answer = YES |
57 | Correct | 58 ms | 3576 KB | answer = YES |
58 | Correct | 52 ms | 3448 KB | answer = YES |
59 | Correct | 10 ms | 3456 KB | answer = YES |
60 | Correct | 62 ms | 3704 KB | answer = YES |
61 | Correct | 7 ms | 3200 KB | answer = YES |
62 | Correct | 88 ms | 7932 KB | answer = NO |
63 | Correct | 89 ms | 8060 KB | answer = YES |
64 | Correct | 90 ms | 7928 KB | answer = NO |
65 | Correct | 96 ms | 8132 KB | answer = YES |
66 | Correct | 10 ms | 2816 KB | answer = YES |
67 | Correct | 403 ms | 15984 KB | answer = YES |
68 | Correct | 334 ms | 17140 KB | answer = YES |
69 | Correct | 95 ms | 17140 KB | answer = YES |
70 | Correct | 165 ms | 21572 KB | answer = YES |
71 | Correct | 97 ms | 17140 KB | answer = YES |
72 | Execution timed out | 1066 ms | 13192 KB | Time limit exceeded |
73 | Halted | 0 ms | 0 KB | - |