oj.uz

Submission #286130

# Submission time Handle Problem Language Result Execution time Memory
286130 2020-08-30T07:09:34 Z spdskatr Graph (BOI20_graph) C++14
100 / 100
 200 ms 17008 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB answer = YES
2 Correct 2 ms 2688 KB answer = YES
3 Correct 2 ms 2688 KB answer = YES
4 Correct 2 ms 2688 KB answer = NO
5 Correct 2 ms 2688 KB answer = YES
6 Correct 2 ms 2688 KB answer = YES
7 Correct 2 ms 2688 KB answer = YES
8 Correct 2 ms 2688 KB answer = YES
9 Correct 2 ms 2688 KB answer = NO
10 Correct 2 ms 2688 KB answer = YES
11 Correct 2 ms 2688 KB answer = YES
12 Correct 2 ms 2688 KB answer = NO
13 Correct 2 ms 2688 KB answer = YES
14 Correct 2 ms 2688 KB answer = YES
15 Correct 2 ms 2688 KB answer = YES
16 Correct 2 ms 2688 KB answer = YES
17 Correct 2 ms 2688 KB answer = YES
18 Correct 2 ms 2688 KB answer = YES
19 Correct 2 ms 2688 KB answer = YES
20 Correct 2 ms 2688 KB answer = YES
21 Correct 2 ms 2688 KB answer = YES
22 Correct 2 ms 2688 KB answer = NO
23 Correct 2 ms 2688 KB answer = NO

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB answer = YES
2 Correct 2 ms 2688 KB answer = YES
3 Correct 2 ms 2688 KB answer = YES
4 Correct 2 ms 2688 KB answer = NO
5 Correct 2 ms 2688 KB answer = YES
6 Correct 2 ms 2688 KB answer = YES
7 Correct 2 ms 2688 KB answer = YES
8 Correct 2 ms 2688 KB answer = YES
9 Correct 2 ms 2688 KB answer = NO
10 Correct 2 ms 2688 KB answer = YES
11 Correct 2 ms 2688 KB answer = YES
12 Correct 2 ms 2688 KB answer = NO
13 Correct 2 ms 2688 KB answer = YES
14 Correct 2 ms 2688 KB answer = YES
15 Correct 2 ms 2688 KB answer = YES
16 Correct 2 ms 2688 KB answer = YES
17 Correct 2 ms 2688 KB answer = YES
18 Correct 2 ms 2688 KB answer = YES
19 Correct 2 ms 2688 KB answer = YES
20 Correct 2 ms 2688 KB answer = YES
21 Correct 2 ms 2688 KB answer = YES
22 Correct 2 ms 2688 KB answer = NO
23 Correct 2 ms 2688 KB answer = NO
24 Correct 2 ms 2688 KB answer = YES
25 Correct 2 ms 2688 KB answer = YES
26 Correct 2 ms 2688 KB answer = YES
27 Correct 2 ms 2688 KB answer = YES
28 Correct 2 ms 2688 KB answer = YES
29 Correct 2 ms 2688 KB answer = YES
30 Correct 2 ms 2688 KB answer = NO
31 Correct 2 ms 2688 KB answer = YES
32 Correct 2 ms 2688 KB answer = YES
33 Correct 2 ms 2688 KB answer = YES
34 Correct 2 ms 2688 KB answer = YES
35 Correct 2 ms 2688 KB answer = YES
36 Correct 2 ms 2688 KB answer = YES

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB answer = YES
2 Correct 2 ms 2688 KB answer = YES
3 Correct 2 ms 2688 KB answer = YES
4 Correct 2 ms 2688 KB answer = NO
5 Correct 2 ms 2688 KB answer = YES
6 Correct 2 ms 2688 KB answer = YES
7 Correct 2 ms 2688 KB answer = YES
8 Correct 2 ms 2688 KB answer = YES
9 Correct 2 ms 2688 KB answer = NO
10 Correct 2 ms 2688 KB answer = YES
11 Correct 2 ms 2688 KB answer = YES
12 Correct 2 ms 2688 KB answer = NO
13 Correct 2 ms 2688 KB answer = YES
14 Correct 2 ms 2688 KB answer = YES
15 Correct 2 ms 2688 KB answer = YES
16 Correct 2 ms 2688 KB answer = YES
17 Correct 2 ms 2688 KB answer = YES
18 Correct 2 ms 2688 KB answer = YES
19 Correct 2 ms 2688 KB answer = YES
20 Correct 2 ms 2688 KB answer = YES
21 Correct 2 ms 2688 KB answer = YES
22 Correct 2 ms 2688 KB answer = NO
23 Correct 2 ms 2688 KB answer = NO
24 Correct 2 ms 2688 KB answer = YES
25 Correct 2 ms 2688 KB answer = YES
26 Correct 2 ms 2688 KB answer = YES
27 Correct 2 ms 2688 KB answer = YES
28 Correct 2 ms 2688 KB answer = YES
29 Correct 2 ms 2688 KB answer = YES
30 Correct 2 ms 2688 KB answer = NO
31 Correct 2 ms 2688 KB answer = YES
32 Correct 2 ms 2688 KB answer = YES
33 Correct 2 ms 2688 KB answer = YES
34 Correct 2 ms 2688 KB answer = YES
35 Correct 2 ms 2688 KB answer = YES
36 Correct 2 ms 2688 KB answer = YES
37 Correct 2 ms 2688 KB answer = YES
38 Correct 2 ms 2688 KB answer = YES
39 Correct 2 ms 2688 KB answer = YES
40 Correct 2 ms 2688 KB answer = YES
41 Correct 2 ms 2688 KB answer = NO
42 Correct 3 ms 2688 KB answer = YES
43 Correct 3 ms 2688 KB answer = YES
44 Correct 3 ms 2688 KB answer = YES
45 Correct 3 ms 2688 KB answer = YES
46 Correct 2 ms 2688 KB answer = YES
47 Correct 3 ms 2688 KB answer = YES
48 Correct 3 ms 2688 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB answer = YES
2 Correct 2 ms 2688 KB answer = YES
3 Correct 2 ms 2688 KB answer = YES
4 Correct 2 ms 2688 KB answer = NO
5 Correct 2 ms 2688 KB answer = YES
6 Correct 2 ms 2688 KB answer = YES
7 Correct 2 ms 2688 KB answer = YES
8 Correct 2 ms 2688 KB answer = YES
9 Correct 2 ms 2688 KB answer = NO
10 Correct 2 ms 2688 KB answer = YES
11 Correct 2 ms 2688 KB answer = YES
12 Correct 2 ms 2688 KB answer = NO
13 Correct 2 ms 2688 KB answer = YES
14 Correct 2 ms 2688 KB answer = YES
15 Correct 2 ms 2688 KB answer = YES
16 Correct 2 ms 2688 KB answer = YES
17 Correct 2 ms 2688 KB answer = YES
18 Correct 2 ms 2688 KB answer = YES
19 Correct 2 ms 2688 KB answer = YES
20 Correct 2 ms 2688 KB answer = YES
21 Correct 2 ms 2688 KB answer = YES
22 Correct 2 ms 2688 KB answer = NO
23 Correct 2 ms 2688 KB answer = NO
24 Correct 2 ms 2688 KB answer = YES
25 Correct 2 ms 2688 KB answer = YES
26 Correct 2 ms 2688 KB answer = YES
27 Correct 2 ms 2688 KB answer = YES
28 Correct 2 ms 2688 KB answer = YES
29 Correct 2 ms 2688 KB answer = YES
30 Correct 2 ms 2688 KB answer = NO
31 Correct 2 ms 2688 KB answer = YES
32 Correct 2 ms 2688 KB answer = YES
33 Correct 2 ms 2688 KB answer = YES
34 Correct 2 ms 2688 KB answer = YES
35 Correct 2 ms 2688 KB answer = YES
36 Correct 2 ms 2688 KB answer = YES
37 Correct 2 ms 2688 KB answer = YES
38 Correct 2 ms 2688 KB answer = YES
39 Correct 2 ms 2688 KB answer = YES
40 Correct 2 ms 2688 KB answer = YES
41 Correct 2 ms 2688 KB answer = NO
42 Correct 3 ms 2688 KB answer = YES
43 Correct 3 ms 2688 KB answer = YES
44 Correct 3 ms 2688 KB answer = YES
45 Correct 3 ms 2688 KB answer = YES
46 Correct 2 ms 2688 KB answer = YES
47 Correct 3 ms 2688 KB answer = YES
48 Correct 3 ms 2688 KB answer = YES
49 Correct 10 ms 3456 KB answer = YES
50 Correct 11 ms 3584 KB answer = YES
51 Correct 11 ms 3712 KB answer = YES
52 Correct 7 ms 3456 KB answer = NO
53 Correct 3 ms 2688 KB answer = YES
54 Correct 4 ms 2816 KB answer = YES
55 Correct 6 ms 3072 KB answer = YES
56 Correct 10 ms 3456 KB answer = YES
57 Correct 10 ms 3328 KB answer = YES
58 Correct 9 ms 3328 KB answer = YES
59 Correct 12 ms 3328 KB answer = YES
60 Correct 10 ms 3456 KB answer = YES
61 Correct 6 ms 3072 KB answer = YES
62 Correct 88 ms 7800 KB answer = NO
63 Correct 90 ms 7928 KB answer = YES
64 Correct 90 ms 7764 KB answer = NO
65 Correct 93 ms 7924 KB answer = YES
66 Correct 3 ms 2816 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB answer = YES
2 Correct 2 ms 2688 KB answer = YES
3 Correct 2 ms 2688 KB answer = YES
4 Correct 2 ms 2688 KB answer = NO
5 Correct 2 ms 2688 KB answer = YES
6 Correct 2 ms 2688 KB answer = YES
7 Correct 2 ms 2688 KB answer = YES
8 Correct 2 ms 2688 KB answer = YES
9 Correct 2 ms 2688 KB answer = NO
10 Correct 2 ms 2688 KB answer = YES
11 Correct 2 ms 2688 KB answer = YES
12 Correct 2 ms 2688 KB answer = NO
13 Correct 2 ms 2688 KB answer = YES
14 Correct 2 ms 2688 KB answer = YES
15 Correct 2 ms 2688 KB answer = YES
16 Correct 2 ms 2688 KB answer = YES
17 Correct 2 ms 2688 KB answer = YES
18 Correct 2 ms 2688 KB answer = YES
19 Correct 2 ms 2688 KB answer = YES
20 Correct 2 ms 2688 KB answer = YES
21 Correct 2 ms 2688 KB answer = YES
22 Correct 2 ms 2688 KB answer = NO
23 Correct 2 ms 2688 KB answer = NO
24 Correct 2 ms 2688 KB answer = YES
25 Correct 2 ms 2688 KB answer = YES
26 Correct 2 ms 2688 KB answer = YES
27 Correct 2 ms 2688 KB answer = YES
28 Correct 2 ms 2688 KB answer = YES
29 Correct 2 ms 2688 KB answer = YES
30 Correct 2 ms 2688 KB answer = NO
31 Correct 2 ms 2688 KB answer = YES
32 Correct 2 ms 2688 KB answer = YES
33 Correct 2 ms 2688 KB answer = YES
34 Correct 2 ms 2688 KB answer = YES
35 Correct 2 ms 2688 KB answer = YES
36 Correct 2 ms 2688 KB answer = YES
37 Correct 2 ms 2688 KB answer = YES
38 Correct 2 ms 2688 KB answer = YES
39 Correct 2 ms 2688 KB answer = YES
40 Correct 2 ms 2688 KB answer = YES
41 Correct 2 ms 2688 KB answer = NO
42 Correct 3 ms 2688 KB answer = YES
43 Correct 3 ms 2688 KB answer = YES
44 Correct 3 ms 2688 KB answer = YES
45 Correct 3 ms 2688 KB answer = YES
46 Correct 2 ms 2688 KB answer = YES
47 Correct 3 ms 2688 KB answer = YES
48 Correct 3 ms 2688 KB answer = YES
49 Correct 10 ms 3456 KB answer = YES
50 Correct 11 ms 3584 KB answer = YES
51 Correct 11 ms 3712 KB answer = YES
52 Correct 7 ms 3456 KB answer = NO
53 Correct 3 ms 2688 KB answer = YES
54 Correct 4 ms 2816 KB answer = YES
55 Correct 6 ms 3072 KB answer = YES
56 Correct 10 ms 3456 KB answer = YES
57 Correct 10 ms 3328 KB answer = YES
58 Correct 9 ms 3328 KB answer = YES
59 Correct 12 ms 3328 KB answer = YES
60 Correct 10 ms 3456 KB answer = YES
61 Correct 6 ms 3072 KB answer = YES
62 Correct 88 ms 7800 KB answer = NO
63 Correct 90 ms 7928 KB answer = YES
64 Correct 90 ms 7764 KB answer = NO
65 Correct 93 ms 7924 KB answer = YES
66 Correct 3 ms 2816 KB answer = YES
67 Correct 96 ms 14324 KB answer = YES
68 Correct 82 ms 14196 KB answer = YES
69 Correct 79 ms 13812 KB answer = YES
70 Correct 129 ms 17008 KB answer = YES
71 Correct 84 ms 13936 KB answer = YES
72 Correct 106 ms 10216 KB answer = YES
73 Correct 106 ms 9836 KB answer = YES
74 Correct 68 ms 9592 KB answer = YES
75 Correct 40 ms 8312 KB answer = NO
76 Correct 12 ms 3584 KB answer = YES
77 Correct 24 ms 4608 KB answer = YES
78 Correct 41 ms 6004 KB answer = YES
79 Correct 92 ms 9400 KB answer = YES
80 Correct 68 ms 9716 KB answer = YES
81 Correct 63 ms 9972 KB answer = NO
82 Correct 106 ms 13556 KB answer = YES
83 Correct 124 ms 14068 KB answer = YES
84 Correct 131 ms 14324 KB answer = YES
85 Correct 92 ms 14452 KB answer = YES
86 Correct 90 ms 13940 KB answer = YES
87 Correct 72 ms 9336 KB answer = NO
88 Correct 123 ms 11132 KB answer = YES
89 Correct 95 ms 8728 KB answer = YES
90 Correct 119 ms 8696 KB answer = YES
91 Correct 109 ms 8696 KB answer = YES
92 Correct 48 ms 6260 KB answer = YES
93 Correct 49 ms 6260 KB answer = YES
94 Correct 84 ms 12148 KB answer = NO
95 Correct 65 ms 7672 KB answer = NO
96 Correct 200 ms 15140 KB answer = YES
97 Correct 51 ms 12148 KB answer = NO