제출 #953460

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
953460		koukirocks	Graph (BOI20_graph)	C++17	0 / 100	5 ms	14940 KiB

Graph

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
 
namespace{using namespace std;}
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;

int n,m;
vector<pii> G[MAX];
struct equ {
	ldb x,c;
	equ(ldb _x,ldb _c):x(_x),c(_c){}
	equ():x(0),c(0){}
	equ operator-(const equ& a) {
		return equ(x-a.x,c-a.c);
	}
} val[MAX];
ldb ans[MAX];
bool vis[MAX];
bool flag=false;

template <class T>
bool operator==(const ldb& a,const T &b) {
	return abs(a-b)<=eps;
}

ldb solve(equ a,equ b,ldb n) {
	ldb x=a.x+b.x;
	ldb c=a.c+b.c;
	c=n-c;
	if (x==0) {
		if (c!=0) flag=true;
		return INF;
	}
	return c/x;
}

void dfs(int v,int p,ldb& pos,vector<bool>& tmpvis) {
	cout<<v<<" "<<val[v].x<<" "<<val[v].c<<"\n";
	tmpvis[v]=true;
	for (auto [i,c]:G[v]) {
		if (i==p) {
			p=-1;
			continue;
		}
		if (vis[i]) continue;
		if (tmpvis[i]) {
			ldb x=solve(val[v],val[i],c);
//			cout<<v<<" "<<i<<"\n";
//			cout<<x<<" x\n";
			if (x==INF) continue;
			if (pos==INF or pos==x) pos=x;
			else {
				flag=true;
			}
			continue;
		}
		val[i]=equ(0,c)-val[v];
		dfs(i,v,pos,tmpvis);
	}
	vis[v]=true;
	tmpvis[v]=false;
}

void dfs2(int v,ldb pos,vector<bool>& tmpvis) {
	tmpvis[v]=true;
	ans[v]=val[v].x*pos+val[v].c;
	for (auto [i,c]:G[v]) {
		if (tmpvis[i]) continue;
		dfs2(i,pos,tmpvis);
	}
	tmpvis[v]=false;
}

void dfs3(int v,vector<ldb>& allc,vector<bool>& tmpvis) {
	tmpvis[v]=true;
	allc.push_back(-1*val[v].x*val[v].c);
	for (auto [i,c]:G[v]) {
		if (tmpvis[i]) continue;
		dfs3(i,allc,tmpvis);
	}
	tmpvis[v]=false;
}

void mark(int v,vector<bool>& tmpvis) {
	tmpvis[v]=true;
	for (auto [i,c]:G[v]) {
		if (tmpvis[i]) continue;
		if (!vis[v]) continue;
		mark(i,tmpvis);
	}
	vis[v]=false;
	tmpvis[v]=false;
}

int main() {
	speed;
	cin>>n>>m;
	for (int i=0;i<m;i++) {
		int a,b,c;
		cin>>a>>b>>c;
		G[a].emplace_back(b,c);
		G[b].emplace_back(a,c);
	}
	memset(vis,0,sizeof(vis));
	vector<bool> tmpvis(n+1,0);
	for (int i=1;i<=n;i++) {
		if (vis[i]) continue;
		ldb pos=INF;
		val[i]=equ(1,0);
		dfs(i,0,pos,tmpvis);
		if (flag) {
			cout<<"NO\n";
			return 0;
		}
		if (pos==INF) {
			vector<ldb> allc;
			dfs3(i,allc,tmpvis);
			mark(i,tmpvis);
			sort(all(allc));
			pos=allc[allc.size()/2];
//			cout<<pos<<" pos\n";
		}
		dfs2(i,pos,tmpvis);
	}
	cout<<"YES\n";
	for (int i=1;i<=n;i++) {
		cout<<ans[i]<<" ";
	}
	cout<<"\n";
	return 0;
}

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