| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 859325 |
2023-10-10T04:09:53 Z |
maks007 |
Graph (BOI20_graph) |
C++14 |
|
700 ms |
460 KB |
#include "bits/stdc++.h"
using namespace std;
#define int long long
signed main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector <pair <int, double>> g[n];
vector <double> node(n, (double)1e9), ans(n);
double mn = 1e9;
function<void(int)> dfs=[&](int v) {
node[v] = 0;
for(auto [i, j] : g[v]) {
if(!node[i]) continue;
dfs(i);
}
};
function<void(int)> rec=[&](int i) {
// cout << i << " ";
if(i==n) {
for(int j = 0; j < n; j ++) {
for(auto [k, w] : g[j]) {
if(node[k] + node[j] == w) continue;
return;
}
}
double sum = 0.0;
for(auto i : node) sum += fabs(i);
// cout << mn << " ";
if(sum < mn) {
ans = node;
mn = min(mn, sum);
}
return;
}
for(double val = -2; val < 3; val += 0.25) {
node[i] = val;
rec(i+1);
node[i] = 1e9;
}
};
for(int i = 0; i < m; i ++) {
int u, v;
cin >> u >> v;
u --, v --;
int w;
cin >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
int cnt = 0;
for(int i = 0; i < n; i ++) {
if(!node[i]) continue;
cnt ++;
dfs(i);
}
assert(cnt <= 5);
for(auto &j : node) j = 1e9;
rec(0);
if(mn == 1e9) {
cout << "NO\n";
return 0;
}
cout << "YES" << "\n";
for(auto i : ans) cout << fixed << setprecision(6) << i << " ";
return 0;
}
Compilation message
Graph.cpp: In lambda function:
Graph.cpp:17:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
17 | for(auto [i, j] : g[v]) {
| ^
Graph.cpp: In lambda function:
Graph.cpp:26:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
26 | for(auto [k, w] : g[j]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 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 |
24 ms |
348 KB |
answer = YES |
| 6 |
Correct |
0 ms |
348 KB |
answer = YES |
| 7 |
Correct |
0 ms |
348 KB |
answer = YES |
| 8 |
Correct |
2 ms |
348 KB |
answer = YES |
| 9 |
Correct |
1 ms |
456 KB |
answer = NO |
| 10 |
Correct |
2 ms |
456 KB |
answer = YES |
| 11 |
Correct |
1 ms |
348 KB |
answer = YES |
| 12 |
Correct |
1 ms |
348 KB |
answer = NO |
| 13 |
Correct |
28 ms |
436 KB |
answer = YES |
| 14 |
Correct |
25 ms |
456 KB |
answer = YES |
| 15 |
Correct |
25 ms |
456 KB |
answer = YES |
| 16 |
Correct |
23 ms |
348 KB |
answer = YES |
| 17 |
Correct |
0 ms |
344 KB |
answer = YES |
| 18 |
Correct |
0 ms |
460 KB |
answer = YES |
| 19 |
Correct |
0 ms |
348 KB |
answer = YES |
| 20 |
Correct |
0 ms |
348 KB |
answer = YES |
| 21 |
Correct |
1 ms |
348 KB |
answer = YES |
| 22 |
Correct |
0 ms |
452 KB |
answer = NO |
| 23 |
Correct |
0 ms |
348 KB |
answer = NO |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 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 |
24 ms |
348 KB |
answer = YES |
| 6 |
Correct |
0 ms |
348 KB |
answer = YES |
| 7 |
Correct |
0 ms |
348 KB |
answer = YES |
| 8 |
Correct |
2 ms |
348 KB |
answer = YES |
| 9 |
Correct |
1 ms |
456 KB |
answer = NO |
| 10 |
Correct |
2 ms |
456 KB |
answer = YES |
| 11 |
Correct |
1 ms |
348 KB |
answer = YES |
| 12 |
Correct |
1 ms |
348 KB |
answer = NO |
| 13 |
Correct |
28 ms |
436 KB |
answer = YES |
| 14 |
Correct |
25 ms |
456 KB |
answer = YES |
| 15 |
Correct |
25 ms |
456 KB |
answer = YES |
| 16 |
Correct |
23 ms |
348 KB |
answer = YES |
| 17 |
Correct |
0 ms |
344 KB |
answer = YES |
| 18 |
Correct |
0 ms |
460 KB |
answer = YES |
| 19 |
Correct |
0 ms |
348 KB |
answer = YES |
| 20 |
Correct |
0 ms |
348 KB |
answer = YES |
| 21 |
Correct |
1 ms |
348 KB |
answer = YES |
| 22 |
Correct |
0 ms |
452 KB |
answer = NO |
| 23 |
Correct |
0 ms |
348 KB |
answer = NO |
| 24 |
Execution timed out |
1036 ms |
344 KB |
Time limit exceeded |
| 25 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 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 |
24 ms |
348 KB |
answer = YES |
| 6 |
Correct |
0 ms |
348 KB |
answer = YES |
| 7 |
Correct |
0 ms |
348 KB |
answer = YES |
| 8 |
Correct |
2 ms |
348 KB |
answer = YES |
| 9 |
Correct |
1 ms |
456 KB |
answer = NO |
| 10 |
Correct |
2 ms |
456 KB |
answer = YES |
| 11 |
Correct |
1 ms |
348 KB |
answer = YES |
| 12 |
Correct |
1 ms |
348 KB |
answer = NO |
| 13 |
Correct |
28 ms |
436 KB |
answer = YES |
| 14 |
Correct |
25 ms |
456 KB |
answer = YES |
| 15 |
Correct |
25 ms |
456 KB |
answer = YES |
| 16 |
Correct |
23 ms |
348 KB |
answer = YES |
| 17 |
Correct |
0 ms |
344 KB |
answer = YES |
| 18 |
Correct |
0 ms |
460 KB |
answer = YES |
| 19 |
Correct |
0 ms |
348 KB |
answer = YES |
| 20 |
Correct |
0 ms |
348 KB |
answer = YES |
| 21 |
Correct |
1 ms |
348 KB |
answer = YES |
| 22 |
Correct |
0 ms |
452 KB |
answer = NO |
| 23 |
Correct |
0 ms |
348 KB |
answer = NO |
| 24 |
Execution timed out |
1036 ms |
344 KB |
Time limit exceeded |
| 25 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 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 |
24 ms |
348 KB |
answer = YES |
| 6 |
Correct |
0 ms |
348 KB |
answer = YES |
| 7 |
Correct |
0 ms |
348 KB |
answer = YES |
| 8 |
Correct |
2 ms |
348 KB |
answer = YES |
| 9 |
Correct |
1 ms |
456 KB |
answer = NO |
| 10 |
Correct |
2 ms |
456 KB |
answer = YES |
| 11 |
Correct |
1 ms |
348 KB |
answer = YES |
| 12 |
Correct |
1 ms |
348 KB |
answer = NO |
| 13 |
Correct |
28 ms |
436 KB |
answer = YES |
| 14 |
Correct |
25 ms |
456 KB |
answer = YES |
| 15 |
Correct |
25 ms |
456 KB |
answer = YES |
| 16 |
Correct |
23 ms |
348 KB |
answer = YES |
| 17 |
Correct |
0 ms |
344 KB |
answer = YES |
| 18 |
Correct |
0 ms |
460 KB |
answer = YES |
| 19 |
Correct |
0 ms |
348 KB |
answer = YES |
| 20 |
Correct |
0 ms |
348 KB |
answer = YES |
| 21 |
Correct |
1 ms |
348 KB |
answer = YES |
| 22 |
Correct |
0 ms |
452 KB |
answer = NO |
| 23 |
Correct |
0 ms |
348 KB |
answer = NO |
| 24 |
Execution timed out |
1036 ms |
344 KB |
Time limit exceeded |
| 25 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 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 |
24 ms |
348 KB |
answer = YES |
| 6 |
Correct |
0 ms |
348 KB |
answer = YES |
| 7 |
Correct |
0 ms |
348 KB |
answer = YES |
| 8 |
Correct |
2 ms |
348 KB |
answer = YES |
| 9 |
Correct |
1 ms |
456 KB |
answer = NO |
| 10 |
Correct |
2 ms |
456 KB |
answer = YES |
| 11 |
Correct |
1 ms |
348 KB |
answer = YES |
| 12 |
Correct |
1 ms |
348 KB |
answer = NO |
| 13 |
Correct |
28 ms |
436 KB |
answer = YES |
| 14 |
Correct |
25 ms |
456 KB |
answer = YES |
| 15 |
Correct |
25 ms |
456 KB |
answer = YES |
| 16 |
Correct |
23 ms |
348 KB |
answer = YES |
| 17 |
Correct |
0 ms |
344 KB |
answer = YES |
| 18 |
Correct |
0 ms |
460 KB |
answer = YES |
| 19 |
Correct |
0 ms |
348 KB |
answer = YES |
| 20 |
Correct |
0 ms |
348 KB |
answer = YES |
| 21 |
Correct |
1 ms |
348 KB |
answer = YES |
| 22 |
Correct |
0 ms |
452 KB |
answer = NO |
| 23 |
Correct |
0 ms |
348 KB |
answer = NO |
| 24 |
Execution timed out |
1036 ms |
344 KB |
Time limit exceeded |
| 25 |
Halted |
0 ms |
0 KB |
- |
