oj.uz

Submission #670450

# Submission time Handle Problem Language Result Execution time Memory
670450 2022-12-09T06:42:04 Z jamezzz Graph (BOI20_graph) C++17
100 / 100
 139 ms 27936 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define sf scanf
#define pf printf
#define pb push_back
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;

#define maxn 100005

int n,m;
double ans[maxn];
ii val[maxn];
vector<int> sub;
vector<ii> AL[maxn];
vector<iii> back;

void dfs(int u,int p){
    sub.pb(u);
	for(auto[v,w]:AL[u]){
	    if(v==p)continue;
	    if(val[v].fi!=0)back.pb({u,v,w});
	    else{
	        val[v].fi=-val[u].fi;
	        val[v].se=w-val[u].se;
	        dfs(v,u);
	    }
	}
}

int main(){
	sf("%d%d",&n,&m);
	for(int i=0;i<m;++i){
		int a,b,c;sf("%d%d%d",&a,&b,&c);
		AL[a].pb({b,c});
		AL[b].pb({a,c});
	}
	for(int i=1;i<=n;++i){
		if(val[i].fi!=0)continue;
		back.clear();
		sub.clear();
		val[i]={1,0};
		dfs(i,-1);
		if(back.size()==0){
		    vector<double> xs;
		    for(int i:sub){
		        xs.pb(-(double)val[i].se/val[i].fi);
		    }
		    sort(all(xs));
		    double x=xs[xs.size()/2];
		    for(int i:sub){
		        ans[i]=x*val[i].fi+val[i].se;
		    }
		}
		else{
		    vector<double> xs;
		    for(int i:sub){
		        xs.pb(-(double)val[i].se/val[i].fi);
		    }
		    sort(all(xs));
		    double x=xs[xs.size()/2];
		    bool done=false,pos=true;
		    for(auto[a,b,c]:back){
    		    auto[a1,a2]=val[a];
    		    auto[b1,b2]=val[b];
    		    if(done){
    		        if(a1*x+a2+b1*x+b2!=c){
    		            pos=false;
    		            break;
    		        }
    		    }
    		    else{
    		        if(a1+b1==0){
    		            if(a2+b2!=c){
    		                pos=false;
    		                break;
    		            }
    		        }
    		        else{
    		            x=(double)(c-a2-b2)/(a1+b1);
    		            done=true;
    		        }
    		    }
		    }
		    if(!pos){
		        pf("NO\n");
		        exit(0);
		    }
		    for(int i:sub){
		        ans[i]=val[i].fi*x+val[i].se;
		    }
		}
	}
	pf("YES\n");
	for(int i=1;i<=n;++i){
	    pf("%f ",ans[i]);
	}
}

Compilation message

Graph.cpp: In function 'int main()':
Graph.cpp:36:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  sf("%d%d",&n,&m);
      |    ^
Graph.cpp:38:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   int a,b,c;sf("%d%d%d",&a,&b,&c);
      |               ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 1 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Correct 1 ms 2644 KB answer = YES
6 Correct 1 ms 2644 KB answer = YES
7 Correct 1 ms 2644 KB answer = YES
8 Correct 1 ms 2644 KB answer = YES
9 Correct 2 ms 2644 KB answer = NO
10 Correct 2 ms 2644 KB answer = YES
11 Correct 1 ms 2644 KB answer = YES
12 Correct 2 ms 2644 KB answer = NO
13 Correct 2 ms 2656 KB answer = YES
14 Correct 2 ms 2644 KB answer = YES
15 Correct 2 ms 2644 KB answer = YES
16 Correct 2 ms 2644 KB answer = YES
17 Correct 2 ms 2644 KB answer = YES
18 Correct 1 ms 2656 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 2 ms 2664 KB answer = YES
21 Correct 2 ms 2660 KB answer = YES
22 Correct 1 ms 2644 KB answer = NO
23 Correct 1 ms 2644 KB answer = NO

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 1 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Correct 1 ms 2644 KB answer = YES
6 Correct 1 ms 2644 KB answer = YES
7 Correct 1 ms 2644 KB answer = YES
8 Correct 1 ms 2644 KB answer = YES
9 Correct 2 ms 2644 KB answer = NO
10 Correct 2 ms 2644 KB answer = YES
11 Correct 1 ms 2644 KB answer = YES
12 Correct 2 ms 2644 KB answer = NO
13 Correct 2 ms 2656 KB answer = YES
14 Correct 2 ms 2644 KB answer = YES
15 Correct 2 ms 2644 KB answer = YES
16 Correct 2 ms 2644 KB answer = YES
17 Correct 2 ms 2644 KB answer = YES
18 Correct 1 ms 2656 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 2 ms 2664 KB answer = YES
21 Correct 2 ms 2660 KB answer = YES
22 Correct 1 ms 2644 KB answer = NO
23 Correct 1 ms 2644 KB answer = NO
24 Correct 1 ms 2644 KB answer = YES
25 Correct 2 ms 2600 KB answer = YES
26 Correct 2 ms 2644 KB answer = YES
27 Correct 1 ms 2644 KB answer = YES
28 Correct 2 ms 2644 KB answer = YES
29 Correct 2 ms 2644 KB answer = YES
30 Correct 1 ms 2660 KB answer = NO
31 Correct 2 ms 2644 KB answer = YES
32 Correct 2 ms 2644 KB answer = YES
33 Correct 1 ms 2644 KB answer = YES
34 Correct 2 ms 2660 KB answer = YES
35 Correct 2 ms 2656 KB answer = YES
36 Correct 1 ms 2644 KB answer = YES

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 1 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Correct 1 ms 2644 KB answer = YES
6 Correct 1 ms 2644 KB answer = YES
7 Correct 1 ms 2644 KB answer = YES
8 Correct 1 ms 2644 KB answer = YES
9 Correct 2 ms 2644 KB answer = NO
10 Correct 2 ms 2644 KB answer = YES
11 Correct 1 ms 2644 KB answer = YES
12 Correct 2 ms 2644 KB answer = NO
13 Correct 2 ms 2656 KB answer = YES
14 Correct 2 ms 2644 KB answer = YES
15 Correct 2 ms 2644 KB answer = YES
16 Correct 2 ms 2644 KB answer = YES
17 Correct 2 ms 2644 KB answer = YES
18 Correct 1 ms 2656 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 2 ms 2664 KB answer = YES
21 Correct 2 ms 2660 KB answer = YES
22 Correct 1 ms 2644 KB answer = NO
23 Correct 1 ms 2644 KB answer = NO
24 Correct 1 ms 2644 KB answer = YES
25 Correct 2 ms 2600 KB answer = YES
26 Correct 2 ms 2644 KB answer = YES
27 Correct 1 ms 2644 KB answer = YES
28 Correct 2 ms 2644 KB answer = YES
29 Correct 2 ms 2644 KB answer = YES
30 Correct 1 ms 2660 KB answer = NO
31 Correct 2 ms 2644 KB answer = YES
32 Correct 2 ms 2644 KB answer = YES
33 Correct 1 ms 2644 KB answer = YES
34 Correct 2 ms 2660 KB answer = YES
35 Correct 2 ms 2656 KB answer = YES
36 Correct 1 ms 2644 KB answer = YES
37 Correct 2 ms 2644 KB answer = YES
38 Correct 2 ms 2644 KB answer = YES
39 Correct 2 ms 2644 KB answer = YES
40 Correct 2 ms 2644 KB answer = YES
41 Correct 2 ms 2644 KB answer = NO
42 Correct 2 ms 2668 KB answer = YES
43 Correct 3 ms 2644 KB answer = YES
44 Correct 2 ms 2644 KB answer = YES
45 Correct 2 ms 2644 KB answer = YES
46 Correct 2 ms 2644 KB answer = YES
47 Correct 2 ms 2644 KB answer = YES
48 Correct 2 ms 2644 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 1 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Correct 1 ms 2644 KB answer = YES
6 Correct 1 ms 2644 KB answer = YES
7 Correct 1 ms 2644 KB answer = YES
8 Correct 1 ms 2644 KB answer = YES
9 Correct 2 ms 2644 KB answer = NO
10 Correct 2 ms 2644 KB answer = YES
11 Correct 1 ms 2644 KB answer = YES
12 Correct 2 ms 2644 KB answer = NO
13 Correct 2 ms 2656 KB answer = YES
14 Correct 2 ms 2644 KB answer = YES
15 Correct 2 ms 2644 KB answer = YES
16 Correct 2 ms 2644 KB answer = YES
17 Correct 2 ms 2644 KB answer = YES
18 Correct 1 ms 2656 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 2 ms 2664 KB answer = YES
21 Correct 2 ms 2660 KB answer = YES
22 Correct 1 ms 2644 KB answer = NO
23 Correct 1 ms 2644 KB answer = NO
24 Correct 1 ms 2644 KB answer = YES
25 Correct 2 ms 2600 KB answer = YES
26 Correct 2 ms 2644 KB answer = YES
27 Correct 1 ms 2644 KB answer = YES
28 Correct 2 ms 2644 KB answer = YES
29 Correct 2 ms 2644 KB answer = YES
30 Correct 1 ms 2660 KB answer = NO
31 Correct 2 ms 2644 KB answer = YES
32 Correct 2 ms 2644 KB answer = YES
33 Correct 1 ms 2644 KB answer = YES
34 Correct 2 ms 2660 KB answer = YES
35 Correct 2 ms 2656 KB answer = YES
36 Correct 1 ms 2644 KB answer = YES
37 Correct 2 ms 2644 KB answer = YES
38 Correct 2 ms 2644 KB answer = YES
39 Correct 2 ms 2644 KB answer = YES
40 Correct 2 ms 2644 KB answer = YES
41 Correct 2 ms 2644 KB answer = NO
42 Correct 2 ms 2668 KB answer = YES
43 Correct 3 ms 2644 KB answer = YES
44 Correct 2 ms 2644 KB answer = YES
45 Correct 2 ms 2644 KB answer = YES
46 Correct 2 ms 2644 KB answer = YES
47 Correct 2 ms 2644 KB answer = YES
48 Correct 2 ms 2644 KB answer = YES
49 Correct 8 ms 3488 KB answer = YES
50 Correct 9 ms 4052 KB answer = YES
51 Correct 8 ms 4036 KB answer = YES
52 Correct 6 ms 3924 KB answer = NO
53 Correct 2 ms 2644 KB answer = YES
54 Correct 3 ms 2900 KB answer = YES
55 Correct 5 ms 3156 KB answer = YES
56 Correct 8 ms 3540 KB answer = YES
57 Correct 8 ms 3412 KB answer = YES
58 Correct 8 ms 3428 KB answer = YES
59 Correct 7 ms 3412 KB answer = YES
60 Correct 11 ms 3540 KB answer = YES
61 Correct 5 ms 3156 KB answer = YES
62 Correct 61 ms 16640 KB answer = NO
63 Correct 71 ms 16692 KB answer = YES
64 Correct 61 ms 16756 KB answer = NO
65 Correct 64 ms 16656 KB answer = YES
66 Correct 3 ms 2772 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB answer = YES
2 Correct 1 ms 2644 KB answer = YES
3 Correct 2 ms 2644 KB answer = YES
4 Correct 2 ms 2644 KB answer = NO
5 Correct 1 ms 2644 KB answer = YES
6 Correct 1 ms 2644 KB answer = YES
7 Correct 1 ms 2644 KB answer = YES
8 Correct 1 ms 2644 KB answer = YES
9 Correct 2 ms 2644 KB answer = NO
10 Correct 2 ms 2644 KB answer = YES
11 Correct 1 ms 2644 KB answer = YES
12 Correct 2 ms 2644 KB answer = NO
13 Correct 2 ms 2656 KB answer = YES
14 Correct 2 ms 2644 KB answer = YES
15 Correct 2 ms 2644 KB answer = YES
16 Correct 2 ms 2644 KB answer = YES
17 Correct 2 ms 2644 KB answer = YES
18 Correct 1 ms 2656 KB answer = YES
19 Correct 2 ms 2644 KB answer = YES
20 Correct 2 ms 2664 KB answer = YES
21 Correct 2 ms 2660 KB answer = YES
22 Correct 1 ms 2644 KB answer = NO
23 Correct 1 ms 2644 KB answer = NO
24 Correct 1 ms 2644 KB answer = YES
25 Correct 2 ms 2600 KB answer = YES
26 Correct 2 ms 2644 KB answer = YES
27 Correct 1 ms 2644 KB answer = YES
28 Correct 2 ms 2644 KB answer = YES
29 Correct 2 ms 2644 KB answer = YES
30 Correct 1 ms 2660 KB answer = NO
31 Correct 2 ms 2644 KB answer = YES
32 Correct 2 ms 2644 KB answer = YES
33 Correct 1 ms 2644 KB answer = YES
34 Correct 2 ms 2660 KB answer = YES
35 Correct 2 ms 2656 KB answer = YES
36 Correct 1 ms 2644 KB answer = YES
37 Correct 2 ms 2644 KB answer = YES
38 Correct 2 ms 2644 KB answer = YES
39 Correct 2 ms 2644 KB answer = YES
40 Correct 2 ms 2644 KB answer = YES
41 Correct 2 ms 2644 KB answer = NO
42 Correct 2 ms 2668 KB answer = YES
43 Correct 3 ms 2644 KB answer = YES
44 Correct 2 ms 2644 KB answer = YES
45 Correct 2 ms 2644 KB answer = YES
46 Correct 2 ms 2644 KB answer = YES
47 Correct 2 ms 2644 KB answer = YES
48 Correct 2 ms 2644 KB answer = YES
49 Correct 8 ms 3488 KB answer = YES
50 Correct 9 ms 4052 KB answer = YES
51 Correct 8 ms 4036 KB answer = YES
52 Correct 6 ms 3924 KB answer = NO
53 Correct 2 ms 2644 KB answer = YES
54 Correct 3 ms 2900 KB answer = YES
55 Correct 5 ms 3156 KB answer = YES
56 Correct 8 ms 3540 KB answer = YES
57 Correct 8 ms 3412 KB answer = YES
58 Correct 8 ms 3428 KB answer = YES
59 Correct 7 ms 3412 KB answer = YES
60 Correct 11 ms 3540 KB answer = YES
61 Correct 5 ms 3156 KB answer = YES
62 Correct 61 ms 16640 KB answer = NO
63 Correct 71 ms 16692 KB answer = YES
64 Correct 61 ms 16756 KB answer = NO
65 Correct 64 ms 16656 KB answer = YES
66 Correct 3 ms 2772 KB answer = YES
67 Correct 77 ms 19760 KB answer = YES
68 Correct 64 ms 19388 KB answer = YES
69 Correct 64 ms 19380 KB answer = YES
70 Correct 103 ms 27936 KB answer = YES
71 Correct 70 ms 19516 KB answer = YES
72 Correct 73 ms 10648 KB answer = YES
73 Correct 90 ms 10692 KB answer = YES
74 Correct 54 ms 12364 KB answer = YES
75 Correct 32 ms 11688 KB answer = NO
76 Correct 9 ms 3788 KB answer = YES
77 Correct 19 ms 4728 KB answer = YES
78 Correct 32 ms 6124 KB answer = YES
79 Correct 69 ms 9512 KB answer = YES
80 Correct 53 ms 12376 KB answer = YES
81 Correct 52 ms 14252 KB answer = NO
82 Correct 88 ms 18688 KB answer = YES
83 Correct 102 ms 19560 KB answer = YES
84 Correct 92 ms 19536 KB answer = YES
85 Correct 73 ms 19592 KB answer = YES
86 Correct 73 ms 19528 KB answer = YES
87 Correct 53 ms 11936 KB answer = NO
88 Correct 95 ms 13952 KB answer = YES
89 Correct 76 ms 9548 KB answer = YES
90 Correct 80 ms 9484 KB answer = YES
91 Correct 74 ms 9556 KB answer = YES
92 Correct 38 ms 6688 KB answer = YES
93 Correct 35 ms 6692 KB answer = YES
94 Correct 57 ms 18816 KB answer = NO
95 Correct 41 ms 8584 KB answer = NO
96 Correct 139 ms 24168 KB answer = YES
97 Correct 43 ms 18804 KB answer = NO