# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
859395 |
2023-10-10T05:57:38 Z |
maks007 |
Graph (BOI20_graph) |
C++14 |
|
1 ms |
348 KB |
#include "bits/stdc++.h"
using namespace std;
#define int long long
vector <vector <pair <int,double>>> g;
vector <double> used;
vector <int> comp;
void dfs(int v) {
used[v] = 1;
for(auto [i, j] : g[v]) {
if(used[i] == 1e9) dfs(i);
}
}
void get_comps() {
for(int i = 0; i < used.size(); i ++) {
if(used[i] == 1e9) {
dfs(i);
comp.push_back(i);
}
}
}
int check(int v) {
int f = 1;
for(auto [i, j] : g[v]) {
if(used[i] == 1e9) {
used[i] = j - used[v];
f = min(f, check(i));
}else {
if(used[i] + used[v] != j) f = 0;
}
}
return f;
}
vector <pair <int,double>> rec(int v) {
double mn = 1e9;
vector <pair <int,double>> ans;
for(double val = -2; val <= 2; val += 0.125) {
for(auto &j : used) j = 1e9;
used[v] = val;
if(check(v)) {
double cnt = 0;
for(auto &j : used) {
if(j == 1e9) continue;
cnt += fabs(j);
}
if(cnt <= mn) {
mn = cnt;
for(int j = 0; j < used.size(); j ++) {
if(used[j] == 1e9) continue;
ans.push_back({j, used[j]});
}
}
}
// cout << val << " ";
// if(val == 0.5) {
// for(auto j : used) cout << j << " ";
// }
}
if(mn == 1e9) {
cout << "NO\n";
exit(0);
}
return ans;
}
signed main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
g.resize(n);
used.resize(n, 1e9);
for(int i = 0; i < m; i ++) {
int u, v;
cin >> u >> v;
u --, v --;
double w;
cin >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
get_comps();
for(auto &j : used) j = 1e9;
vector <vector <pair <int,double>>> res;
for(auto i : comp) {
res.push_back(rec(i));
}
cout << "YES\n";
vector <double> ans(n);
for(auto i : res) {
for(auto j : i) ans[j.first] = j.second;
}
for(auto i : ans) cout << fixed << setprecision(6) << i << " ";
return 0;
}
Compilation message
Graph.cpp: In function 'void dfs(long long int)':
Graph.cpp:13:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
13 | for(auto [i, j] : g[v]) {
| ^
Graph.cpp: In function 'void get_comps()':
Graph.cpp:19:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for(int i = 0; i < used.size(); i ++) {
| ~~^~~~~~~~~~~~~
Graph.cpp: In function 'long long int check(long long int)':
Graph.cpp:29:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
29 | for(auto [i, j] : g[v]) {
| ^
Graph.cpp: In function 'std::vector<std::pair<long long int, double> > rec(long long int)':
Graph.cpp:54:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int j = 0; j < used.size(); j ++) {
| ~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
answer = YES |
2 |
Correct |
0 ms |
348 KB |
answer = YES |
3 |
Correct |
0 ms |
348 KB |
answer = YES |
4 |
Correct |
0 ms |
348 KB |
answer = NO |
5 |
Correct |
0 ms |
348 KB |
answer = YES |
6 |
Correct |
0 ms |
348 KB |
answer = YES |
7 |
Correct |
0 ms |
344 KB |
answer = YES |
8 |
Correct |
0 ms |
348 KB |
answer = YES |
9 |
Correct |
0 ms |
344 KB |
answer = NO |
10 |
Correct |
0 ms |
348 KB |
answer = YES |
11 |
Correct |
0 ms |
348 KB |
answer = YES |
12 |
Correct |
0 ms |
348 KB |
answer = NO |
13 |
Correct |
0 ms |
348 KB |
answer = YES |
14 |
Correct |
0 ms |
348 KB |
answer = YES |
15 |
Correct |
0 ms |
344 KB |
answer = YES |
16 |
Correct |
0 ms |
348 KB |
answer = YES |
17 |
Correct |
0 ms |
348 KB |
answer = YES |
18 |
Correct |
0 ms |
344 KB |
answer = YES |
19 |
Correct |
0 ms |
348 KB |
answer = YES |
20 |
Correct |
0 ms |
348 KB |
answer = YES |
21 |
Correct |
0 ms |
348 KB |
answer = YES |
22 |
Correct |
0 ms |
348 KB |
answer = NO |
23 |
Correct |
0 ms |
348 KB |
answer = NO |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
answer = YES |
2 |
Correct |
0 ms |
348 KB |
answer = YES |
3 |
Correct |
0 ms |
348 KB |
answer = YES |
4 |
Correct |
0 ms |
348 KB |
answer = NO |
5 |
Correct |
0 ms |
348 KB |
answer = YES |
6 |
Correct |
0 ms |
348 KB |
answer = YES |
7 |
Correct |
0 ms |
344 KB |
answer = YES |
8 |
Correct |
0 ms |
348 KB |
answer = YES |
9 |
Correct |
0 ms |
344 KB |
answer = NO |
10 |
Correct |
0 ms |
348 KB |
answer = YES |
11 |
Correct |
0 ms |
348 KB |
answer = YES |
12 |
Correct |
0 ms |
348 KB |
answer = NO |
13 |
Correct |
0 ms |
348 KB |
answer = YES |
14 |
Correct |
0 ms |
348 KB |
answer = YES |
15 |
Correct |
0 ms |
344 KB |
answer = YES |
16 |
Correct |
0 ms |
348 KB |
answer = YES |
17 |
Correct |
0 ms |
348 KB |
answer = YES |
18 |
Correct |
0 ms |
344 KB |
answer = YES |
19 |
Correct |
0 ms |
348 KB |
answer = YES |
20 |
Correct |
0 ms |
348 KB |
answer = YES |
21 |
Correct |
0 ms |
348 KB |
answer = YES |
22 |
Correct |
0 ms |
348 KB |
answer = NO |
23 |
Correct |
0 ms |
348 KB |
answer = NO |
24 |
Correct |
1 ms |
348 KB |
answer = YES |
25 |
Correct |
0 ms |
348 KB |
answer = YES |
26 |
Incorrect |
0 ms |
348 KB |
participant answer is larger than the answer of jury |
27 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
answer = YES |
2 |
Correct |
0 ms |
348 KB |
answer = YES |
3 |
Correct |
0 ms |
348 KB |
answer = YES |
4 |
Correct |
0 ms |
348 KB |
answer = NO |
5 |
Correct |
0 ms |
348 KB |
answer = YES |
6 |
Correct |
0 ms |
348 KB |
answer = YES |
7 |
Correct |
0 ms |
344 KB |
answer = YES |
8 |
Correct |
0 ms |
348 KB |
answer = YES |
9 |
Correct |
0 ms |
344 KB |
answer = NO |
10 |
Correct |
0 ms |
348 KB |
answer = YES |
11 |
Correct |
0 ms |
348 KB |
answer = YES |
12 |
Correct |
0 ms |
348 KB |
answer = NO |
13 |
Correct |
0 ms |
348 KB |
answer = YES |
14 |
Correct |
0 ms |
348 KB |
answer = YES |
15 |
Correct |
0 ms |
344 KB |
answer = YES |
16 |
Correct |
0 ms |
348 KB |
answer = YES |
17 |
Correct |
0 ms |
348 KB |
answer = YES |
18 |
Correct |
0 ms |
344 KB |
answer = YES |
19 |
Correct |
0 ms |
348 KB |
answer = YES |
20 |
Correct |
0 ms |
348 KB |
answer = YES |
21 |
Correct |
0 ms |
348 KB |
answer = YES |
22 |
Correct |
0 ms |
348 KB |
answer = NO |
23 |
Correct |
0 ms |
348 KB |
answer = NO |
24 |
Correct |
1 ms |
348 KB |
answer = YES |
25 |
Correct |
0 ms |
348 KB |
answer = YES |
26 |
Incorrect |
0 ms |
348 KB |
participant answer is larger than the answer of jury |
27 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
answer = YES |
2 |
Correct |
0 ms |
348 KB |
answer = YES |
3 |
Correct |
0 ms |
348 KB |
answer = YES |
4 |
Correct |
0 ms |
348 KB |
answer = NO |
5 |
Correct |
0 ms |
348 KB |
answer = YES |
6 |
Correct |
0 ms |
348 KB |
answer = YES |
7 |
Correct |
0 ms |
344 KB |
answer = YES |
8 |
Correct |
0 ms |
348 KB |
answer = YES |
9 |
Correct |
0 ms |
344 KB |
answer = NO |
10 |
Correct |
0 ms |
348 KB |
answer = YES |
11 |
Correct |
0 ms |
348 KB |
answer = YES |
12 |
Correct |
0 ms |
348 KB |
answer = NO |
13 |
Correct |
0 ms |
348 KB |
answer = YES |
14 |
Correct |
0 ms |
348 KB |
answer = YES |
15 |
Correct |
0 ms |
344 KB |
answer = YES |
16 |
Correct |
0 ms |
348 KB |
answer = YES |
17 |
Correct |
0 ms |
348 KB |
answer = YES |
18 |
Correct |
0 ms |
344 KB |
answer = YES |
19 |
Correct |
0 ms |
348 KB |
answer = YES |
20 |
Correct |
0 ms |
348 KB |
answer = YES |
21 |
Correct |
0 ms |
348 KB |
answer = YES |
22 |
Correct |
0 ms |
348 KB |
answer = NO |
23 |
Correct |
0 ms |
348 KB |
answer = NO |
24 |
Correct |
1 ms |
348 KB |
answer = YES |
25 |
Correct |
0 ms |
348 KB |
answer = YES |
26 |
Incorrect |
0 ms |
348 KB |
participant answer is larger than the answer of jury |
27 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
answer = YES |
2 |
Correct |
0 ms |
348 KB |
answer = YES |
3 |
Correct |
0 ms |
348 KB |
answer = YES |
4 |
Correct |
0 ms |
348 KB |
answer = NO |
5 |
Correct |
0 ms |
348 KB |
answer = YES |
6 |
Correct |
0 ms |
348 KB |
answer = YES |
7 |
Correct |
0 ms |
344 KB |
answer = YES |
8 |
Correct |
0 ms |
348 KB |
answer = YES |
9 |
Correct |
0 ms |
344 KB |
answer = NO |
10 |
Correct |
0 ms |
348 KB |
answer = YES |
11 |
Correct |
0 ms |
348 KB |
answer = YES |
12 |
Correct |
0 ms |
348 KB |
answer = NO |
13 |
Correct |
0 ms |
348 KB |
answer = YES |
14 |
Correct |
0 ms |
348 KB |
answer = YES |
15 |
Correct |
0 ms |
344 KB |
answer = YES |
16 |
Correct |
0 ms |
348 KB |
answer = YES |
17 |
Correct |
0 ms |
348 KB |
answer = YES |
18 |
Correct |
0 ms |
344 KB |
answer = YES |
19 |
Correct |
0 ms |
348 KB |
answer = YES |
20 |
Correct |
0 ms |
348 KB |
answer = YES |
21 |
Correct |
0 ms |
348 KB |
answer = YES |
22 |
Correct |
0 ms |
348 KB |
answer = NO |
23 |
Correct |
0 ms |
348 KB |
answer = NO |
24 |
Correct |
1 ms |
348 KB |
answer = YES |
25 |
Correct |
0 ms |
348 KB |
answer = YES |
26 |
Incorrect |
0 ms |
348 KB |
participant answer is larger than the answer of jury |
27 |
Halted |
0 ms |
0 KB |
- |