# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
722739 |
2023-04-12T18:47:00 Z |
gagik_2007 |
Graph (BOI20_graph) |
C++17 |
|
200 ms |
28396 KB |
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;
typedef long long ll;
typedef long double ld;
#define ff first
#define ss second
ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 200007;
const ll M = 107;
const ll LG = 31;
ll n, m, k;
vector<pair<int, int>>g[N];
bool used[N];
bool neg[N]; // if the x in the value formula has the negative sign
ll val[N]; // if neg[v]: value = val[v] - x, else: value = x + val[v]
bool defined_value[N];
ll vlx2[N];
bool is_root[N];
vector<int>cmp[N];
void dfs(int v, int par, int root) {
//cout << v << endl;
cmp[root].push_back(v);
for (auto e : g[v]) {
int to = e.ff;
int c = e.ss;
if (to != par) {
if (!used[to]) {
if (neg[v]) {
val[to] = c - val[v];
}
else {
neg[to] = true;
val[to] = c - val[v];
}
used[to] = true;
dfs(to, v, root);
}
else {
if (neg[v] == neg[to]) {
if (neg[v]) {
if (!defined_value[root]) {
vlx2[root] = val[v] + val[to] - c;
defined_value[root] = true;
//cout << "Defined: " << vlx2[root] << endl;
}
else if (vlx2[root] != val[v] + val[to] - c) {
cout << "NO\n";
exit(0);
}
}
else {
if (!defined_value[root]) {
vlx2[root] = c - val[v] - val[to];
defined_value[root] = true;
//cout << "Defined: " << vlx2[root] << endl;
}
else if (vlx2[root] != c - val[v] - val[to]) {
cout << "NO\n";
exit(0);
}
}
}
else {
if (val[v] + val[to] != c) {
cout << "NO\n";
exit(0);
}
}
}
}
}
}
ll get_sum(ll curvlx2, int root) {
//cout << "PROCESSING: " << curvlx2 << endl;
ll sum = 0;
for (int v : cmp[root]) {
ll vl = 0;
if (neg[v]) {
vl = val[v] * 2 - curvlx2;
}
else {
vl = val[v] * 2 + curvlx2;
}
//cout << vl << " ";
sum += abs(vl);
}
//cout << endl;
return sum;
}
int main() {
//freopen("in.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y;
int tp;
cin >> x >> y >> tp;
g[x].push_back({ y,tp });
g[y].push_back({ x,tp });
}
for (int v = 1; v <= n; v++) {
if (!used[v]) {
used[v] = true;
is_root[v] = true;
dfs(v, -1, v);
}
}
cout << setprecision(12) << fixed;
cout << "YES\n";
vector<ld>ans(n + 1, 0);
for (int u = 1; u <= n; u++) {
if (is_root[u]) {
if (defined_value[u]) {
for (int v : cmp[u]) {
ld vl = 0;
if (neg[v]) {
vl = val[v] - ld(vlx2[u]) / 2.0;
}
else {
vl = val[v] + ld(vlx2[u]) / 2.0;
}
ans[v] = vl;
}
}
else {
pair<ll, ll>mn = { INF,INF };
for (ll cur = -M; cur <= M; cur++) {
mn = min(mn, { get_sum(cur,u),cur });
}
vlx2[u] = mn.ss;
for (int v : cmp[u]) {
ld vl = 0;
if (neg[v]) {
vl = val[v] - ld(vlx2[u]) / 2.0;
}
else {
vl = val[v] + ld(vlx2[u]) / 2.0;
}
ans[v] = vl;
}
}
}
}
for (int v = 1; v <= n; v++) {
cout << ans[v] << " ";
}
cout << endl;
}
/// ---- - -------- ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - -------- ------ -------- -- - - -
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
answer = YES |
2 |
Correct |
6 ms |
9684 KB |
answer = YES |
3 |
Correct |
5 ms |
9684 KB |
answer = YES |
4 |
Correct |
5 ms |
9684 KB |
answer = NO |
5 |
Correct |
5 ms |
9684 KB |
answer = YES |
6 |
Correct |
5 ms |
9684 KB |
answer = YES |
7 |
Correct |
5 ms |
9684 KB |
answer = YES |
8 |
Correct |
5 ms |
9636 KB |
answer = YES |
9 |
Correct |
5 ms |
9684 KB |
answer = NO |
10 |
Correct |
5 ms |
9684 KB |
answer = YES |
11 |
Correct |
7 ms |
9700 KB |
answer = YES |
12 |
Correct |
6 ms |
9684 KB |
answer = NO |
13 |
Correct |
5 ms |
9684 KB |
answer = YES |
14 |
Correct |
5 ms |
9684 KB |
answer = YES |
15 |
Correct |
5 ms |
9684 KB |
answer = YES |
16 |
Correct |
5 ms |
9684 KB |
answer = YES |
17 |
Correct |
6 ms |
9684 KB |
answer = YES |
18 |
Correct |
5 ms |
9684 KB |
answer = YES |
19 |
Correct |
6 ms |
9684 KB |
answer = YES |
20 |
Correct |
5 ms |
9684 KB |
answer = YES |
21 |
Correct |
6 ms |
9684 KB |
answer = YES |
22 |
Correct |
6 ms |
9684 KB |
answer = NO |
23 |
Correct |
5 ms |
9684 KB |
answer = NO |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
answer = YES |
2 |
Correct |
6 ms |
9684 KB |
answer = YES |
3 |
Correct |
5 ms |
9684 KB |
answer = YES |
4 |
Correct |
5 ms |
9684 KB |
answer = NO |
5 |
Correct |
5 ms |
9684 KB |
answer = YES |
6 |
Correct |
5 ms |
9684 KB |
answer = YES |
7 |
Correct |
5 ms |
9684 KB |
answer = YES |
8 |
Correct |
5 ms |
9636 KB |
answer = YES |
9 |
Correct |
5 ms |
9684 KB |
answer = NO |
10 |
Correct |
5 ms |
9684 KB |
answer = YES |
11 |
Correct |
7 ms |
9700 KB |
answer = YES |
12 |
Correct |
6 ms |
9684 KB |
answer = NO |
13 |
Correct |
5 ms |
9684 KB |
answer = YES |
14 |
Correct |
5 ms |
9684 KB |
answer = YES |
15 |
Correct |
5 ms |
9684 KB |
answer = YES |
16 |
Correct |
5 ms |
9684 KB |
answer = YES |
17 |
Correct |
6 ms |
9684 KB |
answer = YES |
18 |
Correct |
5 ms |
9684 KB |
answer = YES |
19 |
Correct |
6 ms |
9684 KB |
answer = YES |
20 |
Correct |
5 ms |
9684 KB |
answer = YES |
21 |
Correct |
6 ms |
9684 KB |
answer = YES |
22 |
Correct |
6 ms |
9684 KB |
answer = NO |
23 |
Correct |
5 ms |
9684 KB |
answer = NO |
24 |
Correct |
5 ms |
9684 KB |
answer = YES |
25 |
Correct |
5 ms |
9684 KB |
answer = YES |
26 |
Correct |
5 ms |
9684 KB |
answer = YES |
27 |
Correct |
5 ms |
9684 KB |
answer = YES |
28 |
Correct |
5 ms |
9684 KB |
answer = YES |
29 |
Correct |
7 ms |
9684 KB |
answer = YES |
30 |
Correct |
5 ms |
9684 KB |
answer = NO |
31 |
Correct |
7 ms |
9748 KB |
answer = YES |
32 |
Correct |
5 ms |
9684 KB |
answer = YES |
33 |
Correct |
5 ms |
9684 KB |
answer = YES |
34 |
Correct |
5 ms |
9684 KB |
answer = YES |
35 |
Correct |
5 ms |
9684 KB |
answer = YES |
36 |
Correct |
6 ms |
9684 KB |
answer = YES |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
answer = YES |
2 |
Correct |
6 ms |
9684 KB |
answer = YES |
3 |
Correct |
5 ms |
9684 KB |
answer = YES |
4 |
Correct |
5 ms |
9684 KB |
answer = NO |
5 |
Correct |
5 ms |
9684 KB |
answer = YES |
6 |
Correct |
5 ms |
9684 KB |
answer = YES |
7 |
Correct |
5 ms |
9684 KB |
answer = YES |
8 |
Correct |
5 ms |
9636 KB |
answer = YES |
9 |
Correct |
5 ms |
9684 KB |
answer = NO |
10 |
Correct |
5 ms |
9684 KB |
answer = YES |
11 |
Correct |
7 ms |
9700 KB |
answer = YES |
12 |
Correct |
6 ms |
9684 KB |
answer = NO |
13 |
Correct |
5 ms |
9684 KB |
answer = YES |
14 |
Correct |
5 ms |
9684 KB |
answer = YES |
15 |
Correct |
5 ms |
9684 KB |
answer = YES |
16 |
Correct |
5 ms |
9684 KB |
answer = YES |
17 |
Correct |
6 ms |
9684 KB |
answer = YES |
18 |
Correct |
5 ms |
9684 KB |
answer = YES |
19 |
Correct |
6 ms |
9684 KB |
answer = YES |
20 |
Correct |
5 ms |
9684 KB |
answer = YES |
21 |
Correct |
6 ms |
9684 KB |
answer = YES |
22 |
Correct |
6 ms |
9684 KB |
answer = NO |
23 |
Correct |
5 ms |
9684 KB |
answer = NO |
24 |
Correct |
5 ms |
9684 KB |
answer = YES |
25 |
Correct |
5 ms |
9684 KB |
answer = YES |
26 |
Correct |
5 ms |
9684 KB |
answer = YES |
27 |
Correct |
5 ms |
9684 KB |
answer = YES |
28 |
Correct |
5 ms |
9684 KB |
answer = YES |
29 |
Correct |
7 ms |
9684 KB |
answer = YES |
30 |
Correct |
5 ms |
9684 KB |
answer = NO |
31 |
Correct |
7 ms |
9748 KB |
answer = YES |
32 |
Correct |
5 ms |
9684 KB |
answer = YES |
33 |
Correct |
5 ms |
9684 KB |
answer = YES |
34 |
Correct |
5 ms |
9684 KB |
answer = YES |
35 |
Correct |
5 ms |
9684 KB |
answer = YES |
36 |
Correct |
6 ms |
9684 KB |
answer = YES |
37 |
Correct |
5 ms |
9684 KB |
answer = YES |
38 |
Correct |
5 ms |
9684 KB |
answer = YES |
39 |
Correct |
6 ms |
9684 KB |
answer = YES |
40 |
Correct |
7 ms |
9756 KB |
answer = YES |
41 |
Correct |
5 ms |
9684 KB |
answer = NO |
42 |
Correct |
7 ms |
9812 KB |
answer = YES |
43 |
Correct |
9 ms |
9812 KB |
answer = YES |
44 |
Correct |
7 ms |
9812 KB |
answer = YES |
45 |
Correct |
9 ms |
9812 KB |
answer = YES |
46 |
Correct |
6 ms |
9740 KB |
answer = YES |
47 |
Correct |
6 ms |
9776 KB |
answer = YES |
48 |
Correct |
7 ms |
9812 KB |
answer = YES |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
answer = YES |
2 |
Correct |
6 ms |
9684 KB |
answer = YES |
3 |
Correct |
5 ms |
9684 KB |
answer = YES |
4 |
Correct |
5 ms |
9684 KB |
answer = NO |
5 |
Correct |
5 ms |
9684 KB |
answer = YES |
6 |
Correct |
5 ms |
9684 KB |
answer = YES |
7 |
Correct |
5 ms |
9684 KB |
answer = YES |
8 |
Correct |
5 ms |
9636 KB |
answer = YES |
9 |
Correct |
5 ms |
9684 KB |
answer = NO |
10 |
Correct |
5 ms |
9684 KB |
answer = YES |
11 |
Correct |
7 ms |
9700 KB |
answer = YES |
12 |
Correct |
6 ms |
9684 KB |
answer = NO |
13 |
Correct |
5 ms |
9684 KB |
answer = YES |
14 |
Correct |
5 ms |
9684 KB |
answer = YES |
15 |
Correct |
5 ms |
9684 KB |
answer = YES |
16 |
Correct |
5 ms |
9684 KB |
answer = YES |
17 |
Correct |
6 ms |
9684 KB |
answer = YES |
18 |
Correct |
5 ms |
9684 KB |
answer = YES |
19 |
Correct |
6 ms |
9684 KB |
answer = YES |
20 |
Correct |
5 ms |
9684 KB |
answer = YES |
21 |
Correct |
6 ms |
9684 KB |
answer = YES |
22 |
Correct |
6 ms |
9684 KB |
answer = NO |
23 |
Correct |
5 ms |
9684 KB |
answer = NO |
24 |
Correct |
5 ms |
9684 KB |
answer = YES |
25 |
Correct |
5 ms |
9684 KB |
answer = YES |
26 |
Correct |
5 ms |
9684 KB |
answer = YES |
27 |
Correct |
5 ms |
9684 KB |
answer = YES |
28 |
Correct |
5 ms |
9684 KB |
answer = YES |
29 |
Correct |
7 ms |
9684 KB |
answer = YES |
30 |
Correct |
5 ms |
9684 KB |
answer = NO |
31 |
Correct |
7 ms |
9748 KB |
answer = YES |
32 |
Correct |
5 ms |
9684 KB |
answer = YES |
33 |
Correct |
5 ms |
9684 KB |
answer = YES |
34 |
Correct |
5 ms |
9684 KB |
answer = YES |
35 |
Correct |
5 ms |
9684 KB |
answer = YES |
36 |
Correct |
6 ms |
9684 KB |
answer = YES |
37 |
Correct |
5 ms |
9684 KB |
answer = YES |
38 |
Correct |
5 ms |
9684 KB |
answer = YES |
39 |
Correct |
6 ms |
9684 KB |
answer = YES |
40 |
Correct |
7 ms |
9756 KB |
answer = YES |
41 |
Correct |
5 ms |
9684 KB |
answer = NO |
42 |
Correct |
7 ms |
9812 KB |
answer = YES |
43 |
Correct |
9 ms |
9812 KB |
answer = YES |
44 |
Correct |
7 ms |
9812 KB |
answer = YES |
45 |
Correct |
9 ms |
9812 KB |
answer = YES |
46 |
Correct |
6 ms |
9740 KB |
answer = YES |
47 |
Correct |
6 ms |
9776 KB |
answer = YES |
48 |
Correct |
7 ms |
9812 KB |
answer = YES |
49 |
Correct |
22 ms |
10624 KB |
answer = YES |
50 |
Correct |
15 ms |
11016 KB |
answer = YES |
51 |
Correct |
18 ms |
10964 KB |
answer = YES |
52 |
Correct |
8 ms |
10196 KB |
answer = NO |
53 |
Correct |
6 ms |
9812 KB |
answer = YES |
54 |
Correct |
11 ms |
9940 KB |
answer = YES |
55 |
Correct |
13 ms |
10196 KB |
answer = YES |
56 |
Correct |
20 ms |
10580 KB |
answer = YES |
57 |
Correct |
18 ms |
10580 KB |
answer = YES |
58 |
Correct |
17 ms |
10544 KB |
answer = YES |
59 |
Correct |
13 ms |
10488 KB |
answer = YES |
60 |
Correct |
21 ms |
10584 KB |
answer = YES |
61 |
Correct |
9 ms |
10196 KB |
answer = YES |
62 |
Correct |
67 ms |
14532 KB |
answer = NO |
63 |
Correct |
65 ms |
15332 KB |
answer = YES |
64 |
Correct |
57 ms |
15132 KB |
answer = NO |
65 |
Correct |
78 ms |
15248 KB |
answer = YES |
66 |
Correct |
8 ms |
9812 KB |
answer = YES |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
answer = YES |
2 |
Correct |
6 ms |
9684 KB |
answer = YES |
3 |
Correct |
5 ms |
9684 KB |
answer = YES |
4 |
Correct |
5 ms |
9684 KB |
answer = NO |
5 |
Correct |
5 ms |
9684 KB |
answer = YES |
6 |
Correct |
5 ms |
9684 KB |
answer = YES |
7 |
Correct |
5 ms |
9684 KB |
answer = YES |
8 |
Correct |
5 ms |
9636 KB |
answer = YES |
9 |
Correct |
5 ms |
9684 KB |
answer = NO |
10 |
Correct |
5 ms |
9684 KB |
answer = YES |
11 |
Correct |
7 ms |
9700 KB |
answer = YES |
12 |
Correct |
6 ms |
9684 KB |
answer = NO |
13 |
Correct |
5 ms |
9684 KB |
answer = YES |
14 |
Correct |
5 ms |
9684 KB |
answer = YES |
15 |
Correct |
5 ms |
9684 KB |
answer = YES |
16 |
Correct |
5 ms |
9684 KB |
answer = YES |
17 |
Correct |
6 ms |
9684 KB |
answer = YES |
18 |
Correct |
5 ms |
9684 KB |
answer = YES |
19 |
Correct |
6 ms |
9684 KB |
answer = YES |
20 |
Correct |
5 ms |
9684 KB |
answer = YES |
21 |
Correct |
6 ms |
9684 KB |
answer = YES |
22 |
Correct |
6 ms |
9684 KB |
answer = NO |
23 |
Correct |
5 ms |
9684 KB |
answer = NO |
24 |
Correct |
5 ms |
9684 KB |
answer = YES |
25 |
Correct |
5 ms |
9684 KB |
answer = YES |
26 |
Correct |
5 ms |
9684 KB |
answer = YES |
27 |
Correct |
5 ms |
9684 KB |
answer = YES |
28 |
Correct |
5 ms |
9684 KB |
answer = YES |
29 |
Correct |
7 ms |
9684 KB |
answer = YES |
30 |
Correct |
5 ms |
9684 KB |
answer = NO |
31 |
Correct |
7 ms |
9748 KB |
answer = YES |
32 |
Correct |
5 ms |
9684 KB |
answer = YES |
33 |
Correct |
5 ms |
9684 KB |
answer = YES |
34 |
Correct |
5 ms |
9684 KB |
answer = YES |
35 |
Correct |
5 ms |
9684 KB |
answer = YES |
36 |
Correct |
6 ms |
9684 KB |
answer = YES |
37 |
Correct |
5 ms |
9684 KB |
answer = YES |
38 |
Correct |
5 ms |
9684 KB |
answer = YES |
39 |
Correct |
6 ms |
9684 KB |
answer = YES |
40 |
Correct |
7 ms |
9756 KB |
answer = YES |
41 |
Correct |
5 ms |
9684 KB |
answer = NO |
42 |
Correct |
7 ms |
9812 KB |
answer = YES |
43 |
Correct |
9 ms |
9812 KB |
answer = YES |
44 |
Correct |
7 ms |
9812 KB |
answer = YES |
45 |
Correct |
9 ms |
9812 KB |
answer = YES |
46 |
Correct |
6 ms |
9740 KB |
answer = YES |
47 |
Correct |
6 ms |
9776 KB |
answer = YES |
48 |
Correct |
7 ms |
9812 KB |
answer = YES |
49 |
Correct |
22 ms |
10624 KB |
answer = YES |
50 |
Correct |
15 ms |
11016 KB |
answer = YES |
51 |
Correct |
18 ms |
10964 KB |
answer = YES |
52 |
Correct |
8 ms |
10196 KB |
answer = NO |
53 |
Correct |
6 ms |
9812 KB |
answer = YES |
54 |
Correct |
11 ms |
9940 KB |
answer = YES |
55 |
Correct |
13 ms |
10196 KB |
answer = YES |
56 |
Correct |
20 ms |
10580 KB |
answer = YES |
57 |
Correct |
18 ms |
10580 KB |
answer = YES |
58 |
Correct |
17 ms |
10544 KB |
answer = YES |
59 |
Correct |
13 ms |
10488 KB |
answer = YES |
60 |
Correct |
21 ms |
10584 KB |
answer = YES |
61 |
Correct |
9 ms |
10196 KB |
answer = YES |
62 |
Correct |
67 ms |
14532 KB |
answer = NO |
63 |
Correct |
65 ms |
15332 KB |
answer = YES |
64 |
Correct |
57 ms |
15132 KB |
answer = NO |
65 |
Correct |
78 ms |
15248 KB |
answer = YES |
66 |
Correct |
8 ms |
9812 KB |
answer = YES |
67 |
Correct |
133 ms |
25288 KB |
answer = YES |
68 |
Correct |
119 ms |
25156 KB |
answer = YES |
69 |
Correct |
95 ms |
25276 KB |
answer = YES |
70 |
Correct |
141 ms |
28396 KB |
answer = YES |
71 |
Correct |
91 ms |
25284 KB |
answer = YES |
72 |
Correct |
200 ms |
18148 KB |
answer = YES |
73 |
Correct |
106 ms |
18196 KB |
answer = YES |
74 |
Correct |
73 ms |
18888 KB |
answer = YES |
75 |
Correct |
28 ms |
14688 KB |
answer = NO |
76 |
Correct |
26 ms |
10768 KB |
answer = YES |
77 |
Correct |
49 ms |
11892 KB |
answer = YES |
78 |
Correct |
105 ms |
13308 KB |
answer = YES |
79 |
Correct |
175 ms |
16904 KB |
answer = YES |
80 |
Correct |
116 ms |
18912 KB |
answer = YES |
81 |
Correct |
48 ms |
18440 KB |
answer = NO |
82 |
Correct |
115 ms |
24776 KB |
answer = YES |
83 |
Correct |
131 ms |
25584 KB |
answer = YES |
84 |
Incorrect |
180 ms |
25408 KB |
participant answer is larger than the answer of jury |
85 |
Halted |
0 ms |
0 KB |
- |