# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
550846 |
2022-04-19T10:27:55 Z |
Zhora_004 |
Graph (BOI20_graph) |
C++17 |
|
700 ms |
14588 KB |
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <string>
#include <sstream>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <stack>
#include <cstdio>
#include <climits>
#include <tuple>
#include <ctime>
#include <cstring>
#include <numeric>
#include <functional>
#include <chrono>
#include <cassert>
#include <bitset>
#include <fstream>
//#include <bit>
//#include <ranges>
//#include <numbers>
#define itn int
#define sacnf scanf
#define sz(a) ((int)((a).size()))
// printf("%.10f\n", ans);
/*ofstream fout("timeline.out");
ifstream fin("timeline.in");*/
using ll = long long;
using namespace std;
const ll mod = 1e9 + 7;
const int N = 2e5 + 1, inf = 1e9;
struct Edge {
int v, w;
};
int n, m;
vector<bool> vis;
vector<int> comp, ans;
vector<vector<Edge>> gp;
void dfs1(int u)
{
vis[u] = 1;
comp.push_back(u);
for (Edge& e : gp[u]) if (!vis[e.v]) dfs1(e.v);
}
void dfs2(int u, int val)
{
vis[u] = 1;
ans[u] = val;
for (Edge& e : gp[u]) if (!vis[e.v]) dfs2(e.v, e.w - val);
}
int ok()
{
int sum = 0;
for (int& u : comp)
{
for (Edge& e : gp[u])
{
int v = e.v, w = e.w;
if (!(-200 <= ans[u] && ans[u] <= 200 && -200 <= ans[v] && ans[v] <= 200 && ans[u] + ans[v] == w)) return inf;
}
sum += abs(ans[u]);
}
return sum;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
vis = vector<bool>(n);
ans = vector<int>(n);
gp = vector<vector<Edge>>(n);
for (int i = 0; i < m; i++)
{
int u, v, w;
cin >> u >> v >> w;
gp[--u].push_back({ --v, w * 2 });
gp[v].push_back({ u, w * 2 });
}
for (int i = 0; i < n; i++)
{
if (!vis[i])
{
comp.clear();
dfs1(i);
int mn = inf, num = inf;
for (int val = -200; val <= 200; val++)
{
for (int& u : comp) vis[u] = 0;
dfs2(i, val);
int sum = ok();
if (sum < mn)
{
mn = sum;
num = val;
}
}
if (num == inf) return cout << "NO", 0;
for (int& u : comp) vis[u] = 0;
dfs2(i, num);
}
}
cout << "YES\n";
for (int& i : ans)
{
if (i == -1) cout << "-0.5";
else
{
cout << i / 2;
if (abs(i) & 1) cout << ".5";
}
cout << " ";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
answer = YES |
2 |
Correct |
0 ms |
212 KB |
answer = YES |
3 |
Correct |
0 ms |
212 KB |
answer = YES |
4 |
Correct |
0 ms |
212 KB |
answer = NO |
5 |
Correct |
0 ms |
212 KB |
answer = YES |
6 |
Correct |
0 ms |
212 KB |
answer = YES |
7 |
Correct |
1 ms |
212 KB |
answer = YES |
8 |
Correct |
0 ms |
212 KB |
answer = YES |
9 |
Correct |
0 ms |
212 KB |
answer = NO |
10 |
Correct |
1 ms |
212 KB |
answer = YES |
11 |
Correct |
0 ms |
212 KB |
answer = YES |
12 |
Correct |
0 ms |
212 KB |
answer = NO |
13 |
Correct |
0 ms |
212 KB |
answer = YES |
14 |
Correct |
1 ms |
212 KB |
answer = YES |
15 |
Correct |
1 ms |
212 KB |
answer = YES |
16 |
Correct |
0 ms |
212 KB |
answer = YES |
17 |
Correct |
0 ms |
212 KB |
answer = YES |
18 |
Correct |
0 ms |
212 KB |
answer = YES |
19 |
Correct |
0 ms |
212 KB |
answer = YES |
20 |
Correct |
1 ms |
212 KB |
answer = YES |
21 |
Correct |
0 ms |
212 KB |
answer = YES |
22 |
Correct |
0 ms |
212 KB |
answer = NO |
23 |
Correct |
0 ms |
212 KB |
answer = NO |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
answer = YES |
2 |
Correct |
0 ms |
212 KB |
answer = YES |
3 |
Correct |
0 ms |
212 KB |
answer = YES |
4 |
Correct |
0 ms |
212 KB |
answer = NO |
5 |
Correct |
0 ms |
212 KB |
answer = YES |
6 |
Correct |
0 ms |
212 KB |
answer = YES |
7 |
Correct |
1 ms |
212 KB |
answer = YES |
8 |
Correct |
0 ms |
212 KB |
answer = YES |
9 |
Correct |
0 ms |
212 KB |
answer = NO |
10 |
Correct |
1 ms |
212 KB |
answer = YES |
11 |
Correct |
0 ms |
212 KB |
answer = YES |
12 |
Correct |
0 ms |
212 KB |
answer = NO |
13 |
Correct |
0 ms |
212 KB |
answer = YES |
14 |
Correct |
1 ms |
212 KB |
answer = YES |
15 |
Correct |
1 ms |
212 KB |
answer = YES |
16 |
Correct |
0 ms |
212 KB |
answer = YES |
17 |
Correct |
0 ms |
212 KB |
answer = YES |
18 |
Correct |
0 ms |
212 KB |
answer = YES |
19 |
Correct |
0 ms |
212 KB |
answer = YES |
20 |
Correct |
1 ms |
212 KB |
answer = YES |
21 |
Correct |
0 ms |
212 KB |
answer = YES |
22 |
Correct |
0 ms |
212 KB |
answer = NO |
23 |
Correct |
0 ms |
212 KB |
answer = NO |
24 |
Correct |
1 ms |
212 KB |
answer = YES |
25 |
Correct |
1 ms |
212 KB |
answer = YES |
26 |
Correct |
2 ms |
212 KB |
answer = YES |
27 |
Correct |
1 ms |
212 KB |
answer = YES |
28 |
Correct |
1 ms |
212 KB |
answer = YES |
29 |
Correct |
2 ms |
212 KB |
answer = YES |
30 |
Correct |
2 ms |
212 KB |
answer = NO |
31 |
Correct |
1 ms |
212 KB |
answer = YES |
32 |
Correct |
1 ms |
212 KB |
answer = YES |
33 |
Correct |
1 ms |
212 KB |
answer = YES |
34 |
Correct |
1 ms |
212 KB |
answer = YES |
35 |
Correct |
1 ms |
212 KB |
answer = YES |
36 |
Correct |
1 ms |
212 KB |
answer = YES |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
answer = YES |
2 |
Correct |
0 ms |
212 KB |
answer = YES |
3 |
Correct |
0 ms |
212 KB |
answer = YES |
4 |
Correct |
0 ms |
212 KB |
answer = NO |
5 |
Correct |
0 ms |
212 KB |
answer = YES |
6 |
Correct |
0 ms |
212 KB |
answer = YES |
7 |
Correct |
1 ms |
212 KB |
answer = YES |
8 |
Correct |
0 ms |
212 KB |
answer = YES |
9 |
Correct |
0 ms |
212 KB |
answer = NO |
10 |
Correct |
1 ms |
212 KB |
answer = YES |
11 |
Correct |
0 ms |
212 KB |
answer = YES |
12 |
Correct |
0 ms |
212 KB |
answer = NO |
13 |
Correct |
0 ms |
212 KB |
answer = YES |
14 |
Correct |
1 ms |
212 KB |
answer = YES |
15 |
Correct |
1 ms |
212 KB |
answer = YES |
16 |
Correct |
0 ms |
212 KB |
answer = YES |
17 |
Correct |
0 ms |
212 KB |
answer = YES |
18 |
Correct |
0 ms |
212 KB |
answer = YES |
19 |
Correct |
0 ms |
212 KB |
answer = YES |
20 |
Correct |
1 ms |
212 KB |
answer = YES |
21 |
Correct |
0 ms |
212 KB |
answer = YES |
22 |
Correct |
0 ms |
212 KB |
answer = NO |
23 |
Correct |
0 ms |
212 KB |
answer = NO |
24 |
Correct |
1 ms |
212 KB |
answer = YES |
25 |
Correct |
1 ms |
212 KB |
answer = YES |
26 |
Correct |
2 ms |
212 KB |
answer = YES |
27 |
Correct |
1 ms |
212 KB |
answer = YES |
28 |
Correct |
1 ms |
212 KB |
answer = YES |
29 |
Correct |
2 ms |
212 KB |
answer = YES |
30 |
Correct |
2 ms |
212 KB |
answer = NO |
31 |
Correct |
1 ms |
212 KB |
answer = YES |
32 |
Correct |
1 ms |
212 KB |
answer = YES |
33 |
Correct |
1 ms |
212 KB |
answer = YES |
34 |
Correct |
1 ms |
212 KB |
answer = YES |
35 |
Correct |
1 ms |
212 KB |
answer = YES |
36 |
Correct |
1 ms |
212 KB |
answer = YES |
37 |
Correct |
3 ms |
212 KB |
answer = YES |
38 |
Correct |
2 ms |
212 KB |
answer = YES |
39 |
Correct |
7 ms |
340 KB |
answer = YES |
40 |
Correct |
8 ms |
340 KB |
answer = YES |
41 |
Correct |
8 ms |
340 KB |
answer = NO |
42 |
Correct |
10 ms |
400 KB |
answer = YES |
43 |
Correct |
13 ms |
388 KB |
answer = YES |
44 |
Correct |
9 ms |
384 KB |
answer = YES |
45 |
Correct |
9 ms |
340 KB |
answer = YES |
46 |
Correct |
6 ms |
340 KB |
answer = YES |
47 |
Correct |
9 ms |
340 KB |
answer = YES |
48 |
Correct |
9 ms |
340 KB |
answer = YES |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
answer = YES |
2 |
Correct |
0 ms |
212 KB |
answer = YES |
3 |
Correct |
0 ms |
212 KB |
answer = YES |
4 |
Correct |
0 ms |
212 KB |
answer = NO |
5 |
Correct |
0 ms |
212 KB |
answer = YES |
6 |
Correct |
0 ms |
212 KB |
answer = YES |
7 |
Correct |
1 ms |
212 KB |
answer = YES |
8 |
Correct |
0 ms |
212 KB |
answer = YES |
9 |
Correct |
0 ms |
212 KB |
answer = NO |
10 |
Correct |
1 ms |
212 KB |
answer = YES |
11 |
Correct |
0 ms |
212 KB |
answer = YES |
12 |
Correct |
0 ms |
212 KB |
answer = NO |
13 |
Correct |
0 ms |
212 KB |
answer = YES |
14 |
Correct |
1 ms |
212 KB |
answer = YES |
15 |
Correct |
1 ms |
212 KB |
answer = YES |
16 |
Correct |
0 ms |
212 KB |
answer = YES |
17 |
Correct |
0 ms |
212 KB |
answer = YES |
18 |
Correct |
0 ms |
212 KB |
answer = YES |
19 |
Correct |
0 ms |
212 KB |
answer = YES |
20 |
Correct |
1 ms |
212 KB |
answer = YES |
21 |
Correct |
0 ms |
212 KB |
answer = YES |
22 |
Correct |
0 ms |
212 KB |
answer = NO |
23 |
Correct |
0 ms |
212 KB |
answer = NO |
24 |
Correct |
1 ms |
212 KB |
answer = YES |
25 |
Correct |
1 ms |
212 KB |
answer = YES |
26 |
Correct |
2 ms |
212 KB |
answer = YES |
27 |
Correct |
1 ms |
212 KB |
answer = YES |
28 |
Correct |
1 ms |
212 KB |
answer = YES |
29 |
Correct |
2 ms |
212 KB |
answer = YES |
30 |
Correct |
2 ms |
212 KB |
answer = NO |
31 |
Correct |
1 ms |
212 KB |
answer = YES |
32 |
Correct |
1 ms |
212 KB |
answer = YES |
33 |
Correct |
1 ms |
212 KB |
answer = YES |
34 |
Correct |
1 ms |
212 KB |
answer = YES |
35 |
Correct |
1 ms |
212 KB |
answer = YES |
36 |
Correct |
1 ms |
212 KB |
answer = YES |
37 |
Correct |
3 ms |
212 KB |
answer = YES |
38 |
Correct |
2 ms |
212 KB |
answer = YES |
39 |
Correct |
7 ms |
340 KB |
answer = YES |
40 |
Correct |
8 ms |
340 KB |
answer = YES |
41 |
Correct |
8 ms |
340 KB |
answer = NO |
42 |
Correct |
10 ms |
400 KB |
answer = YES |
43 |
Correct |
13 ms |
388 KB |
answer = YES |
44 |
Correct |
9 ms |
384 KB |
answer = YES |
45 |
Correct |
9 ms |
340 KB |
answer = YES |
46 |
Correct |
6 ms |
340 KB |
answer = YES |
47 |
Correct |
9 ms |
340 KB |
answer = YES |
48 |
Correct |
9 ms |
340 KB |
answer = YES |
49 |
Correct |
171 ms |
1080 KB |
answer = YES |
50 |
Correct |
94 ms |
1364 KB |
answer = YES |
51 |
Correct |
109 ms |
1364 KB |
answer = YES |
52 |
Correct |
86 ms |
1364 KB |
answer = NO |
53 |
Correct |
12 ms |
340 KB |
answer = YES |
54 |
Correct |
32 ms |
484 KB |
answer = YES |
55 |
Correct |
80 ms |
692 KB |
answer = YES |
56 |
Correct |
167 ms |
1052 KB |
answer = YES |
57 |
Correct |
125 ms |
968 KB |
answer = YES |
58 |
Correct |
130 ms |
924 KB |
answer = YES |
59 |
Correct |
121 ms |
948 KB |
answer = YES |
60 |
Correct |
161 ms |
1032 KB |
answer = YES |
61 |
Correct |
77 ms |
680 KB |
answer = YES |
62 |
Correct |
462 ms |
5668 KB |
answer = NO |
63 |
Correct |
447 ms |
8032 KB |
answer = YES |
64 |
Correct |
528 ms |
7932 KB |
answer = NO |
65 |
Correct |
455 ms |
8020 KB |
answer = YES |
66 |
Correct |
25 ms |
468 KB |
answer = YES |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
answer = YES |
2 |
Correct |
0 ms |
212 KB |
answer = YES |
3 |
Correct |
0 ms |
212 KB |
answer = YES |
4 |
Correct |
0 ms |
212 KB |
answer = NO |
5 |
Correct |
0 ms |
212 KB |
answer = YES |
6 |
Correct |
0 ms |
212 KB |
answer = YES |
7 |
Correct |
1 ms |
212 KB |
answer = YES |
8 |
Correct |
0 ms |
212 KB |
answer = YES |
9 |
Correct |
0 ms |
212 KB |
answer = NO |
10 |
Correct |
1 ms |
212 KB |
answer = YES |
11 |
Correct |
0 ms |
212 KB |
answer = YES |
12 |
Correct |
0 ms |
212 KB |
answer = NO |
13 |
Correct |
0 ms |
212 KB |
answer = YES |
14 |
Correct |
1 ms |
212 KB |
answer = YES |
15 |
Correct |
1 ms |
212 KB |
answer = YES |
16 |
Correct |
0 ms |
212 KB |
answer = YES |
17 |
Correct |
0 ms |
212 KB |
answer = YES |
18 |
Correct |
0 ms |
212 KB |
answer = YES |
19 |
Correct |
0 ms |
212 KB |
answer = YES |
20 |
Correct |
1 ms |
212 KB |
answer = YES |
21 |
Correct |
0 ms |
212 KB |
answer = YES |
22 |
Correct |
0 ms |
212 KB |
answer = NO |
23 |
Correct |
0 ms |
212 KB |
answer = NO |
24 |
Correct |
1 ms |
212 KB |
answer = YES |
25 |
Correct |
1 ms |
212 KB |
answer = YES |
26 |
Correct |
2 ms |
212 KB |
answer = YES |
27 |
Correct |
1 ms |
212 KB |
answer = YES |
28 |
Correct |
1 ms |
212 KB |
answer = YES |
29 |
Correct |
2 ms |
212 KB |
answer = YES |
30 |
Correct |
2 ms |
212 KB |
answer = NO |
31 |
Correct |
1 ms |
212 KB |
answer = YES |
32 |
Correct |
1 ms |
212 KB |
answer = YES |
33 |
Correct |
1 ms |
212 KB |
answer = YES |
34 |
Correct |
1 ms |
212 KB |
answer = YES |
35 |
Correct |
1 ms |
212 KB |
answer = YES |
36 |
Correct |
1 ms |
212 KB |
answer = YES |
37 |
Correct |
3 ms |
212 KB |
answer = YES |
38 |
Correct |
2 ms |
212 KB |
answer = YES |
39 |
Correct |
7 ms |
340 KB |
answer = YES |
40 |
Correct |
8 ms |
340 KB |
answer = YES |
41 |
Correct |
8 ms |
340 KB |
answer = NO |
42 |
Correct |
10 ms |
400 KB |
answer = YES |
43 |
Correct |
13 ms |
388 KB |
answer = YES |
44 |
Correct |
9 ms |
384 KB |
answer = YES |
45 |
Correct |
9 ms |
340 KB |
answer = YES |
46 |
Correct |
6 ms |
340 KB |
answer = YES |
47 |
Correct |
9 ms |
340 KB |
answer = YES |
48 |
Correct |
9 ms |
340 KB |
answer = YES |
49 |
Correct |
171 ms |
1080 KB |
answer = YES |
50 |
Correct |
94 ms |
1364 KB |
answer = YES |
51 |
Correct |
109 ms |
1364 KB |
answer = YES |
52 |
Correct |
86 ms |
1364 KB |
answer = NO |
53 |
Correct |
12 ms |
340 KB |
answer = YES |
54 |
Correct |
32 ms |
484 KB |
answer = YES |
55 |
Correct |
80 ms |
692 KB |
answer = YES |
56 |
Correct |
167 ms |
1052 KB |
answer = YES |
57 |
Correct |
125 ms |
968 KB |
answer = YES |
58 |
Correct |
130 ms |
924 KB |
answer = YES |
59 |
Correct |
121 ms |
948 KB |
answer = YES |
60 |
Correct |
161 ms |
1032 KB |
answer = YES |
61 |
Correct |
77 ms |
680 KB |
answer = YES |
62 |
Correct |
462 ms |
5668 KB |
answer = NO |
63 |
Correct |
447 ms |
8032 KB |
answer = YES |
64 |
Correct |
528 ms |
7932 KB |
answer = NO |
65 |
Correct |
455 ms |
8020 KB |
answer = YES |
66 |
Correct |
25 ms |
468 KB |
answer = YES |
67 |
Execution timed out |
844 ms |
14588 KB |
Time limit exceeded |
68 |
Halted |
0 ms |
0 KB |
- |