oj.uz

Submission #939958

# Submission time Handle Problem Language Result Execution time Memory
939958 2024-03-07T02:28:34 Z pcc Graph (BOI20_graph) C++14
100 / 100
 186 ms 36828 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define ld long double

const int mxn = 2e5+10;
int N,M;
vector<pii> paths[mxn];
int idx[mxn];
vector<pair<pii,int>> back_edge;
int col[mxn];
pii dp[mxn];//val = dp[i].fs*x+dp[i].sc
ld ans[mxn];
int cnt = 0;
vector<int> all;

void dfs1(int now,int pid){
	all.push_back(now);
	idx[now] = ++cnt;
	for(auto nxt:paths[now]){
		if(nxt.sc == pid)continue;
		if(idx[nxt.fs]){
			back_edge.push_back({{now,nxt.fs},col[nxt.sc]});
		}
		else{
			auto tmp = dp[now];
			tmp.fs = -tmp.fs,tmp.sc = -tmp.sc;
			tmp.sc += col[nxt.sc];
			dp[nxt.fs] = tmp;
			dfs1(nxt.fs,nxt.sc);
		}
	}
	return;
}

int get_med(int now){
	vector<ld> v;
	for(auto &i:all){
		v.push_back(-dp[i].sc/(ld)dp[i].fs);
	}
	sort(v.begin(),v.end());
	return v[v.size()/2];
}
ld get_x(int now){
	ld X;
	while(!back_edge.empty()){
		int a = back_edge.back().fs.fs,b = back_edge.back().fs.sc;
		if(dp[a].fs+dp[b].fs == 0)back_edge.pop_back();
		else break;
	}
	if(back_edge.empty()){
		X = get_med(now);
	}
	else{
		int a = back_edge.back().fs.fs,b = back_edge.back().fs.sc,tar = back_edge.back().sc;
		pii s = {dp[a].fs+dp[b].fs,dp[a].sc+dp[b].sc};
		tar -= s.sc;
		X = tar/(ld)s.fs;
	}
	return X;
}

void dfs2(int now,int pid,ld X){
	ans[now] = dp[now].fs*X+dp[now].sc;
	for(auto nxt:paths[now]){
		if(ans[nxt.fs]>1e8)dfs2(nxt.fs,nxt.sc,X);
	}
	return;
}

bool check(){
	for(int i = 1;i<=N;i++){
		for(auto nxt:paths[i]){
			if(abs(ans[i]+ans[nxt.fs]-col[nxt.sc])>1e-6)return false;
		}
	}
	return true;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	for(int i = 1;i<=M;i++){
		int a,b,c;
		cin>>a>>b>>c;
		paths[a].push_back({b,i});
		paths[b].push_back({a,i});
		col[i] = c;
	}
	for(int i = 1;i<=N;i++)ans[i] = 1e9;
	for(int i = 1;i<=N;i++){
		if(idx[i])continue;
		dp[i] = {1,0};
		dfs1(i,0);
		dfs2(i,0,get_x(i));
		all.clear();
		back_edge.clear();
	}
	if(!check()){
		cout<<"NO\n";
		return 0;
	}
	cout<<"YES\n";
	for(int i = 1;i<=N;i++)cout<<fixed<<setprecision(20)<<ans[i]<<' ';cout<<'\n';
	return 0;
}

Compilation message

Graph.cpp: In function 'int main()':
Graph.cpp:110:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  110 |  for(int i = 1;i<=N;i++)cout<<fixed<<setprecision(20)<<ans[i]<<' ';cout<<'\n';
      |  ^~~
Graph.cpp:110:68: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  110 |  for(int i = 1;i<=N;i++)cout<<fixed<<setprecision(20)<<ans[i]<<' ';cout<<'\n';
      |                                                                    ^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
17.0 / 17.0

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

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB answer = YES
2 Correct 2 ms 9048 KB answer = YES
3 Correct 2 ms 9052 KB answer = YES
4 Correct 2 ms 9052 KB answer = NO
5 Correct 2 ms 9052 KB answer = YES
6 Correct 2 ms 9052 KB answer = YES
7 Correct 2 ms 9052 KB answer = YES
8 Correct 2 ms 9052 KB answer = YES
9 Correct 2 ms 9052 KB answer = NO
10 Correct 2 ms 9052 KB answer = YES
11 Correct 2 ms 9048 KB answer = YES
12 Correct 2 ms 9052 KB answer = NO
13 Correct 2 ms 9052 KB answer = YES
14 Correct 2 ms 9052 KB answer = YES
15 Correct 2 ms 9052 KB answer = YES
16 Correct 2 ms 9052 KB answer = YES
17 Correct 2 ms 9052 KB answer = YES
18 Correct 2 ms 9052 KB answer = YES
19 Correct 2 ms 9052 KB answer = YES
20 Correct 3 ms 9052 KB answer = YES
21 Correct 2 ms 9052 KB answer = YES
22 Correct 2 ms 9052 KB answer = NO
23 Correct 2 ms 9052 KB answer = NO
24 Correct 2 ms 9052 KB answer = YES
25 Correct 2 ms 9048 KB answer = YES
26 Correct 2 ms 9048 KB answer = YES
27 Correct 2 ms 9052 KB answer = YES
28 Correct 2 ms 9048 KB answer = YES
29 Correct 2 ms 9052 KB answer = YES
30 Correct 2 ms 9052 KB answer = NO
31 Correct 2 ms 9052 KB answer = YES
32 Correct 2 ms 9052 KB answer = YES
33 Correct 2 ms 9132 KB answer = YES
34 Correct 2 ms 9052 KB answer = YES
35 Correct 2 ms 9052 KB answer = YES
36 Correct 3 ms 9052 KB answer = YES
37 Correct 2 ms 9048 KB answer = YES
38 Correct 3 ms 9052 KB answer = YES
39 Correct 2 ms 9204 KB answer = YES
40 Correct 2 ms 9308 KB answer = YES
41 Correct 2 ms 9308 KB answer = NO
42 Correct 3 ms 9144 KB answer = YES
43 Correct 3 ms 9284 KB answer = YES
44 Correct 3 ms 9196 KB answer = YES
45 Correct 3 ms 9052 KB answer = YES
46 Correct 2 ms 9052 KB answer = YES
47 Correct 3 ms 9304 KB answer = YES
48 Correct 3 ms 9308 KB answer = YES
49 Correct 11 ms 10076 KB answer = YES
50 Correct 11 ms 10732 KB answer = YES
51 Correct 11 ms 10844 KB answer = YES
52 Correct 6 ms 10844 KB answer = NO
53 Correct 3 ms 9560 KB answer = YES
54 Correct 5 ms 9308 KB answer = YES
55 Correct 8 ms 9740 KB answer = YES
56 Correct 10 ms 10108 KB answer = YES
57 Correct 9 ms 10076 KB answer = YES
58 Correct 9 ms 10148 KB answer = YES
59 Correct 12 ms 9820 KB answer = YES
60 Correct 10 ms 10260 KB answer = YES
61 Correct 6 ms 9564 KB answer = YES
62 Correct 47 ms 24664 KB answer = NO
63 Correct 74 ms 23872 KB answer = YES
64 Correct 48 ms 23792 KB answer = NO
65 Correct 52 ms 23536 KB answer = YES
66 Correct 4 ms 9560 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB answer = YES
2 Correct 2 ms 9048 KB answer = YES
3 Correct 2 ms 9052 KB answer = YES
4 Correct 2 ms 9052 KB answer = NO
5 Correct 2 ms 9052 KB answer = YES
6 Correct 2 ms 9052 KB answer = YES
7 Correct 2 ms 9052 KB answer = YES
8 Correct 2 ms 9052 KB answer = YES
9 Correct 2 ms 9052 KB answer = NO
10 Correct 2 ms 9052 KB answer = YES
11 Correct 2 ms 9048 KB answer = YES
12 Correct 2 ms 9052 KB answer = NO
13 Correct 2 ms 9052 KB answer = YES
14 Correct 2 ms 9052 KB answer = YES
15 Correct 2 ms 9052 KB answer = YES
16 Correct 2 ms 9052 KB answer = YES
17 Correct 2 ms 9052 KB answer = YES
18 Correct 2 ms 9052 KB answer = YES
19 Correct 2 ms 9052 KB answer = YES
20 Correct 3 ms 9052 KB answer = YES
21 Correct 2 ms 9052 KB answer = YES
22 Correct 2 ms 9052 KB answer = NO
23 Correct 2 ms 9052 KB answer = NO
24 Correct 2 ms 9052 KB answer = YES
25 Correct 2 ms 9048 KB answer = YES
26 Correct 2 ms 9048 KB answer = YES
27 Correct 2 ms 9052 KB answer = YES
28 Correct 2 ms 9048 KB answer = YES
29 Correct 2 ms 9052 KB answer = YES
30 Correct 2 ms 9052 KB answer = NO
31 Correct 2 ms 9052 KB answer = YES
32 Correct 2 ms 9052 KB answer = YES
33 Correct 2 ms 9132 KB answer = YES
34 Correct 2 ms 9052 KB answer = YES
35 Correct 2 ms 9052 KB answer = YES
36 Correct 3 ms 9052 KB answer = YES
37 Correct 2 ms 9048 KB answer = YES
38 Correct 3 ms 9052 KB answer = YES
39 Correct 2 ms 9204 KB answer = YES
40 Correct 2 ms 9308 KB answer = YES
41 Correct 2 ms 9308 KB answer = NO
42 Correct 3 ms 9144 KB answer = YES
43 Correct 3 ms 9284 KB answer = YES
44 Correct 3 ms 9196 KB answer = YES
45 Correct 3 ms 9052 KB answer = YES
46 Correct 2 ms 9052 KB answer = YES
47 Correct 3 ms 9304 KB answer = YES
48 Correct 3 ms 9308 KB answer = YES
49 Correct 11 ms 10076 KB answer = YES
50 Correct 11 ms 10732 KB answer = YES
51 Correct 11 ms 10844 KB answer = YES
52 Correct 6 ms 10844 KB answer = NO
53 Correct 3 ms 9560 KB answer = YES
54 Correct 5 ms 9308 KB answer = YES
55 Correct 8 ms 9740 KB answer = YES
56 Correct 10 ms 10108 KB answer = YES
57 Correct 9 ms 10076 KB answer = YES
58 Correct 9 ms 10148 KB answer = YES
59 Correct 12 ms 9820 KB answer = YES
60 Correct 10 ms 10260 KB answer = YES
61 Correct 6 ms 9564 KB answer = YES
62 Correct 47 ms 24664 KB answer = NO
63 Correct 74 ms 23872 KB answer = YES
64 Correct 48 ms 23792 KB answer = NO
65 Correct 52 ms 23536 KB answer = YES
66 Correct 4 ms 9560 KB answer = YES
67 Correct 95 ms 29656 KB answer = YES
68 Correct 82 ms 29484 KB answer = YES
69 Correct 77 ms 29644 KB answer = YES
70 Correct 105 ms 36828 KB answer = YES
71 Correct 79 ms 29552 KB answer = YES
72 Correct 91 ms 19332 KB answer = YES
73 Correct 79 ms 19528 KB answer = YES
74 Correct 61 ms 21656 KB answer = YES
75 Correct 29 ms 21328 KB answer = NO
76 Correct 12 ms 12376 KB answer = YES
77 Correct 23 ms 13384 KB answer = YES
78 Correct 38 ms 14824 KB answer = YES
79 Correct 72 ms 18256 KB answer = YES
80 Correct 67 ms 21836 KB answer = YES
81 Correct 38 ms 21920 KB answer = NO
82 Correct 99 ms 28720 KB answer = YES
83 Correct 105 ms 29732 KB answer = YES
84 Correct 121 ms 29780 KB answer = YES
85 Correct 92 ms 29728 KB answer = YES
86 Correct 97 ms 29640 KB answer = YES
87 Correct 42 ms 19716 KB answer = NO
88 Correct 98 ms 23120 KB answer = YES
89 Correct 78 ms 17960 KB answer = YES
90 Correct 82 ms 17984 KB answer = YES
91 Correct 97 ms 18000 KB answer = YES
92 Correct 40 ms 15328 KB answer = YES
93 Correct 45 ms 15316 KB answer = YES
94 Correct 65 ms 29268 KB answer = NO
95 Correct 31 ms 15700 KB answer = NO
96 Correct 186 ms 31864 KB answer = YES
97 Correct 40 ms 29388 KB answer = NO