Submission #939958

#	Time	Username	Problem	Language	Result	Execution time	Memory
939958		pcc	Graph (BOI20_graph)	C++14	100 / 100	186 ms	36828 KiB

Graph

#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 (stderr)

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 / 5
• Subtask 2: 12 / 12
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 42 / 42