Submission #286130

#	Time	Username	Problem	Language	Result	Execution time	Memory
286130		spdskatr	Graph (BOI20_graph)	C++14	100 / 100	200 ms	17008 KiB

Graph

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#define fi first
#define se second
#define eps 0.000001

using namespace std;
typedef pair<int, int> pii;
int N, M, seen[100005], fac[100005], con[100005];
double val[100005];
vector<pii> graph[100005];
vector<int> nds, elems;
int founda = 0, rip = 0;
double aval = 0;

void ripexit() {
	printf("NO\n");
	exit(0);
}

void dfs(int x) {
	//printf("%d: x%d c%d\n", x, fac[x], con[x]);
	nds.push_back(x);
	seen[x] = 1;
	for (pii p : graph[x]) {
		int v = p.fi, k = p.se;
		if (seen[v]) {
			if (fac[v] + fac[x]) {
				// A value is determined.
				double pval = (k - (con[v] + con[x]))/((double)(fac[v] + fac[x]));
				if (founda) { 
					if (fabs(pval - aval) > eps) {
						rip = 1;
					}
				} else {
					founda = 1;
					aval = pval;
				}
			} else {
				if (con[v] + con[x] != k) {
					rip = 1;
				}
			}
		} else {
			fac[v] = -fac[x];
			con[v] = k - con[x];
			dfs(v);
		}
	}
}

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		graph[a].push_back({ b, c });
		graph[b].push_back({ a, c });
	}
	for (int i = 1; i <= N; i++) {
		if (!seen[i]) {
			founda = 0, rip = 0;
			fac[i] = 1;
			con[i] = 0;
			dfs(i);
			if (rip) {
				ripexit();
			}
			if (!founda) {
				elems.clear();
				for (int x : nds) {
					elems.push_back(con[x] * fac[x]);
				}
				sort(elems.begin(), elems.end());
				aval = -elems[elems.size()/2];
			}
			for (int x : nds) {
				val[x] = fac[x] * aval + con[x];
			}
			nds.clear();
		}
	}
	printf("YES\n");
	for (int i = 1; i <= N; i++) {
		if (i == 1) printf("%lf", val[i]);
		else printf(" %lf", val[i]);
	} printf("\n");
}

Compilation message (stderr)

Graph.cpp: In function 'int main()':
Graph.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |  scanf("%d %d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~~
Graph.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |   scanf("%d %d %d", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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