oj.uz

Submission #953462

# Submission time Handle Problem Language Result Execution time Memory
953462 2024-03-26T02:31:04 Z koukirocks Graph (BOI20_graph) C++17
5 / 100
 700 ms 14936 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;
		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);
		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 4 ms 14680 KB answer = YES
2 Correct 4 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 14684 KB answer = NO
13 Correct 4 ms 14684 KB answer = YES
14 Correct 4 ms 14680 KB answer = YES
15 Correct 4 ms 14684 KB answer = YES
16 Correct 4 ms 14684 KB answer = YES
17 Correct 4 ms 14680 KB answer = YES
18 Correct 4 ms 14684 KB answer = YES
19 Correct 4 ms 14684 KB answer = YES
20 Correct 4 ms 14684 KB answer = YES
21 Correct 4 ms 14684 KB answer = YES
22 Correct 5 ms 14684 KB answer = NO
23 Correct 4 ms 14684 KB answer = NO

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14680 KB answer = YES
2 Correct 4 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 14684 KB answer = NO
13 Correct 4 ms 14684 KB answer = YES
14 Correct 4 ms 14680 KB answer = YES
15 Correct 4 ms 14684 KB answer = YES
16 Correct 4 ms 14684 KB answer = YES
17 Correct 4 ms 14680 KB answer = YES
18 Correct 4 ms 14684 KB answer = YES
19 Correct 4 ms 14684 KB answer = YES
20 Correct 4 ms 14684 KB answer = YES
21 Correct 4 ms 14684 KB answer = YES
22 Correct 5 ms 14684 KB answer = NO
23 Correct 4 ms 14684 KB answer = NO
24 Correct 5 ms 14936 KB answer = YES
25 Correct 5 ms 14684 KB answer = YES
26 Correct 5 ms 14684 KB answer = YES
27 Correct 4 ms 14684 KB answer = YES
28 Correct 6 ms 14684 KB answer = YES
29 Correct 5 ms 14684 KB answer = YES
30 Correct 4 ms 14684 KB answer = NO
31 Correct 4 ms 14680 KB answer = YES
32 Correct 4 ms 14684 KB answer = YES
33 Correct 4 ms 14684 KB answer = YES
34 Execution timed out 1064 ms 14684 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14680 KB answer = YES
2 Correct 4 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 14684 KB answer = NO
13 Correct 4 ms 14684 KB answer = YES
14 Correct 4 ms 14680 KB answer = YES
15 Correct 4 ms 14684 KB answer = YES
16 Correct 4 ms 14684 KB answer = YES
17 Correct 4 ms 14680 KB answer = YES
18 Correct 4 ms 14684 KB answer = YES
19 Correct 4 ms 14684 KB answer = YES
20 Correct 4 ms 14684 KB answer = YES
21 Correct 4 ms 14684 KB answer = YES
22 Correct 5 ms 14684 KB answer = NO
23 Correct 4 ms 14684 KB answer = NO
24 Correct 5 ms 14936 KB answer = YES
25 Correct 5 ms 14684 KB answer = YES
26 Correct 5 ms 14684 KB answer = YES
27 Correct 4 ms 14684 KB answer = YES
28 Correct 6 ms 14684 KB answer = YES
29 Correct 5 ms 14684 KB answer = YES
30 Correct 4 ms 14684 KB answer = NO
31 Correct 4 ms 14680 KB answer = YES
32 Correct 4 ms 14684 KB answer = YES
33 Correct 4 ms 14684 KB answer = YES
34 Execution timed out 1064 ms 14684 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14680 KB answer = YES
2 Correct 4 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 14684 KB answer = NO
13 Correct 4 ms 14684 KB answer = YES
14 Correct 4 ms 14680 KB answer = YES
15 Correct 4 ms 14684 KB answer = YES
16 Correct 4 ms 14684 KB answer = YES
17 Correct 4 ms 14680 KB answer = YES
18 Correct 4 ms 14684 KB answer = YES
19 Correct 4 ms 14684 KB answer = YES
20 Correct 4 ms 14684 KB answer = YES
21 Correct 4 ms 14684 KB answer = YES
22 Correct 5 ms 14684 KB answer = NO
23 Correct 4 ms 14684 KB answer = NO
24 Correct 5 ms 14936 KB answer = YES
25 Correct 5 ms 14684 KB answer = YES
26 Correct 5 ms 14684 KB answer = YES
27 Correct 4 ms 14684 KB answer = YES
28 Correct 6 ms 14684 KB answer = YES
29 Correct 5 ms 14684 KB answer = YES
30 Correct 4 ms 14684 KB answer = NO
31 Correct 4 ms 14680 KB answer = YES
32 Correct 4 ms 14684 KB answer = YES
33 Correct 4 ms 14684 KB answer = YES
34 Execution timed out 1064 ms 14684 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14680 KB answer = YES
2 Correct 4 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 14684 KB answer = NO
13 Correct 4 ms 14684 KB answer = YES
14 Correct 4 ms 14680 KB answer = YES
15 Correct 4 ms 14684 KB answer = YES
16 Correct 4 ms 14684 KB answer = YES
17 Correct 4 ms 14680 KB answer = YES
18 Correct 4 ms 14684 KB answer = YES
19 Correct 4 ms 14684 KB answer = YES
20 Correct 4 ms 14684 KB answer = YES
21 Correct 4 ms 14684 KB answer = YES
22 Correct 5 ms 14684 KB answer = NO
23 Correct 4 ms 14684 KB answer = NO
24 Correct 5 ms 14936 KB answer = YES
25 Correct 5 ms 14684 KB answer = YES
26 Correct 5 ms 14684 KB answer = YES
27 Correct 4 ms 14684 KB answer = YES
28 Correct 6 ms 14684 KB answer = YES
29 Correct 5 ms 14684 KB answer = YES
30 Correct 4 ms 14684 KB answer = NO
31 Correct 4 ms 14680 KB answer = YES
32 Correct 4 ms 14684 KB answer = YES
33 Correct 4 ms 14684 KB answer = YES
34 Execution timed out 1064 ms 14684 KB Time limit exceeded
35 Halted 0 ms 0 KB -