oj.uz

답안 #467331

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
467331 2021-08-22T16:19:30 Z MVP_Harry Graph (BOI20_graph) C++17
0 / 100
 2 ms 2636 KB 
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define rep(i, m, n) for (int i = m; i <= n; i++)
#define per(i, m, n) for (int i = m; i >= n; i--)
#define sz(v) (int) v.size()
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second

const int maxn = 1e5 + 5;
const double eps = 1e-6;

int N, M, leader, impossible, cycle = 0;
int vis[maxn];
double a[maxn];
vector<pair<int, int> > G[maxn];
vector<int> pt;
pair<int, int> c[maxn];

void dfs1(int u, int par) {
	vis[u] = 2;
	for (auto node : G[u]) {
		int v = node.fi, x = node.se;
		if (v == par) continue;
		if (vis[v] == 2) {
			// consider c[u], c[v]
			if (c[u].se + c[v].se == 0) continue;
			cycle = 1;
			double val = (double) (x - c[u].fi - c[v].fi) / (c[u].se + c[v].se);
			if (a[leader] == INF) a[leader] = val;
			else {
				if (abs(a[leader] - val) > eps) impossible = 1;
			}
		} else {
			c[v] = mp(x - c[u].fi, -c[u].se);
			dfs1(v, u);
		}
	}
}

void dfs2(int u, int par) {
	vis[u] = 3;
	pt.push_back((-c[u].se) * c[u].fi);
	for (auto node : G[u]) {
		if (node.fi == par || vis[node.fi] == 3) continue;
		dfs2(node.fi, u);
	}
}

void dfs3(int u, int par) {
	vis[u] = 1;
	if (u != leader) a[u] = (double) c[u].fi + (double) c[u].se * a[leader];
	for (auto node : G[u]) {
		if (node.fi == par || vis[node.fi] == 1) continue;
		dfs3(node.fi, u);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> M;
	rep(i, 1, M) {
		int u, v, x;
		cin >> u >> v >> x;
		G[u].push_back(mp(v, x)), G[v].push_back(mp(u, x));
	}
	rep(i, 1, N) a[i] = INF;
	rep(i, 1, N) if (!vis[i]) {
		c[i] = mp(0, 1);
		leader = i, cycle = 0;
		dfs1(i, 0);
		if (impossible) {
			cout << "NO\n";
			return 0;
		}
		if (!cycle) {
			pt.clear();
			dfs2(i, 0);
			sort(all(pt));
			a[leader] = pt[(sz(pt) - 1) / 2];
		}
		dfs3(i, 0);
	}
	cout << "YES\n";
	rep(i, 1, N) cout << a[i] << " ";
	cout << "\n";
	return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB answer = YES
2 Correct 2 ms 2636 KB answer = YES
3 Correct 2 ms 2636 KB answer = YES
4 Incorrect 2 ms 2636 KB Sum of endpoints for edge (2; 1) differs from the expected value 1.
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB answer = YES
2 Correct 2 ms 2636 KB answer = YES
3 Correct 2 ms 2636 KB answer = YES
4 Incorrect 2 ms 2636 KB Sum of endpoints for edge (2; 1) differs from the expected value 1.
5 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB answer = YES
2 Correct 2 ms 2636 KB answer = YES
3 Correct 2 ms 2636 KB answer = YES
4 Incorrect 2 ms 2636 KB Sum of endpoints for edge (2; 1) differs from the expected value 1.
5 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB answer = YES
2 Correct 2 ms 2636 KB answer = YES
3 Correct 2 ms 2636 KB answer = YES
4 Incorrect 2 ms 2636 KB Sum of endpoints for edge (2; 1) differs from the expected value 1.
5 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB answer = YES
2 Correct 2 ms 2636 KB answer = YES
3 Correct 2 ms 2636 KB answer = YES
4 Incorrect 2 ms 2636 KB Sum of endpoints for edge (2; 1) differs from the expected value 1.
5 Halted 0 ms 0 KB -