| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 859407 |
2023-10-10T06:04:40 Z |
maks007 |
Graph (BOI20_graph) |
C++14 |
|
1 ms |
604 KB |
#include "bits/stdc++.h"
using namespace std;
#define int long long
vector <vector <pair <int,int>>> g;
vector <int> used;
vector <int> comp;
#define int long long
void dfs(int v) {
used[v] = 1;
for(auto [i, j] : g[v]) {
if(used[i] == LLONG_MAX) dfs(i);
}
}
void get_comps() {
for(int i = 0; i < used.size(); i ++) {
if(used[i] == LLONG_MAX) {
dfs(i);
comp.push_back(i);
}
}
}
int check(int v) {
int f = 1;
for(auto [i, j] : g[v]) {
if(used[i] == LLONG_MAX) {
used[i] = j - used[v];
f = min(f, check(i));
}else {
if(used[i] + used[v] != j) f = 0;
}
}
return f;
}
vector <pair <int,int>> rec(int v) {
int mn = LLONG_MAX;
vector <pair <int,int>> ans;
for(int val = -1000; val <= 1000; val += 1) {
for(auto &j : used) j = LLONG_MAX;
used[v] = val;
if(check(v)) {
int cnt = 0;
for(auto &j : used) {
if(j == LLONG_MAX) continue;
cnt += abs(j);
}
if(cnt <= mn) {
mn = cnt;
for(int j = 0; j < used.size(); j ++) {
if(used[j] == LLONG_MAX) continue;
ans.push_back({j, used[j]});
}
}
}
// cout << val << " ";
// if(val == 0.5) {
// for(auto j : used) cout << j << " ";
// }
}
if(mn == LLONG_MAX) {
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, LLONG_MAX);
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*1000});
g[v].push_back({u, w*1000});
}
get_comps();
// assert(comp.size() < 2);
for(auto &j : used) j = LLONG_MAX;
vector <vector <pair <int,int>>> res;
for(auto i : comp) {
res.push_back(rec(i));
}
cout << "YES\n";
vector <int> ans(n);
for(auto i : res) {
for(auto j : i) ans[j.first] = j.second;
}
for(auto i : ans) cout << fixed << setprecision(6) << (double)i*0.001 << " ";
return 0;
}
Compilation message
Graph.cpp: In function 'void dfs(long long int)':
Graph.cpp:15:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
15 | for(auto [i, j] : g[v]) {
| ^
Graph.cpp: In function 'void get_comps()':
Graph.cpp:21:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(int i = 0; i < used.size(); i ++) {
| ~~^~~~~~~~~~~~~
Graph.cpp: In function 'long long int check(long long int)':
Graph.cpp:31:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
31 | for(auto [i, j] : g[v]) {
| ^
Graph.cpp: In function 'std::vector<std::pair<long long int, long long int> > rec(long long int)':
Graph.cpp:56:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int j = 0; j < used.size(); j ++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
answer = YES |
| 2 |
Correct |
0 ms |
604 KB |
answer = YES |
| 3 |
Correct |
0 ms |
344 KB |
answer = YES |
| 4 |
Correct |
0 ms |
600 KB |
answer = NO |
| 5 |
Correct |
0 ms |
604 KB |
answer = YES |
| 6 |
Correct |
0 ms |
604 KB |
answer = YES |
| 7 |
Correct |
0 ms |
348 KB |
answer = YES |
| 8 |
Correct |
1 ms |
600 KB |
answer = YES |
| 9 |
Correct |
0 ms |
348 KB |
answer = NO |
| 10 |
Incorrect |
0 ms |
348 KB |
jury has the better answer: jans = YES, pans = NO |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
answer = YES |
| 2 |
Correct |
0 ms |
604 KB |
answer = YES |
| 3 |
Correct |
0 ms |
344 KB |
answer = YES |
| 4 |
Correct |
0 ms |
600 KB |
answer = NO |
| 5 |
Correct |
0 ms |
604 KB |
answer = YES |
| 6 |
Correct |
0 ms |
604 KB |
answer = YES |
| 7 |
Correct |
0 ms |
348 KB |
answer = YES |
| 8 |
Correct |
1 ms |
600 KB |
answer = YES |
| 9 |
Correct |
0 ms |
348 KB |
answer = NO |
| 10 |
Incorrect |
0 ms |
348 KB |
jury has the better answer: jans = YES, pans = NO |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
answer = YES |
| 2 |
Correct |
0 ms |
604 KB |
answer = YES |
| 3 |
Correct |
0 ms |
344 KB |
answer = YES |
| 4 |
Correct |
0 ms |
600 KB |
answer = NO |
| 5 |
Correct |
0 ms |
604 KB |
answer = YES |
| 6 |
Correct |
0 ms |
604 KB |
answer = YES |
| 7 |
Correct |
0 ms |
348 KB |
answer = YES |
| 8 |
Correct |
1 ms |
600 KB |
answer = YES |
| 9 |
Correct |
0 ms |
348 KB |
answer = NO |
| 10 |
Incorrect |
0 ms |
348 KB |
jury has the better answer: jans = YES, pans = NO |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
answer = YES |
| 2 |
Correct |
0 ms |
604 KB |
answer = YES |
| 3 |
Correct |
0 ms |
344 KB |
answer = YES |
| 4 |
Correct |
0 ms |
600 KB |
answer = NO |
| 5 |
Correct |
0 ms |
604 KB |
answer = YES |
| 6 |
Correct |
0 ms |
604 KB |
answer = YES |
| 7 |
Correct |
0 ms |
348 KB |
answer = YES |
| 8 |
Correct |
1 ms |
600 KB |
answer = YES |
| 9 |
Correct |
0 ms |
348 KB |
answer = NO |
| 10 |
Incorrect |
0 ms |
348 KB |
jury has the better answer: jans = YES, pans = NO |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
answer = YES |
| 2 |
Correct |
0 ms |
604 KB |
answer = YES |
| 3 |
Correct |
0 ms |
344 KB |
answer = YES |
| 4 |
Correct |
0 ms |
600 KB |
answer = NO |
| 5 |
Correct |
0 ms |
604 KB |
answer = YES |
| 6 |
Correct |
0 ms |
604 KB |
answer = YES |
| 7 |
Correct |
0 ms |
348 KB |
answer = YES |
| 8 |
Correct |
1 ms |
600 KB |
answer = YES |
| 9 |
Correct |
0 ms |
348 KB |
answer = NO |
| 10 |
Incorrect |
0 ms |
348 KB |
jury has the better answer: jans = YES, pans = NO |
| 11 |
Halted |
0 ms |
0 KB |
- |
