Submission #308061

#	Time	Username	Problem	Language	Result	Execution time	Memory
308061		yuzhechuan	Graph (BOI20_graph)	C++14	100 / 100	157 ms	23148 KiB

Graph

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
	char c=getchar();bool f=0;x=0;
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	if(f) x=-x;return x;
}
template<class t,class ...A> inline void read(t &x,A &...a){
	read(x);read(a...);
}
template<class t> inline void write(t x){
	if(x<0) putchar('-'),write(-x);
	else{if(x>9) write(x/10);putchar('0'+x%10);}
}

#define edge pair<int,int>
#define x first
#define v second

const int N=1e5+5;
vector<edge> g[N];
int n,m,A[N],B[N];
double ans[N];
vector<double> val;
vector<int> nd,num;

void GG(){
	puts("NO");
	exit(0);
}

void dfs(int x,int a,int b){
	if(!A[x]){
		A[x]=a;
		B[x]=b;
	}
	else if(A[x]!=a||B[x]!=b){
		if(A[x]==a) GG();
		val.push_back(1.0*(b-B[x])/(A[x]-a));
		return ;
	}
	else return ;
	nd.push_back(x);
	num.push_back(a*b);
	for(edge e:g[x]) dfs(e.x,-a,e.v-b);
}

signed main(){
	read(n,m);
	for(int i=1,x,y,z;i<=m;i++){
		read(x,y,z);
		g[x].emplace_back(y,z);
		g[y].emplace_back(x,z);
	}
	for(int i=1;i<=n;i++) if(!A[i]){
		val.clear();nd.clear();num.clear();
		dfs(i,1,0);
		if(val.size()){
			if(*max_element(val.begin(),val.end())!=*min_element(val.begin(),val.end())) GG();
			for(int x:nd) ans[x]=A[x]*val[0]+B[x];
		}
		else{
			nth_element(num.begin(),num.begin()+nd.size()/2,num.end());
			int v=-num[nd.size()/2];
			for(int x:nd) ans[x]=A[x]*v+B[x];
		}
	}
	puts("YES");
	for(int i=1;i<=n;i++) printf("%.1lf ",ans[i]);
}

Compilation message (stderr)

Graph.cpp: In function 't read(t&)':
Graph.cpp:8:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    8 |  if(f) x=-x;return x;
      |  ^~
Graph.cpp:8:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    8 |  if(f) x=-x;return x;
      |             ^~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 42 / 42