Submission #859460

#TimeUsernameProblemLanguageResultExecution timeMemory
859460maks007Graph (BOI20_graph)C++14
17 / 100
3 ms2512 KiB
#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 = -100; val <= 100; 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*10}); g[v].push_back({u, w*10}); } 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) printf("%.6lf ", i*0.1); return 0; }

Compilation message (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...