Submission #23686

#TimeUsernameProblemLanguageResultExecution timeMemory
23686kdh9949Toll (APIO13_toll)C++14
100 / 100
1696 ms24696 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; struct Edg{ int s, e, c, i; bool operator<(const Edg &oth) const { return c < oth.c; } }; int n, m, k, s[21], e[21], p[100010], wh[100010], ch[300022], chk[22], par[22], pc[22], dep[22], mi, cnt; ll sp[22], a[22], ans; vector<Edg> av, v, sv, t[100010], st[22], nv; struct Dsu{ int p[100010]; void ini(int n){ for(int i = 1; i <= n; i++) p[i] = i; } int fnd(int x){ return p[x] = (x == p[x] ? x : fnd(p[x])); } void uni(int x, int y){ p[fnd(x)] = fnd(y); } } D; void bld(){ sort(v.begin(), v.end()); D.ini(n); for(auto &i : v){ if(D.fnd(i.s) == D.fnd(i.e)) continue; D.uni(i.s, i.e); t[i.s].push_back(i); t[i.e].push_back({i.e, i.s, i.c, i.i}); ch[i.i] = 1; } for(int i = 1; i <= k; i++) v.push_back({s[i], e[i], 0, m + i}); sort(v.begin(), v.end()); D.ini(n); for(auto &i : v){ if(D.fnd(i.s) == D.fnd(i.e)) continue; D.uni(i.s, i.e); if(ch[i.i]) ch[i.i] = 0; } for(int i = 1; i <= m; i++) if(ch[i]) sv.push_back(av[i - 1]); } void sdfs(int x, int pv, int id){ wh[x] = id; sp[id] += (ll)p[x]; for(auto &i : t[x]){ if(i.e == pv) continue; if(ch[i.i]) continue; sdfs(i.e, x, id); } } ll adfs(int x, int p, int d){ a[x] = sp[x]; dep[x] = d; for(auto &i : st[x]){ if(i.e == p) continue; a[x] += adfs(i.e, x, d + 1); par[i.e] = x; pc[i.e] = 1e9; chk[i.e] = i.i; } return a[x]; } ll f(int x){ D.ini(cnt); for(int i = 1; i <= cnt; i++) st[i].clear(); nv.clear(); for(int i = 1; i <= k; i++){ if(x & (1 << (i - 1))){ if(D.fnd(s[i]) == D.fnd(e[i])) return 0; D.uni(s[i], e[i]); st[s[i]].push_back({s[i], e[i], 0, 1}); st[e[i]].push_back({e[i], s[i], 0, 1}); } } for(auto &i : sv){ if(D.fnd(i.s) == D.fnd(i.e)) nv.push_back(i); else{ D.uni(i.s, i.e); st[i.s].push_back({i.s, i.e, 0, 0}); st[i.e].push_back({i.e, i.s, 0, 0}); } } adfs(1, 0, 0); for(auto &i : nv){ if(dep[i.s] < dep[i.e]) swap(i.s, i.e); while(dep[i.s] != dep[i.e]){ pc[i.s] = min(pc[i.s], i.c); i.s = par[i.s]; } while(i.s != i.e){ pc[i.s] = min(pc[i.s], i.c); pc[i.e] = min(pc[i.e], i.c); i.s = par[i.s]; i.e = par[i.e]; } } ll ret = 0; for(int i = 2; i <= cnt; i++){ if(chk[i]) ret += pc[i] * a[i]; } return ret; } int main(){ scanf("%d%d%d", &n, &m, &k); for(int i = 1, x, y, c; i <= m; i++){ scanf("%d%d%d", &x, &y, &c); v.push_back({x, y, c, i}); } av = v; for(int i = 1; i <= k; i++){ scanf("%d%d", s + i, e + i); } for(int i = 1; i <= n; i++) scanf("%d", p + i); bld(); for(int i = 1; i <= n; i++){ if(!wh[i]){ sdfs(i, 0, ++cnt); } } for(int i = 1; i <= k; i++){ s[i] = wh[s[i]]; e[i] = wh[e[i]]; } for(auto &i : sv){ i.s = wh[i.s]; i.e = wh[i.e]; } sort(sv.begin(), sv.end()); for(int i = 1; i <= (1 << k); i++) ans = max(ans, f(i)); printf("%lld\n", ans); }

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:111:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &k);
                             ^
toll.cpp:113:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &x, &y, &c);
                              ^
toll.cpp:118:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", s + i, e + i);
                              ^
toll.cpp:120:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= n; i++) scanf("%d", p + i);
                                                ^
#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...