oj.uz

Submission #793176

# Submission time Handle Problem Language Result Execution time Memory
793176 2023-07-25T15:12:35 Z peijar Graph (BOI20_graph) C++17
100 / 100
 107 ms 16892 KB 
#include <iostream>
#include <fstream>
#include <cstdio>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <string>
#include <cmath>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <functional>
#include <limits>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef vector<vector<int> > graph;
 
const double pi = acos(-1.0);
 
#define oned(a, x1, x2) { cout << #a << ":"; for(int _i = (x1); _i < (x2); _i++){ cout << " " << a[_i]; } cout << endl; }
#define twod(a, x1, x2, y1, y2) { cout << #a << ":" << endl; for(int _i = (x1); _i < (x2); _i++){ for(int _j = (y1); _j < (y2); _j++){ cout << (_j > y1 ? " " : "") << a[_i][_j]; } cout << endl; } }
 
#define mp make_pair
#define pb push_back
#define fst first
#define snd second
 
const int MAXN = 200005;
 
int n, m;
vector<pii> g[MAXN];
 
int vis[MAXN];
int sgn[MAXN];
int val[MAXN];
 
queue<int> Q;
 
int ans[MAXN];
 
int cnt;
int comp[MAXN];
int num[MAXN];
 
void solve() {
	memset(vis,0,sizeof(vis));
	for(int u = 1; u <= n; u++) {
		if(!vis[u]) {
			vis[u] = true;
			sgn[u] = +1;
			val[u] = 0;
			cnt = 0;
			comp[cnt++] = u;
			bool bip = true;
			double x;
			Q.push(u);
			while(!Q.empty()) {
				int v = Q.front(); Q.pop();
				for(size_t i = 0; i < g[v].size(); i++) {
					int w = g[v][i].fst;
					int sum = g[v][i].snd;
					if(!vis[w]) {
						vis[w] = true;
						sgn[w] = -sgn[v];
						val[w] = sum-val[v];
						comp[cnt++] = w;
						Q.push(w);
					} else if(sgn[w]==sgn[v]) {
						bip = false;
						x = sgn[w]*(sum-val[w]-val[v])/2;
					}
				}
			}
			
			if(bip) {
				for(int i = 0; i < cnt; i++) {
					int v = comp[i];
					num[i] = (-sgn[v])*val[v];
				}
				sort(num,num+cnt);
				x = num[cnt/2];
			}
			
			for(int i = 0; i < cnt; i++) {
				int v = comp[i];
				ans[v] = val[v] + sgn[v]*x;
			}
			
			for(int i = 0; i < cnt; i++) {
				int v = comp[i];
				for(size_t i = 0; i < g[v].size(); i++) {
					int w = g[v][i].fst;
					if(ans[v]+ans[w]!=g[v][i].snd) {
						printf("NO\n");
						return;
					}
				}
			}
		}
	}
	
	printf("YES\n");
	for(int v = 1; v <= n; v++) {
		printf("%.1lf ", 0.5*ans[v]);
	}
	printf("\n");
}
 
int main() {
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	while(scanf("%d %d", &n, &m)==2) {
		for(int i = 1; i <= n; i++) {
			g[i].clear();
		}
		for(int i = 0; i < m; i++) {
			int a, b, c; scanf("%d %d %d", &a, &b, &c);
			c *= 2;
			g[a].pb(mp(b,c));
			g[b].pb(mp(a,c));
		}
		solve();
	}
}

Compilation message

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

Subtask #1
5.0 / 5.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
17.0 / 17.0

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

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB answer = YES
2 Correct 4 ms 5844 KB answer = YES
3 Correct 3 ms 5788 KB answer = YES
4 Correct 3 ms 5780 KB answer = NO
5 Correct 2 ms 5716 KB answer = YES
6 Correct 3 ms 5716 KB answer = YES
7 Correct 3 ms 5776 KB answer = YES
8 Correct 3 ms 5844 KB answer = YES
9 Correct 3 ms 5716 KB answer = NO
10 Correct 3 ms 5716 KB answer = YES
11 Correct 3 ms 5716 KB answer = YES
12 Correct 2 ms 5704 KB answer = NO
13 Correct 3 ms 5784 KB answer = YES
14 Correct 2 ms 5776 KB answer = YES
15 Correct 3 ms 5716 KB answer = YES
16 Correct 3 ms 5784 KB answer = YES
17 Correct 2 ms 5716 KB answer = YES
18 Correct 4 ms 5716 KB answer = YES
19 Correct 3 ms 5716 KB answer = YES
20 Correct 3 ms 5784 KB answer = YES
21 Correct 3 ms 5780 KB answer = YES
22 Correct 3 ms 5716 KB answer = NO
23 Correct 3 ms 5780 KB answer = NO
24 Correct 3 ms 5716 KB answer = YES
25 Correct 3 ms 5716 KB answer = YES
26 Correct 3 ms 5716 KB answer = YES
27 Correct 3 ms 5716 KB answer = YES
28 Correct 3 ms 5716 KB answer = YES
29 Correct 3 ms 5780 KB answer = YES
30 Correct 3 ms 5784 KB answer = NO
31 Correct 3 ms 5776 KB answer = YES
32 Correct 3 ms 5716 KB answer = YES
33 Correct 3 ms 5716 KB answer = YES
34 Correct 3 ms 5716 KB answer = YES
35 Correct 3 ms 5716 KB answer = YES
36 Correct 3 ms 5716 KB answer = YES
37 Correct 3 ms 5716 KB answer = YES
38 Correct 2 ms 5772 KB answer = YES
39 Correct 3 ms 5844 KB answer = YES
40 Correct 3 ms 5796 KB answer = YES
41 Correct 3 ms 5844 KB answer = NO
42 Correct 3 ms 5792 KB answer = YES
43 Correct 3 ms 5864 KB answer = YES
44 Correct 3 ms 5844 KB answer = YES
45 Correct 3 ms 5844 KB answer = YES
46 Correct 3 ms 5844 KB answer = YES
47 Correct 3 ms 5844 KB answer = YES
48 Correct 3 ms 5780 KB answer = YES
49 Correct 8 ms 6484 KB answer = YES
50 Correct 8 ms 6356 KB answer = YES
51 Correct 11 ms 6484 KB answer = YES
52 Correct 6 ms 6432 KB answer = NO
53 Correct 3 ms 5844 KB answer = YES
54 Correct 4 ms 5916 KB answer = YES
55 Correct 5 ms 6100 KB answer = YES
56 Correct 7 ms 6484 KB answer = YES
57 Correct 7 ms 6356 KB answer = YES
58 Correct 7 ms 6356 KB answer = YES
59 Correct 7 ms 6356 KB answer = YES
60 Correct 8 ms 6432 KB answer = YES
61 Correct 6 ms 6100 KB answer = YES
62 Correct 53 ms 12812 KB answer = NO
63 Correct 58 ms 12876 KB answer = YES
64 Correct 53 ms 12788 KB answer = NO
65 Correct 56 ms 12916 KB answer = YES
66 Correct 4 ms 5844 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB answer = YES
2 Correct 4 ms 5844 KB answer = YES
3 Correct 3 ms 5788 KB answer = YES
4 Correct 3 ms 5780 KB answer = NO
5 Correct 2 ms 5716 KB answer = YES
6 Correct 3 ms 5716 KB answer = YES
7 Correct 3 ms 5776 KB answer = YES
8 Correct 3 ms 5844 KB answer = YES
9 Correct 3 ms 5716 KB answer = NO
10 Correct 3 ms 5716 KB answer = YES
11 Correct 3 ms 5716 KB answer = YES
12 Correct 2 ms 5704 KB answer = NO
13 Correct 3 ms 5784 KB answer = YES
14 Correct 2 ms 5776 KB answer = YES
15 Correct 3 ms 5716 KB answer = YES
16 Correct 3 ms 5784 KB answer = YES
17 Correct 2 ms 5716 KB answer = YES
18 Correct 4 ms 5716 KB answer = YES
19 Correct 3 ms 5716 KB answer = YES
20 Correct 3 ms 5784 KB answer = YES
21 Correct 3 ms 5780 KB answer = YES
22 Correct 3 ms 5716 KB answer = NO
23 Correct 3 ms 5780 KB answer = NO
24 Correct 3 ms 5716 KB answer = YES
25 Correct 3 ms 5716 KB answer = YES
26 Correct 3 ms 5716 KB answer = YES
27 Correct 3 ms 5716 KB answer = YES
28 Correct 3 ms 5716 KB answer = YES
29 Correct 3 ms 5780 KB answer = YES
30 Correct 3 ms 5784 KB answer = NO
31 Correct 3 ms 5776 KB answer = YES
32 Correct 3 ms 5716 KB answer = YES
33 Correct 3 ms 5716 KB answer = YES
34 Correct 3 ms 5716 KB answer = YES
35 Correct 3 ms 5716 KB answer = YES
36 Correct 3 ms 5716 KB answer = YES
37 Correct 3 ms 5716 KB answer = YES
38 Correct 2 ms 5772 KB answer = YES
39 Correct 3 ms 5844 KB answer = YES
40 Correct 3 ms 5796 KB answer = YES
41 Correct 3 ms 5844 KB answer = NO
42 Correct 3 ms 5792 KB answer = YES
43 Correct 3 ms 5864 KB answer = YES
44 Correct 3 ms 5844 KB answer = YES
45 Correct 3 ms 5844 KB answer = YES
46 Correct 3 ms 5844 KB answer = YES
47 Correct 3 ms 5844 KB answer = YES
48 Correct 3 ms 5780 KB answer = YES
49 Correct 8 ms 6484 KB answer = YES
50 Correct 8 ms 6356 KB answer = YES
51 Correct 11 ms 6484 KB answer = YES
52 Correct 6 ms 6432 KB answer = NO
53 Correct 3 ms 5844 KB answer = YES
54 Correct 4 ms 5916 KB answer = YES
55 Correct 5 ms 6100 KB answer = YES
56 Correct 7 ms 6484 KB answer = YES
57 Correct 7 ms 6356 KB answer = YES
58 Correct 7 ms 6356 KB answer = YES
59 Correct 7 ms 6356 KB answer = YES
60 Correct 8 ms 6432 KB answer = YES
61 Correct 6 ms 6100 KB answer = YES
62 Correct 53 ms 12812 KB answer = NO
63 Correct 58 ms 12876 KB answer = YES
64 Correct 53 ms 12788 KB answer = NO
65 Correct 56 ms 12916 KB answer = YES
66 Correct 4 ms 5844 KB answer = YES
67 Correct 57 ms 12724 KB answer = YES
68 Correct 51 ms 12512 KB answer = YES
69 Correct 47 ms 12240 KB answer = YES
70 Correct 75 ms 16712 KB answer = YES
71 Correct 49 ms 12188 KB answer = YES
72 Correct 56 ms 13256 KB answer = YES
73 Correct 51 ms 12884 KB answer = YES
74 Correct 50 ms 10060 KB answer = YES
75 Correct 24 ms 10000 KB answer = NO
76 Correct 9 ms 6612 KB answer = YES
77 Correct 15 ms 7636 KB answer = YES
78 Correct 29 ms 9120 KB answer = YES
79 Correct 46 ms 12072 KB answer = YES
80 Correct 40 ms 10352 KB answer = YES
81 Correct 33 ms 11848 KB answer = NO
82 Correct 62 ms 12304 KB answer = YES
83 Correct 64 ms 12560 KB answer = YES
84 Correct 63 ms 12720 KB answer = YES
85 Correct 55 ms 12764 KB answer = YES
86 Correct 51 ms 12328 KB answer = YES
87 Correct 34 ms 11596 KB answer = NO
88 Correct 59 ms 12100 KB answer = YES
89 Correct 53 ms 11848 KB answer = YES
90 Correct 51 ms 11724 KB answer = YES
91 Correct 55 ms 11852 KB answer = YES
92 Correct 27 ms 9300 KB answer = YES
93 Correct 26 ms 9272 KB answer = YES
94 Correct 39 ms 12212 KB answer = NO
95 Correct 32 ms 11432 KB answer = NO
96 Correct 107 ms 16892 KB answer = YES
97 Correct 33 ms 12176 KB answer = NO