oj.uz

Submission #932125

# Submission time Handle Problem Language Result Execution time Memory
932125 2024-02-23T03:38:16 Z Jawad_Akbar_JJ Graph (BOI20_graph) C++17
0 / 100
 4 ms 11444 KB 
#include <iostream>
#include <vector>
#include <iomanip>

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;
int pen[100];

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 * 10 + 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;
}

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] = inf;

	for (int i=1;i<=m;i++){
		int u,v,t;
		cin>>u>>v>>t;
		l[i] = u;
		r[i] = v;
		c[i] = t;
		nei[u].push_back({v,t});
		nei[v].push_back({u,t});
	}
	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);

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

	ld lft = -1e5,rgt = k / 2.0;

	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)
			cout<<lft + a[i]<<" ";
		else
			cout<<k - lft + b[i]<<" ";
	cout<<endl;

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11356 KB answer = YES
2 Correct 3 ms 11444 KB answer = YES
3 Correct 2 ms 11356 KB answer = YES
4 Correct 2 ms 11356 KB answer = NO
5 Incorrect 2 ms 11356 KB Sum of endpoints for edge (5; 3) differs from the expected value 2.
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11356 KB answer = YES
2 Correct 3 ms 11444 KB answer = YES
3 Correct 2 ms 11356 KB answer = YES
4 Correct 2 ms 11356 KB answer = NO
5 Incorrect 2 ms 11356 KB Sum of endpoints for edge (5; 3) differs from the expected value 2.
6 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11356 KB answer = YES
2 Correct 3 ms 11444 KB answer = YES
3 Correct 2 ms 11356 KB answer = YES
4 Correct 2 ms 11356 KB answer = NO
5 Incorrect 2 ms 11356 KB Sum of endpoints for edge (5; 3) differs from the expected value 2.
6 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11356 KB answer = YES
2 Correct 3 ms 11444 KB answer = YES
3 Correct 2 ms 11356 KB answer = YES
4 Correct 2 ms 11356 KB answer = NO
5 Incorrect 2 ms 11356 KB Sum of endpoints for edge (5; 3) differs from the expected value 2.
6 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11356 KB answer = YES
2 Correct 3 ms 11444 KB answer = YES
3 Correct 2 ms 11356 KB answer = YES
4 Correct 2 ms 11356 KB answer = NO
5 Incorrect 2 ms 11356 KB Sum of endpoints for edge (5; 3) differs from the expected value 2.
6 Halted 0 ms 0 KB -