oj.uz

답안 #932186

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
932186 2024-02-23T05:09:19 Z Jawad_Akbar_JJ Graph (BOI20_graph) C++17
0 / 100
 12 ms 24976 KB 
#include <iostream>
#include <vector>
#include <iomanip>
#include <map>

using namespace std;
#define ld long double
const int N = 2e5 + 10;
vector<pair<int,int>> nei[N];
int l[N],r[N],c[N];
ld a[N],b[N],inf = 1e9,ans[N];
int pen[100];

map<pair<int,int>,int> mp;

void dfs1(int u,int p = 0,int v = 0,int last = 0){
	if (v >= 10){
		last += pen[v];
		if (a[u] != inf){
			if (a[u] != last){
				cout<<"NO\n";
				exit(0);
			}
			return;
		}
		a[u] = last;
		v = 0;
	}
	v *= 10;
	for (auto [i,j] : nei[u]){
		if (i == p)
			continue;
		dfs1(i,u,v + j,last);
	}
}
void dfs2(int u,int p = 0,int v = 0,int last = 0){
	if (v >= 10){
		last += pen[v];
		if (b[u] != inf){
			if (b[u] != last){
				cout<<"NO\n";
				exit(0);
			}
			return;
		}
		b[u] = last;
		v = 0;
	}
	v *= 10;
	for (auto [i,j] : nei[u]){
		if (i == p)
			continue;
		dfs2(i,u,v + j,last);
	}
}
ld k;
ld calc(ld v,int n){
	ld ans = 0;
	for (int i=1;i<=n;i++){
		if (a[i] != inf)
			ans += abs(v + a[i]);
		else
			ans += abs(k - v + b[i]);
	}
	return ans;
}

void dfs3(int u){
	for (auto [i,j] : nei[u]){
		if (ans[i] != inf)
			continue;
		ans[i] = j - ans[u];
		dfs3(i);
	}
}

signed  main(){
	cout<<fixed<<setprecision(9);
	int n,m;
	cin>>n>>m;
	pen[21] = -1;
	pen[12] = +1;

	for (int i=1;i<=n;i++)
		a[i] = b[i] = ans[i] = inf;
	int cur = 1;
	for (int i=1;i<=m;i++){
		int u,v,t;
		cin>>u>>v>>t;
		if (mp[{u,v}] != 0){
			if (mp[{u,v}] == t)
				continue;
			cout<<"NO"<<endl;
			exit(0);
		}
		l[cur] = u;
		r[cur] = v;
		c[cur] = t;
		cur++;
		if (u == v)
			continue;
		nei[u].push_back({v,t});
		nei[v].push_back({u,t});
		mp[{u,v}] = mp[{v,u}] = t;
	}
	m = cur - 1;


	for (int i=1;i<=m;i++){
		if (l[i] == r[i]){
			ans[l[i]] = c[i]/2;
			dfs3(i);
			for (int j=1;j<=m;j++)
				if (ans[l[j]] + ans[r[j]] != c[j]){
					cout<<"NO"<<endl;
					exit(0);
				}
			cout<<"YES"<<endl;
			for (int i=1;i<=n;i++)
				cout<<ans[i]<<" ";
			cout<<endl;
			exit(0);
		}
	}







	a[1] = 0;
	dfs1(1);

	for (int i=1;i<=m;i++){
		if (a[l[i]] != inf and a[r[i]] != inf){
			ld A = (c[i] - a[l[i]] - a[r[i]]) / 2.0;
			cout<<"YES\n";
			for (int j=1;j<=n;j++)
				cout<<A + a[j]<<" ";
			cout<<endl;
			return 0;
		}
	}



	int r2 = nei[1][0].first;
	b[r2] = 0;

	dfs2(r2);


	for (int i=1;i<=n;i++){
		if (a[i] == inf and b[i] == inf)
			cout<<i<<endl;
	}
	// return 0;

	k = nei[1][0].second;

	ld lft = -1e5,rgt = k;

	while (rgt - lft > 0.00000001){
		ld mid = (lft + rgt)/2.0;
		ld frst = calc(mid,n);
		ld sec = calc(min(rgt,mid + 0.00000001),n);
		if (frst < sec)
			rgt = mid;
		else
			lft = mid;
		// cout<<lft<<" "<<rgt<<" "<<mid<<" "<<frst<<" "<<sec<<endl;
	}
	// cout<<calc(0,n)<<endl;
	cout<<"YES"<<endl;
	for (int i=1;i<=n;i++){
		if (a[i] == inf and b[i] == inf)
			cout<<1/0;
		if (a[i] != inf)
			cout<<lft + a[i]<<" ";
		else
			cout<<k - lft + b[i]<<" ";
	}
	cout<<endl;

}

Compilation message

Graph.cpp: In function 'int main()':
Graph.cpp:178:11: warning: division by zero [-Wdiv-by-zero]
  178 |    cout<<1/0;
      |          ~^~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12376 KB answer = YES
2 Correct 3 ms 12380 KB answer = YES
3 Correct 2 ms 12380 KB answer = YES
4 Correct 4 ms 12380 KB answer = NO
5 Runtime error 12 ms 24976 KB Execution killed with signal 4
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12376 KB answer = YES
2 Correct 3 ms 12380 KB answer = YES
3 Correct 2 ms 12380 KB answer = YES
4 Correct 4 ms 12380 KB answer = NO
5 Runtime error 12 ms 24976 KB Execution killed with signal 4
6 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12376 KB answer = YES
2 Correct 3 ms 12380 KB answer = YES
3 Correct 2 ms 12380 KB answer = YES
4 Correct 4 ms 12380 KB answer = NO
5 Runtime error 12 ms 24976 KB Execution killed with signal 4
6 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12376 KB answer = YES
2 Correct 3 ms 12380 KB answer = YES
3 Correct 2 ms 12380 KB answer = YES
4 Correct 4 ms 12380 KB answer = NO
5 Runtime error 12 ms 24976 KB Execution killed with signal 4
6 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12376 KB answer = YES
2 Correct 3 ms 12380 KB answer = YES
3 Correct 2 ms 12380 KB answer = YES
4 Correct 4 ms 12380 KB answer = NO
5 Runtime error 12 ms 24976 KB Execution killed with signal 4
6 Halted 0 ms 0 KB -