Submission #287845

#	Time	Username	Problem	Language	Result	Execution time	Memory
287845		nandonathaniel	Graph (BOI20_graph)	C++14	100 / 100	184 ms	14304 KiB

Graph

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=100005,INF=1e9,LOG=90;
pii nilai[MAXN];
vector<pii> adj[MAXN];
double point[MAXN];

void gagal(){
	cout << "NO\n";
	exit(0);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n,m,u,v,w;
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		cin >> u >> v >> w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}
	for(int i=1;i<=n;i++){
		nilai[i].first=INF;
		nilai[i].second=INF;
	}
	for(int i=1;i<=n;i++){
		if(nilai[i].first!=INF)continue;
		//linear equation
		vector<int> V;
		queue<int> Q;
		Q.push(i);
		nilai[i]={1,0};   //x and const
		double X=(double)INF;
		while(!Q.empty()){
			int now=Q.front();
			V.push_back(now);
			Q.pop();
			for(auto nxt : adj[now]){
				if(nilai[nxt.first]==make_pair(INF,INF)){
					nilai[nxt.first]={-nilai[now].first,nxt.second-nilai[now].second};
					Q.push(nxt.first);
				}
				else{
					if(nilai[now].first+nilai[nxt.first].first==0 && nilai[now].second+nilai[nxt.first].second!=nxt.second)gagal();
					if(nilai[now].first+nilai[nxt.first].first!=0){
						double xnow=((double)nxt.second-((double)nilai[now].second+(double)nilai[nxt.first].second))/((double)nilai[now].first+(double)nilai[nxt.first].first);
						if(X==INF)X=xnow;
						else if(xnow!=X)gagal();
					}
				}
			}
		}
		if(X!=INF){
			for(auto isi : V)point[isi]=X*(double)nilai[isi].first+(double)nilai[isi].second;
			continue;
		}
		vector<int> candidate;
		for(auto isi : V){
			if(nilai[isi].first==-1)candidate.push_back(nilai[isi].second);
			else candidate.push_back(-nilai[isi].second);
		}
		sort(candidate.begin(),candidate.end());
		//x yang membuat sigma(ax+b) terkecil adalah median dari pembuat nol semua persamaan mutlak
		X=candidate[V.size()/2];
		if(V.size()%2==0)X=(double)(X+candidate[V.size()/2-1])/2.0;
		for(auto isi : V)point[isi]=X*(double)nilai[isi].first+(double)nilai[isi].second;
	}
	cout << "YES\n";
	for(int i=1;i<=n;i++){
		cout << fixed << setprecision(6) << point[i];
		if(i<n)cout << ' ';
		else cout << '\n';
	}
	return 0;
}

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