Submission #1187856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187856		tamyte	Graph (BOI20_graph)	C++20	100 / 100	176 ms	36308 KiB

Graph

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5;
using ld = long double;
vector<pair<int, ld>> adj[N + 1];
pair<ld, ld> coef[N + 1];
vector<int> now;
bool ok = true;
bool vis[N + 1];


void dfs(int v, int p, ld& x) {
	now.push_back(v);
	vis[v] = true;
	for (auto& [u, val] : adj[v]) {
		if (u == p) continue;
		if (!vis[u]) {
			coef[u].first = -coef[v].first;
			coef[u].second = val - coef[v].second;
			dfs(u, v, x);
			continue;
		}
		pair<ld, ld> current;
		current.first = -coef[v].first;
		current.second = val - coef[v].second;
		if (current.first == coef[u].first) {
			if (current.second != coef[u].second) {
				cout << "NO\n";
				exit(0);
			}
		} else {
			ld nx = (current.second - coef[u].second) / (coef[u].first - current.first);
			// cout << v << " = ";
			// cout << x << " and " << nx << endl;
			if (x != 100000000) {
				if (x != nx) {
					cout << "NO\n";
					exit(0);
				}
			}
			x = nx;
		}
		
	}
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
    	int a, b, c;
    	cin >> a >> b >> c;
    	adj[--a].push_back({--b, c});
    	adj[b].push_back({a, c});
    }
    vector<ld> res(n);
    for (int i = 0; i < n; ++i) {
    	if (!vis[i]) {
    		now.clear();
    		coef[i] = {1, 0};
    		ld x = 100000000;
    		dfs(i, -1, x);
    		if (x == 100000000) {
    			vector<ld> cof;
    			for (auto& v : now) {
    				// cout << coef[v].first << " " << coef[v].second << endl;
    				cof.push_back(-coef[v].second / coef[v].first);
    			}	
    			sort(cof.begin(), cof.end());
    			x = cof[now.size() / 2];
    		}
    		// cout << x << "\n";
    		for (auto& v : now) {
    			res[v] = x * coef[v].first + coef[v].second;
    		}
    	}
    }
    cout << "YES\n";
    for (auto& v : res) {
    	cout << v << " ";
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 24 / 24
• Subtask 4: 42 / 42
• Subtask 5: 5 / 5