oj.uz

답안 #939956

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939956 2024-03-07T02:25:54 Z pcc Graph (BOI20_graph) C++14
5 / 100
 2 ms 9304 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();
	}
	if(!check()){
		cout<<"NO\n";
		return 0;
	}
	for(int i = 1;i<=N;i++)assert(ans[i]<1e8);
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9052 KB answer = YES
2 Correct 2 ms 9052 KB answer = YES
3 Correct 2 ms 9048 KB answer = YES
4 Correct 2 ms 9148 KB answer = NO
5 Correct 2 ms 9052 KB answer = YES
6 Correct 2 ms 9048 KB answer = YES
7 Correct 2 ms 9052 KB answer = YES
8 Correct 2 ms 9304 KB answer = YES
9 Correct 2 ms 9048 KB answer = NO
10 Correct 2 ms 9048 KB answer = YES
11 Correct 2 ms 9052 KB answer = YES
12 Correct 2 ms 9052 KB answer = NO
13 Correct 2 ms 9048 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 9304 KB answer = YES
19 Correct 2 ms 9052 KB answer = YES
20 Correct 2 ms 9052 KB answer = YES
21 Correct 2 ms 9048 KB answer = YES
22 Correct 2 ms 9304 KB answer = NO
23 Correct 2 ms 9048 KB answer = NO

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9052 KB answer = YES
2 Correct 2 ms 9052 KB answer = YES
3 Correct 2 ms 9048 KB answer = YES
4 Correct 2 ms 9148 KB answer = NO
5 Correct 2 ms 9052 KB answer = YES
6 Correct 2 ms 9048 KB answer = YES
7 Correct 2 ms 9052 KB answer = YES
8 Correct 2 ms 9304 KB answer = YES
9 Correct 2 ms 9048 KB answer = NO
10 Correct 2 ms 9048 KB answer = YES
11 Correct 2 ms 9052 KB answer = YES
12 Correct 2 ms 9052 KB answer = NO
13 Correct 2 ms 9048 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 9304 KB answer = YES
19 Correct 2 ms 9052 KB answer = YES
20 Correct 2 ms 9052 KB answer = YES
21 Correct 2 ms 9048 KB answer = YES
22 Correct 2 ms 9304 KB answer = NO
23 Correct 2 ms 9048 KB answer = NO
24 Correct 2 ms 9052 KB answer = YES
25 Correct 2 ms 9052 KB answer = YES
26 Correct 2 ms 9048 KB answer = YES
27 Correct 2 ms 9052 KB answer = YES
28 Correct 2 ms 9052 KB answer = YES
29 Correct 2 ms 9048 KB answer = YES
30 Correct 2 ms 9052 KB answer = NO
31 Incorrect 2 ms 9052 KB participant answer is larger than the answer of jury
32 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9052 KB answer = YES
2 Correct 2 ms 9052 KB answer = YES
3 Correct 2 ms 9048 KB answer = YES
4 Correct 2 ms 9148 KB answer = NO
5 Correct 2 ms 9052 KB answer = YES
6 Correct 2 ms 9048 KB answer = YES
7 Correct 2 ms 9052 KB answer = YES
8 Correct 2 ms 9304 KB answer = YES
9 Correct 2 ms 9048 KB answer = NO
10 Correct 2 ms 9048 KB answer = YES
11 Correct 2 ms 9052 KB answer = YES
12 Correct 2 ms 9052 KB answer = NO
13 Correct 2 ms 9048 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 9304 KB answer = YES
19 Correct 2 ms 9052 KB answer = YES
20 Correct 2 ms 9052 KB answer = YES
21 Correct 2 ms 9048 KB answer = YES
22 Correct 2 ms 9304 KB answer = NO
23 Correct 2 ms 9048 KB answer = NO
24 Correct 2 ms 9052 KB answer = YES
25 Correct 2 ms 9052 KB answer = YES
26 Correct 2 ms 9048 KB answer = YES
27 Correct 2 ms 9052 KB answer = YES
28 Correct 2 ms 9052 KB answer = YES
29 Correct 2 ms 9048 KB answer = YES
30 Correct 2 ms 9052 KB answer = NO
31 Incorrect 2 ms 9052 KB participant answer is larger than the answer of jury
32 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9052 KB answer = YES
2 Correct 2 ms 9052 KB answer = YES
3 Correct 2 ms 9048 KB answer = YES
4 Correct 2 ms 9148 KB answer = NO
5 Correct 2 ms 9052 KB answer = YES
6 Correct 2 ms 9048 KB answer = YES
7 Correct 2 ms 9052 KB answer = YES
8 Correct 2 ms 9304 KB answer = YES
9 Correct 2 ms 9048 KB answer = NO
10 Correct 2 ms 9048 KB answer = YES
11 Correct 2 ms 9052 KB answer = YES
12 Correct 2 ms 9052 KB answer = NO
13 Correct 2 ms 9048 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 9304 KB answer = YES
19 Correct 2 ms 9052 KB answer = YES
20 Correct 2 ms 9052 KB answer = YES
21 Correct 2 ms 9048 KB answer = YES
22 Correct 2 ms 9304 KB answer = NO
23 Correct 2 ms 9048 KB answer = NO
24 Correct 2 ms 9052 KB answer = YES
25 Correct 2 ms 9052 KB answer = YES
26 Correct 2 ms 9048 KB answer = YES
27 Correct 2 ms 9052 KB answer = YES
28 Correct 2 ms 9052 KB answer = YES
29 Correct 2 ms 9048 KB answer = YES
30 Correct 2 ms 9052 KB answer = NO
31 Incorrect 2 ms 9052 KB participant answer is larger than the answer of jury
32 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9052 KB answer = YES
2 Correct 2 ms 9052 KB answer = YES
3 Correct 2 ms 9048 KB answer = YES
4 Correct 2 ms 9148 KB answer = NO
5 Correct 2 ms 9052 KB answer = YES
6 Correct 2 ms 9048 KB answer = YES
7 Correct 2 ms 9052 KB answer = YES
8 Correct 2 ms 9304 KB answer = YES
9 Correct 2 ms 9048 KB answer = NO
10 Correct 2 ms 9048 KB answer = YES
11 Correct 2 ms 9052 KB answer = YES
12 Correct 2 ms 9052 KB answer = NO
13 Correct 2 ms 9048 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 9304 KB answer = YES
19 Correct 2 ms 9052 KB answer = YES
20 Correct 2 ms 9052 KB answer = YES
21 Correct 2 ms 9048 KB answer = YES
22 Correct 2 ms 9304 KB answer = NO
23 Correct 2 ms 9048 KB answer = NO
24 Correct 2 ms 9052 KB answer = YES
25 Correct 2 ms 9052 KB answer = YES
26 Correct 2 ms 9048 KB answer = YES
27 Correct 2 ms 9052 KB answer = YES
28 Correct 2 ms 9052 KB answer = YES
29 Correct 2 ms 9048 KB answer = YES
30 Correct 2 ms 9052 KB answer = NO
31 Incorrect 2 ms 9052 KB participant answer is larger than the answer of jury
32 Halted 0 ms 0 KB -