oj.uz

Submission #953463

# Submission time Handle Problem Language Result Execution time Memory
953463 2024-03-26T02:32:35 Z koukirocks Graph (BOI20_graph) C++17
100 / 100
 200 ms 33108 KB 
#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;
		if (vis[i]) continue;
		dfs2(i,pos,tmpvis);
	}
	vis[v]=true;
	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;
		if (vis[i]) continue;
		dfs3(i,allc,tmpvis);
	}
	vis[v]=true;
	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);
		mark(i,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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14680 KB answer = YES
2 Correct 5 ms 14684 KB answer = YES
3 Correct 4 ms 14684 KB answer = YES
4 Correct 4 ms 14684 KB answer = NO
5 Correct 4 ms 14684 KB answer = YES
6 Correct 4 ms 14684 KB answer = YES
7 Correct 4 ms 14684 KB answer = YES
8 Correct 4 ms 14684 KB answer = YES
9 Correct 4 ms 14684 KB answer = NO
10 Correct 4 ms 14684 KB answer = YES
11 Correct 4 ms 14684 KB answer = YES
12 Correct 4 ms 14740 KB answer = NO
13 Correct 4 ms 14684 KB answer = YES
14 Correct 4 ms 14684 KB answer = YES
15 Correct 4 ms 14684 KB answer = YES
16 Correct 4 ms 14684 KB answer = YES
17 Correct 4 ms 14684 KB answer = YES
18 Correct 4 ms 14684 KB answer = YES
19 Correct 4 ms 14684 KB answer = YES
20 Correct 4 ms 14528 KB answer = YES
21 Correct 4 ms 14524 KB answer = YES
22 Correct 4 ms 14524 KB answer = NO
23 Correct 4 ms 14680 KB answer = NO

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14680 KB answer = YES
2 Correct 5 ms 14684 KB answer = YES
3 Correct 4 ms 14684 KB answer = YES
4 Correct 4 ms 14684 KB answer = NO
5 Correct 4 ms 14684 KB answer = YES
6 Correct 4 ms 14684 KB answer = YES
7 Correct 4 ms 14684 KB answer = YES
8 Correct 4 ms 14684 KB answer = YES
9 Correct 4 ms 14684 KB answer = NO
10 Correct 4 ms 14684 KB answer = YES
11 Correct 4 ms 14684 KB answer = YES
12 Correct 4 ms 14740 KB answer = NO
13 Correct 4 ms 14684 KB answer = YES
14 Correct 4 ms 14684 KB answer = YES
15 Correct 4 ms 14684 KB answer = YES
16 Correct 4 ms 14684 KB answer = YES
17 Correct 4 ms 14684 KB answer = YES
18 Correct 4 ms 14684 KB answer = YES
19 Correct 4 ms 14684 KB answer = YES
20 Correct 4 ms 14528 KB answer = YES
21 Correct 4 ms 14524 KB answer = YES
22 Correct 4 ms 14524 KB answer = NO
23 Correct 4 ms 14680 KB answer = NO
24 Correct 4 ms 14684 KB answer = YES
25 Correct 4 ms 14684 KB answer = YES
26 Correct 4 ms 14684 KB answer = YES
27 Correct 4 ms 14684 KB answer = YES
28 Correct 4 ms 14680 KB answer = YES
29 Correct 4 ms 14684 KB answer = YES
30 Correct 4 ms 14680 KB answer = NO
31 Correct 4 ms 14684 KB answer = YES
32 Correct 4 ms 14684 KB answer = YES
33 Correct 4 ms 14684 KB answer = YES
34 Correct 4 ms 14680 KB answer = YES
35 Correct 4 ms 14684 KB answer = YES
36 Correct 4 ms 14684 KB answer = YES

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14680 KB answer = YES
2 Correct 5 ms 14684 KB answer = YES
3 Correct 4 ms 14684 KB answer = YES
4 Correct 4 ms 14684 KB answer = NO
5 Correct 4 ms 14684 KB answer = YES
6 Correct 4 ms 14684 KB answer = YES
7 Correct 4 ms 14684 KB answer = YES
8 Correct 4 ms 14684 KB answer = YES
9 Correct 4 ms 14684 KB answer = NO
10 Correct 4 ms 14684 KB answer = YES
11 Correct 4 ms 14684 KB answer = YES
12 Correct 4 ms 14740 KB answer = NO
13 Correct 4 ms 14684 KB answer = YES
14 Correct 4 ms 14684 KB answer = YES
15 Correct 4 ms 14684 KB answer = YES
16 Correct 4 ms 14684 KB answer = YES
17 Correct 4 ms 14684 KB answer = YES
18 Correct 4 ms 14684 KB answer = YES
19 Correct 4 ms 14684 KB answer = YES
20 Correct 4 ms 14528 KB answer = YES
21 Correct 4 ms 14524 KB answer = YES
22 Correct 4 ms 14524 KB answer = NO
23 Correct 4 ms 14680 KB answer = NO
24 Correct 4 ms 14684 KB answer = YES
25 Correct 4 ms 14684 KB answer = YES
26 Correct 4 ms 14684 KB answer = YES
27 Correct 4 ms 14684 KB answer = YES
28 Correct 4 ms 14680 KB answer = YES
29 Correct 4 ms 14684 KB answer = YES
30 Correct 4 ms 14680 KB answer = NO
31 Correct 4 ms 14684 KB answer = YES
32 Correct 4 ms 14684 KB answer = YES
33 Correct 4 ms 14684 KB answer = YES
34 Correct 4 ms 14680 KB answer = YES
35 Correct 4 ms 14684 KB answer = YES
36 Correct 4 ms 14684 KB answer = YES
37 Correct 4 ms 14880 KB answer = YES
38 Correct 4 ms 14684 KB answer = YES
39 Correct 5 ms 14684 KB answer = YES
40 Correct 4 ms 14684 KB answer = YES
41 Correct 4 ms 14684 KB answer = NO
42 Correct 4 ms 14684 KB answer = YES
43 Correct 5 ms 14780 KB answer = YES
44 Correct 4 ms 14684 KB answer = YES
45 Correct 4 ms 14684 KB answer = YES
46 Correct 5 ms 14684 KB answer = YES
47 Correct 5 ms 14684 KB answer = YES
48 Correct 4 ms 14808 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14680 KB answer = YES
2 Correct 5 ms 14684 KB answer = YES
3 Correct 4 ms 14684 KB answer = YES
4 Correct 4 ms 14684 KB answer = NO
5 Correct 4 ms 14684 KB answer = YES
6 Correct 4 ms 14684 KB answer = YES
7 Correct 4 ms 14684 KB answer = YES
8 Correct 4 ms 14684 KB answer = YES
9 Correct 4 ms 14684 KB answer = NO
10 Correct 4 ms 14684 KB answer = YES
11 Correct 4 ms 14684 KB answer = YES
12 Correct 4 ms 14740 KB answer = NO
13 Correct 4 ms 14684 KB answer = YES
14 Correct 4 ms 14684 KB answer = YES
15 Correct 4 ms 14684 KB answer = YES
16 Correct 4 ms 14684 KB answer = YES
17 Correct 4 ms 14684 KB answer = YES
18 Correct 4 ms 14684 KB answer = YES
19 Correct 4 ms 14684 KB answer = YES
20 Correct 4 ms 14528 KB answer = YES
21 Correct 4 ms 14524 KB answer = YES
22 Correct 4 ms 14524 KB answer = NO
23 Correct 4 ms 14680 KB answer = NO
24 Correct 4 ms 14684 KB answer = YES
25 Correct 4 ms 14684 KB answer = YES
26 Correct 4 ms 14684 KB answer = YES
27 Correct 4 ms 14684 KB answer = YES
28 Correct 4 ms 14680 KB answer = YES
29 Correct 4 ms 14684 KB answer = YES
30 Correct 4 ms 14680 KB answer = NO
31 Correct 4 ms 14684 KB answer = YES
32 Correct 4 ms 14684 KB answer = YES
33 Correct 4 ms 14684 KB answer = YES
34 Correct 4 ms 14680 KB answer = YES
35 Correct 4 ms 14684 KB answer = YES
36 Correct 4 ms 14684 KB answer = YES
37 Correct 4 ms 14880 KB answer = YES
38 Correct 4 ms 14684 KB answer = YES
39 Correct 5 ms 14684 KB answer = YES
40 Correct 4 ms 14684 KB answer = YES
41 Correct 4 ms 14684 KB answer = NO
42 Correct 4 ms 14684 KB answer = YES
43 Correct 5 ms 14780 KB answer = YES
44 Correct 4 ms 14684 KB answer = YES
45 Correct 4 ms 14684 KB answer = YES
46 Correct 5 ms 14684 KB answer = YES
47 Correct 5 ms 14684 KB answer = YES
48 Correct 4 ms 14808 KB answer = YES
49 Correct 11 ms 15448 KB answer = YES
50 Correct 10 ms 15700 KB answer = YES
51 Correct 13 ms 16188 KB answer = YES
52 Correct 7 ms 15448 KB answer = NO
53 Correct 5 ms 14684 KB answer = YES
54 Correct 6 ms 14964 KB answer = YES
55 Correct 8 ms 15196 KB answer = YES
56 Correct 11 ms 15452 KB answer = YES
57 Correct 11 ms 15196 KB answer = YES
58 Correct 10 ms 15192 KB answer = YES
59 Correct 10 ms 15196 KB answer = YES
60 Correct 11 ms 15452 KB answer = YES
61 Correct 7 ms 14936 KB answer = YES
62 Correct 88 ms 22352 KB answer = NO
63 Correct 93 ms 22352 KB answer = YES
64 Correct 89 ms 22360 KB answer = NO
65 Correct 93 ms 22392 KB answer = YES
66 Correct 5 ms 14684 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14680 KB answer = YES
2 Correct 5 ms 14684 KB answer = YES
3 Correct 4 ms 14684 KB answer = YES
4 Correct 4 ms 14684 KB answer = NO
5 Correct 4 ms 14684 KB answer = YES
6 Correct 4 ms 14684 KB answer = YES
7 Correct 4 ms 14684 KB answer = YES
8 Correct 4 ms 14684 KB answer = YES
9 Correct 4 ms 14684 KB answer = NO
10 Correct 4 ms 14684 KB answer = YES
11 Correct 4 ms 14684 KB answer = YES
12 Correct 4 ms 14740 KB answer = NO
13 Correct 4 ms 14684 KB answer = YES
14 Correct 4 ms 14684 KB answer = YES
15 Correct 4 ms 14684 KB answer = YES
16 Correct 4 ms 14684 KB answer = YES
17 Correct 4 ms 14684 KB answer = YES
18 Correct 4 ms 14684 KB answer = YES
19 Correct 4 ms 14684 KB answer = YES
20 Correct 4 ms 14528 KB answer = YES
21 Correct 4 ms 14524 KB answer = YES
22 Correct 4 ms 14524 KB answer = NO
23 Correct 4 ms 14680 KB answer = NO
24 Correct 4 ms 14684 KB answer = YES
25 Correct 4 ms 14684 KB answer = YES
26 Correct 4 ms 14684 KB answer = YES
27 Correct 4 ms 14684 KB answer = YES
28 Correct 4 ms 14680 KB answer = YES
29 Correct 4 ms 14684 KB answer = YES
30 Correct 4 ms 14680 KB answer = NO
31 Correct 4 ms 14684 KB answer = YES
32 Correct 4 ms 14684 KB answer = YES
33 Correct 4 ms 14684 KB answer = YES
34 Correct 4 ms 14680 KB answer = YES
35 Correct 4 ms 14684 KB answer = YES
36 Correct 4 ms 14684 KB answer = YES
37 Correct 4 ms 14880 KB answer = YES
38 Correct 4 ms 14684 KB answer = YES
39 Correct 5 ms 14684 KB answer = YES
40 Correct 4 ms 14684 KB answer = YES
41 Correct 4 ms 14684 KB answer = NO
42 Correct 4 ms 14684 KB answer = YES
43 Correct 5 ms 14780 KB answer = YES
44 Correct 4 ms 14684 KB answer = YES
45 Correct 4 ms 14684 KB answer = YES
46 Correct 5 ms 14684 KB answer = YES
47 Correct 5 ms 14684 KB answer = YES
48 Correct 4 ms 14808 KB answer = YES
49 Correct 11 ms 15448 KB answer = YES
50 Correct 10 ms 15700 KB answer = YES
51 Correct 13 ms 16188 KB answer = YES
52 Correct 7 ms 15448 KB answer = NO
53 Correct 5 ms 14684 KB answer = YES
54 Correct 6 ms 14964 KB answer = YES
55 Correct 8 ms 15196 KB answer = YES
56 Correct 11 ms 15452 KB answer = YES
57 Correct 11 ms 15196 KB answer = YES
58 Correct 10 ms 15192 KB answer = YES
59 Correct 10 ms 15196 KB answer = YES
60 Correct 11 ms 15452 KB answer = YES
61 Correct 7 ms 14936 KB answer = YES
62 Correct 88 ms 22352 KB answer = NO
63 Correct 93 ms 22352 KB answer = YES
64 Correct 89 ms 22360 KB answer = NO
65 Correct 93 ms 22392 KB answer = YES
66 Correct 5 ms 14684 KB answer = YES
67 Correct 82 ms 31824 KB answer = YES
68 Correct 76 ms 31684 KB answer = YES
69 Correct 69 ms 28752 KB answer = YES
70 Correct 98 ms 33108 KB answer = YES
71 Correct 88 ms 29000 KB answer = YES
72 Correct 85 ms 21868 KB answer = YES
73 Correct 72 ms 20052 KB answer = YES
74 Correct 51 ms 22612 KB answer = YES
75 Correct 30 ms 22364 KB answer = NO
76 Correct 13 ms 15704 KB answer = YES
77 Correct 22 ms 16604 KB answer = YES
78 Correct 37 ms 17880 KB answer = YES
79 Correct 71 ms 21164 KB answer = YES
80 Correct 59 ms 24272 KB answer = YES
81 Correct 43 ms 23984 KB answer = NO
82 Correct 85 ms 28244 KB answer = YES
83 Correct 95 ms 28804 KB answer = YES
84 Correct 200 ms 31772 KB answer = YES
85 Correct 92 ms 31680 KB answer = YES
86 Correct 72 ms 28780 KB answer = YES
87 Correct 36 ms 21840 KB answer = NO
88 Correct 117 ms 23700 KB answer = YES
89 Correct 78 ms 19392 KB answer = YES
90 Correct 77 ms 19328 KB answer = YES
91 Correct 85 ms 19384 KB answer = YES
92 Correct 40 ms 17444 KB answer = YES
93 Correct 38 ms 17340 KB answer = YES
94 Correct 54 ms 28604 KB answer = NO
95 Correct 31 ms 19024 KB answer = NO
96 Correct 162 ms 29508 KB answer = YES
97 Correct 36 ms 28516 KB answer = NO