Submission #1260488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260488		jerzyk	Graph (BOI20_graph)	C++20	100 / 100	107 ms	28868 KiB

Graph

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef long double ld;

#define st first
#define nd second
#define f(a, c, b) for (int a = c; b > a; a++)
#define pb push_back
#define all(a) a.begin(), a.end()
#define wczytaj(a, c, n) a.resize(n); f(i, c, n) cin >> a[i];
#define sz(a) int(a.size())
#define wypisz(a, c) f(i, c, sz(a)) cout << a[i] << " "; cout << "\n";

const ll BRAK = -21372137;
const ll MNOZ = 1000000;

int n, m;

vector<ld> odp;
vector<vector<pair<ll, ll>>> sasiedzi;
vector<ll> odw; //do dfs ktory bedzie sprawdzac poprawnosc
vector<pair<ld, ll>> zmienne; //wartosci pod dfsie ze zmienna - kazda spojna rozwazamy osobno no i fajnie
vector<ll> aktl_spojna;
bool dziala = true;
ld kand;
ld jakie_x;
ld c;
ld suma_stale;
ld suma_x;

vector<ld> wspolczynniki;

void dfs(int v) {
	if (!dziala) return;
	odw[v] = 1;
	aktl_spojna.pb(v);
	for (pair<ll, ll> sasd: sasiedzi[v]) {
		if (!odw[sasd.st]) { //jesli jest nieodwiedzony to ustalam go na podstawie starego i jest fajnie
			zmienne[sasd.st] = {sasd.nd - zmienne[v].st,-zmienne[v].nd};
			dfs(sasd.st);
		} else { //trzeba sprawdzic czy sie zgadza
			if (zmienne[sasd.st].nd == zmienne[v].nd) {
				suma_x = zmienne[sasd.st].nd + zmienne[v].nd;
				suma_stale = zmienne[sasd.st].st + zmienne[v].st;
				c = (sasd.nd) - suma_stale;
				kand = ld(c)/ld(suma_x);
				if (jakie_x == BRAK) {
					jakie_x = kand;
				} else if (jakie_x != kand) {
					dziala = false;
					return;
				}
			} else {
				if (int(zmienne[sasd.st].st + zmienne[v].st) != sasd.nd) {
					dziala = false;
					return;
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	
	odp.resize(n + 1, BRAK);
	
	int w1, w2, w3;
	sasiedzi.resize(n + 1);
	
	f(i, 0, m) {
		cin >> w1 >> w2 >> w3;
		sasiedzi[w1].pb({w2, w3 * MNOZ});
		sasiedzi[w2].pb({w1, w3 * MNOZ});
	}
	
	odw.resize(n + 1, 0);
	zmienne.resize(n + 1);
	f(i, 1, n + 1) {
		if (odw[i]) continue;
		aktl_spojna.clear();
		zmienne[i] = {0, 1};
		jakie_x = BRAK;
		dfs(i);
		if (!dziala) {
			cout << "NO";
			return 0;
		}
		if (jakie_x != BRAK) {
			for (int ele: aktl_spojna) {
				odp[ele] = ld(zmienne[ele].st) + jakie_x * ld(zmienne[ele].nd);
			}
		} else {
			wspolczynniki.clear();
			for (int ele: aktl_spojna) {
				if (zmienne[ele].nd == -1) {
					wspolczynniki.pb(-zmienne[ele].st);
				} else {
					wspolczynniki.pb(zmienne[ele].st);
				}
			}
			sort(all(wspolczynniki));
			if (sz(wspolczynniki)%2 == 1) {
				jakie_x = -(wspolczynniki[sz(wspolczynniki)/2]);
			} else {
				jakie_x = -((wspolczynniki[sz(wspolczynniki)/2] + wspolczynniki[(sz(wspolczynniki)/2) - 1])/2);
			}
			for (int ele: aktl_spojna) {
				odp[ele] = ld(zmienne[ele].st) + jakie_x * ld(zmienne[ele].nd);
			}
		}
	}
	
	cout << "YES\n";
	f(i, 1, n + 1) {
		cout << fixed << setprecision(6) << (odp[i]/ld(MNOZ)) << " ";
	}
	
	return 0;
}

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