답안 #751587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
751587	2023-05-31T19:46:37 Z	javotaz	Graph (BOI20_graph)	C++17	100 / 100	194 ms	20972 KB

Graph

// be nam khodavand jano kherad     kazin bartar andishe bar nagzarad
#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 12;
int n, m, bakhsh[N], omgh[N];
double x[N], check;
bool mrk[N];
vector<pair<int, int> > g[N], xs;
 
void output() {
	cout << "YES\n";
	for (int i = 1; i <= n; i++)
		cout << x[i] << ' ';
}
 
void wrong_output() {
	cout << "NO\n";
	exit(0);
}
 
void check_ans(int a) {
	for (auto i: g[a]) {
		int v = i.first;
		int dis = i.second;
		if (mrk[v]) {
			if (dis - x[a] != x[v])
				wrong_output();
		}
		else {
			mrk[v] = true;
			x[v] = dis - x[a];
			check_ans(v);
		}
	}
}
 
void dfs(int u) {
	for (auto i: g[u]) {
		int v = i.first;
		if (omgh[v] == omgh[u]) {
			check = (x[v] * -1 * omgh[v] + ((i.second - x[u]) * omgh[u])) / 2.0; 
			return;
		}
		if (!omgh[v]) {
			omgh[v] = omgh[u] * -1;
			x[v] = i.second - x[u];  
			dfs(v);
		}
	}
}
 
void dfs_fill_x(int a) {
	for (auto i: g[a]) {
		int u = i.first;
		omgh[u] = omgh[a] * -1;
		int tmp = (i.second - omgh[a] * x[a]) * omgh[u];
		if (mrk[u]) {
			if (x[u] != tmp)
				wrong_output();
		}
		else {
			x[u] = tmp;
			xs.push_back({tmp, u});
			mrk[u] = true;
			dfs_fill_x(u);
		}
	}
}
 
void minimize_output() {
	sort(xs.begin(), xs.end());
	int tmp = xs.size();
	tmp /= 2;
	int r = xs[tmp].first;
	for (auto i: xs) 
		x[i.second] = (i.first - r) * omgh[i.second];
}
 
bool do_bakhshi(int u) {
	bool res = true;
	for (auto i: g[u]) {
		int v = i.first;
		if (bakhsh[v] == bakhsh[u])
			return false;
		if (!bakhsh[v]) {
			bakhsh[v] = (bakhsh[u] == 1)? 2 : 1;
			res &= do_bakhshi(v);
		}
	}
	return res;
}
 
void solve() {
	for (int i = 1; i <= n; i++) {
		if (!mrk[i]) {
			xs.clear();
			xs.push_back({0, i});
			check = 0;
			bakhsh[i] = 1;
			omgh[i] = 1;
			mrk[i] = true;
			if (do_bakhshi(i)) dfs_fill_x(i), minimize_output();
			else {
				dfs(i);
				x[i] = check;
				check_ans(i);
			}
		}
	}
}
 
void input() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v, color;
		cin >> u >> v >> color;
		g[u].push_back({v, color});
		g[v].push_back({u, color});
	}
}
 
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	input(), solve(), output();
}
 
// migan garme bazar kheila

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2680 KB	answer = YES
2	Correct	2 ms	2644 KB	answer = YES
3	Correct	2 ms	2644 KB	answer = YES
4	Correct	2 ms	2644 KB	answer = NO
5	Correct	2 ms	2644 KB	answer = YES
6	Correct	2 ms	2676 KB	answer = YES
7	Correct	2 ms	2644 KB	answer = YES
8	Correct	2 ms	2644 KB	answer = YES
9	Correct	2 ms	2676 KB	answer = NO
10	Correct	2 ms	2648 KB	answer = YES
11	Correct	2 ms	2680 KB	answer = YES
12	Correct	2 ms	2684 KB	answer = NO
13	Correct	2 ms	2644 KB	answer = YES
14	Correct	2 ms	2644 KB	answer = YES
15	Correct	2 ms	2644 KB	answer = YES
16	Correct	2 ms	2644 KB	answer = YES
17	Correct	2 ms	2644 KB	answer = YES
18	Correct	2 ms	2644 KB	answer = YES
19	Correct	2 ms	2644 KB	answer = YES
20	Correct	2 ms	2644 KB	answer = YES
21	Correct	2 ms	2676 KB	answer = YES
22	Correct	2 ms	2644 KB	answer = NO
23	Correct	1 ms	2644 KB	answer = NO

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2680 KB	answer = YES
2	Correct	2 ms	2644 KB	answer = YES
3	Correct	2 ms	2644 KB	answer = YES
4	Correct	2 ms	2644 KB	answer = NO
5	Correct	2 ms	2644 KB	answer = YES
6	Correct	2 ms	2676 KB	answer = YES
7	Correct	2 ms	2644 KB	answer = YES
8	Correct	2 ms	2644 KB	answer = YES
9	Correct	2 ms	2676 KB	answer = NO
10	Correct	2 ms	2648 KB	answer = YES
11	Correct	2 ms	2680 KB	answer = YES
12	Correct	2 ms	2684 KB	answer = NO
13	Correct	2 ms	2644 KB	answer = YES
14	Correct	2 ms	2644 KB	answer = YES
15	Correct	2 ms	2644 KB	answer = YES
16	Correct	2 ms	2644 KB	answer = YES
17	Correct	2 ms	2644 KB	answer = YES
18	Correct	2 ms	2644 KB	answer = YES
19	Correct	2 ms	2644 KB	answer = YES
20	Correct	2 ms	2644 KB	answer = YES
21	Correct	2 ms	2676 KB	answer = YES
22	Correct	2 ms	2644 KB	answer = NO
23	Correct	1 ms	2644 KB	answer = NO
24	Correct	2 ms	2644 KB	answer = YES
25	Correct	2 ms	2644 KB	answer = YES
26	Correct	2 ms	2644 KB	answer = YES
27	Correct	2 ms	2680 KB	answer = YES
28	Correct	2 ms	2684 KB	answer = YES
29	Correct	2 ms	2644 KB	answer = YES
30	Correct	2 ms	2644 KB	answer = NO
31	Correct	2 ms	2644 KB	answer = YES
32	Correct	2 ms	2644 KB	answer = YES
33	Correct	2 ms	2684 KB	answer = YES
34	Correct	2 ms	2644 KB	answer = YES
35	Correct	1 ms	2644 KB	answer = YES
36	Correct	2 ms	2644 KB	answer = YES

Subtask #3
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2680 KB	answer = YES
2	Correct	2 ms	2644 KB	answer = YES
3	Correct	2 ms	2644 KB	answer = YES
4	Correct	2 ms	2644 KB	answer = NO
5	Correct	2 ms	2644 KB	answer = YES
6	Correct	2 ms	2676 KB	answer = YES
7	Correct	2 ms	2644 KB	answer = YES
8	Correct	2 ms	2644 KB	answer = YES
9	Correct	2 ms	2676 KB	answer = NO
10	Correct	2 ms	2648 KB	answer = YES
11	Correct	2 ms	2680 KB	answer = YES
12	Correct	2 ms	2684 KB	answer = NO
13	Correct	2 ms	2644 KB	answer = YES
14	Correct	2 ms	2644 KB	answer = YES
15	Correct	2 ms	2644 KB	answer = YES
16	Correct	2 ms	2644 KB	answer = YES
17	Correct	2 ms	2644 KB	answer = YES
18	Correct	2 ms	2644 KB	answer = YES
19	Correct	2 ms	2644 KB	answer = YES
20	Correct	2 ms	2644 KB	answer = YES
21	Correct	2 ms	2676 KB	answer = YES
22	Correct	2 ms	2644 KB	answer = NO
23	Correct	1 ms	2644 KB	answer = NO
24	Correct	2 ms	2644 KB	answer = YES
25	Correct	2 ms	2644 KB	answer = YES
26	Correct	2 ms	2644 KB	answer = YES
27	Correct	2 ms	2680 KB	answer = YES
28	Correct	2 ms	2684 KB	answer = YES
29	Correct	2 ms	2644 KB	answer = YES
30	Correct	2 ms	2644 KB	answer = NO
31	Correct	2 ms	2644 KB	answer = YES
32	Correct	2 ms	2644 KB	answer = YES
33	Correct	2 ms	2684 KB	answer = YES
34	Correct	2 ms	2644 KB	answer = YES
35	Correct	1 ms	2644 KB	answer = YES
36	Correct	2 ms	2644 KB	answer = YES
37	Correct	2 ms	2676 KB	answer = YES
38	Correct	2 ms	2676 KB	answer = YES
39	Correct	3 ms	2644 KB	answer = YES
40	Correct	2 ms	2644 KB	answer = YES
41	Correct	2 ms	2680 KB	answer = NO
42	Correct	2 ms	2772 KB	answer = YES
43	Correct	3 ms	2644 KB	answer = YES
44	Correct	4 ms	2644 KB	answer = YES
45	Correct	2 ms	2684 KB	answer = YES
46	Correct	2 ms	2644 KB	answer = YES
47	Correct	3 ms	2680 KB	answer = YES
48	Correct	3 ms	2644 KB	answer = YES

Subtask #4
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2680 KB	answer = YES
2	Correct	2 ms	2644 KB	answer = YES
3	Correct	2 ms	2644 KB	answer = YES
4	Correct	2 ms	2644 KB	answer = NO
5	Correct	2 ms	2644 KB	answer = YES
6	Correct	2 ms	2676 KB	answer = YES
7	Correct	2 ms	2644 KB	answer = YES
8	Correct	2 ms	2644 KB	answer = YES
9	Correct	2 ms	2676 KB	answer = NO
10	Correct	2 ms	2648 KB	answer = YES
11	Correct	2 ms	2680 KB	answer = YES
12	Correct	2 ms	2684 KB	answer = NO
13	Correct	2 ms	2644 KB	answer = YES
14	Correct	2 ms	2644 KB	answer = YES
15	Correct	2 ms	2644 KB	answer = YES
16	Correct	2 ms	2644 KB	answer = YES
17	Correct	2 ms	2644 KB	answer = YES
18	Correct	2 ms	2644 KB	answer = YES
19	Correct	2 ms	2644 KB	answer = YES
20	Correct	2 ms	2644 KB	answer = YES
21	Correct	2 ms	2676 KB	answer = YES
22	Correct	2 ms	2644 KB	answer = NO
23	Correct	1 ms	2644 KB	answer = NO
24	Correct	2 ms	2644 KB	answer = YES
25	Correct	2 ms	2644 KB	answer = YES
26	Correct	2 ms	2644 KB	answer = YES
27	Correct	2 ms	2680 KB	answer = YES
28	Correct	2 ms	2684 KB	answer = YES
29	Correct	2 ms	2644 KB	answer = YES
30	Correct	2 ms	2644 KB	answer = NO
31	Correct	2 ms	2644 KB	answer = YES
32	Correct	2 ms	2644 KB	answer = YES
33	Correct	2 ms	2684 KB	answer = YES
34	Correct	2 ms	2644 KB	answer = YES
35	Correct	1 ms	2644 KB	answer = YES
36	Correct	2 ms	2644 KB	answer = YES
37	Correct	2 ms	2676 KB	answer = YES
38	Correct	2 ms	2676 KB	answer = YES
39	Correct	3 ms	2644 KB	answer = YES
40	Correct	2 ms	2644 KB	answer = YES
41	Correct	2 ms	2680 KB	answer = NO
42	Correct	2 ms	2772 KB	answer = YES
43	Correct	3 ms	2644 KB	answer = YES
44	Correct	4 ms	2644 KB	answer = YES
45	Correct	2 ms	2684 KB	answer = YES
46	Correct	2 ms	2644 KB	answer = YES
47	Correct	3 ms	2680 KB	answer = YES
48	Correct	3 ms	2644 KB	answer = YES
49	Correct	10 ms	3456 KB	answer = YES
50	Correct	9 ms	3584 KB	answer = YES
51	Correct	10 ms	4120 KB	answer = YES
52	Correct	7 ms	3456 KB	answer = NO
53	Correct	4 ms	2772 KB	answer = YES
54	Correct	4 ms	2900 KB	answer = YES
55	Correct	6 ms	3028 KB	answer = YES
56	Correct	9 ms	3540 KB	answer = YES
57	Correct	9 ms	3328 KB	answer = YES
58	Correct	12 ms	3404 KB	answer = YES
59	Correct	9 ms	3284 KB	answer = YES
60	Correct	9 ms	3460 KB	answer = YES
61	Correct	5 ms	3028 KB	answer = YES
62	Correct	56 ms	9924 KB	answer = NO
63	Correct	56 ms	10044 KB	answer = YES
64	Correct	53 ms	10112 KB	answer = NO
65	Correct	54 ms	10080 KB	answer = YES
66	Correct	3 ms	2772 KB	answer = YES

Subtask #5
42.0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2680 KB	answer = YES
2	Correct	2 ms	2644 KB	answer = YES
3	Correct	2 ms	2644 KB	answer = YES
4	Correct	2 ms	2644 KB	answer = NO
5	Correct	2 ms	2644 KB	answer = YES
6	Correct	2 ms	2676 KB	answer = YES
7	Correct	2 ms	2644 KB	answer = YES
8	Correct	2 ms	2644 KB	answer = YES
9	Correct	2 ms	2676 KB	answer = NO
10	Correct	2 ms	2648 KB	answer = YES
11	Correct	2 ms	2680 KB	answer = YES
12	Correct	2 ms	2684 KB	answer = NO
13	Correct	2 ms	2644 KB	answer = YES
14	Correct	2 ms	2644 KB	answer = YES
15	Correct	2 ms	2644 KB	answer = YES
16	Correct	2 ms	2644 KB	answer = YES
17	Correct	2 ms	2644 KB	answer = YES
18	Correct	2 ms	2644 KB	answer = YES
19	Correct	2 ms	2644 KB	answer = YES
20	Correct	2 ms	2644 KB	answer = YES
21	Correct	2 ms	2676 KB	answer = YES
22	Correct	2 ms	2644 KB	answer = NO
23	Correct	1 ms	2644 KB	answer = NO
24	Correct	2 ms	2644 KB	answer = YES
25	Correct	2 ms	2644 KB	answer = YES
26	Correct	2 ms	2644 KB	answer = YES
27	Correct	2 ms	2680 KB	answer = YES
28	Correct	2 ms	2684 KB	answer = YES
29	Correct	2 ms	2644 KB	answer = YES
30	Correct	2 ms	2644 KB	answer = NO
31	Correct	2 ms	2644 KB	answer = YES
32	Correct	2 ms	2644 KB	answer = YES
33	Correct	2 ms	2684 KB	answer = YES
34	Correct	2 ms	2644 KB	answer = YES
35	Correct	1 ms	2644 KB	answer = YES
36	Correct	2 ms	2644 KB	answer = YES
37	Correct	2 ms	2676 KB	answer = YES
38	Correct	2 ms	2676 KB	answer = YES
39	Correct	3 ms	2644 KB	answer = YES
40	Correct	2 ms	2644 KB	answer = YES
41	Correct	2 ms	2680 KB	answer = NO
42	Correct	2 ms	2772 KB	answer = YES
43	Correct	3 ms	2644 KB	answer = YES
44	Correct	4 ms	2644 KB	answer = YES
45	Correct	2 ms	2684 KB	answer = YES
46	Correct	2 ms	2644 KB	answer = YES
47	Correct	3 ms	2680 KB	answer = YES
48	Correct	3 ms	2644 KB	answer = YES
49	Correct	10 ms	3456 KB	answer = YES
50	Correct	9 ms	3584 KB	answer = YES
51	Correct	10 ms	4120 KB	answer = YES
52	Correct	7 ms	3456 KB	answer = NO
53	Correct	4 ms	2772 KB	answer = YES
54	Correct	4 ms	2900 KB	answer = YES
55	Correct	6 ms	3028 KB	answer = YES
56	Correct	9 ms	3540 KB	answer = YES
57	Correct	9 ms	3328 KB	answer = YES
58	Correct	12 ms	3404 KB	answer = YES
59	Correct	9 ms	3284 KB	answer = YES
60	Correct	9 ms	3460 KB	answer = YES
61	Correct	5 ms	3028 KB	answer = YES
62	Correct	56 ms	9924 KB	answer = NO
63	Correct	56 ms	10044 KB	answer = YES
64	Correct	53 ms	10112 KB	answer = NO
65	Correct	54 ms	10080 KB	answer = YES
66	Correct	3 ms	2772 KB	answer = YES
67	Correct	98 ms	20924 KB	answer = YES
68	Correct	81 ms	20868 KB	answer = YES
69	Correct	79 ms	13728 KB	answer = YES
70	Correct	108 ms	18152 KB	answer = YES
71	Correct	87 ms	13808 KB	answer = YES
72	Correct	114 ms	10556 KB	answer = YES
73	Correct	95 ms	9676 KB	answer = YES
74	Correct	58 ms	9292 KB	answer = YES
75	Correct	25 ms	9736 KB	answer = NO
76	Correct	12 ms	3668 KB	answer = YES
77	Correct	24 ms	4704 KB	answer = YES
78	Correct	42 ms	6148 KB	answer = YES
79	Correct	87 ms	9512 KB	answer = YES
80	Correct	60 ms	13060 KB	answer = YES
81	Correct	56 ms	11200 KB	answer = NO
82	Correct	127 ms	13540 KB	answer = YES
83	Correct	134 ms	13864 KB	answer = YES
84	Correct	136 ms	20900 KB	answer = YES
85	Correct	91 ms	20972 KB	answer = YES
86	Correct	84 ms	13812 KB	answer = YES
87	Correct	64 ms	12252 KB	answer = NO
88	Correct	132 ms	11336 KB	answer = YES
89	Correct	79 ms	9024 KB	answer = YES
90	Correct	85 ms	9032 KB	answer = YES
91	Correct	118 ms	9052 KB	answer = YES
92	Correct	48 ms	6184 KB	answer = YES
93	Correct	64 ms	6080 KB	answer = YES
94	Correct	68 ms	20668 KB	answer = NO
95	Correct	39 ms	8780 KB	answer = NO
96	Correct	194 ms	16352 KB	answer = YES
97	Correct	36 ms	20544 KB	answer = NO

답안 #751587

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 12.0 / 12.0

Subtask #3 17.0 / 17.0

Subtask #4 24.0 / 24.0

Subtask #5 42.0 / 42.0

Subtask #1
5.0 / 5.0

Subtask #2
12.0 / 12.0

Subtask #3
17.0 / 17.0

Subtask #4
24.0 / 24.0

Subtask #5
42.0 / 42.0