Submission #670450

#	Time	Username	Problem	Language	Result	Execution time	Memory
670450		jamezzz	Graph (BOI20_graph)	C++17	100 / 100	139 ms	27936 KiB

Graph

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

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