제출 #626689

#제출 시각아이디문제언어결과실행 시간메모리
626689messiuuuuu통행료 (APIO13_toll)C++14
16 / 100
1 ms1492 KiB
/// #include<bits/stdc++.h> #define task "C" #define ll long long #define ld long double #define fi first #define se second #define pb push_back using namespace std; const int MAXN = 3e5 + 5; const ll INF = 1e18 + 5; const int MAXK = 25; int n, k, m; struct TEdge { int u, v, w; }es[MAXN], more[21]; int a[MAXN]; void Input() { cin >> n >> m >> k; for (int i = 1; i <= m; i++) { cin >> es[i].u >> es[i].v >> es[i].w; } for (int i = 1; i <= k; i++) { cin >> more[i].u >> more[i].v; } for (int i = 1; i <= n; i++) cin >> a[i]; } int lab[MAXN], w[MAXK][MAXK], w1[MAXK][MAXK]; bool inmst[MAXN]; vector<pair<int, int>> Adj[MAXK]; ll lab1[MAXN], sum[MAXN], res; struct TRb { int u, v, labu, labv; ll lab1u, lab1v; }rb[MAXN]; int szrb = 0; void rollback(int sz) { while (szrb > sz) { auto top = rb[szrb]; lab[top.u] = top.labu; lab[top.v] = top.labv; lab1[top.u] = top.lab1u; lab1[top.v] = top.lab1v; szrb--; } } int FindSet(int u) { return lab[u] < 0 ? u : FindSet(lab[u]); } bool Unite(int u, int v) { u = FindSet(u); v = FindSet(v); if (u == v) return 0; if (lab[u] > lab[v]) swap(u, v); rb[++szrb] = {u, v, lab[u], lab[v], lab1[u], lab1[v]}; lab1[u] += lab1[v]; lab[u] += lab[v]; lab[v] = u; return 1; } void DFS(int u, int par, ll val) { sum[u] = lab1[u]; for (auto v : Adj[u]) { if (v.fi == par) continue; DFS(v.fi, u, val + v.se); sum[u] += sum[v.fi]; } res += val * sum[u]; } void resetDsu() { memset(lab, -1, sizeof(lab)); for (int i = 1; i <= n; i++) lab1[i] = a[i]; szrb = 0; } int ds[MAXN]; void Solve() { resetDsu(); for (int i = 1; i <= k; i++) { Unite(more[i].u, more[i].v); } sort(es + 1, es + 1 + m, [](const auto& i, const auto& j) { return i.w < j.w; }); for (int i = 1; i <= m; i++) { if (Unite(es[i].u, es[i].v)) { inmst[i] = 1; } } resetDsu(); for (int i = 1; i <= m; i++) { if (inmst[i]) { Unite(es[i].u, es[i].v); } } int tplt = 0; for (int i = 1; i <= n; i++) { int u = FindSet(i); if (!ds[u]) { ds[u] = ++tplt; } ds[i] = ds[u]; } for (int i = 1; i <= n; i++) { if (lab[i] < 0) { lab[ds[i]] = -1; lab1[ds[i]] = lab1[i]; } } assert(tplt < MAXK); vector<pair<int, int>> etplt; for (int i = 1; i <= m; i++) { if (!inmst[i]) { int u = FindSet(ds[es[i].u]), v = FindSet(ds[es[i].v]); if (u > v) swap(u, v); assert(u < MAXK && v < MAXK); if (!w[u][v]) { w[u][v] = es[i].w; etplt.pb({u, v}); } } } sort(etplt.begin(), etplt.end(), [](const auto& i, const auto& j) { return w[i.fi][i.se] < w[j.fi][j.se]; }); if (k > 1) return; ll ans = 0; for (int mask = 1; mask < (1 << k); mask++) { int sz = szrb; for (int i = 0; i < k; i++) { if (mask & (1 << i)) { Unite(ds[more[i + 1].u], ds[more[i + 1].v]); } } vector<int> in, out; for (int i = 0; i < etplt.size(); i++) { auto e = etplt[i]; if (Unite(e.fi, e.se)) { in.pb(i); } else { out.pb(i); } } rollback(sz); for (int i : in) { auto e = etplt[i]; Unite(e.fi, e.se); } for (int i : out) { auto e = etplt[i]; int u = FindSet(e.fi), v = FindSet(e.se); if (u > v) swap(u, v); assert(u < MAXK && v < MAXK); if (!w1[u][v]) w1[u][v] = w[u][v]; } for (int i = 0; i < k; i++) { if (mask & (1 << i)) { int r = FindSet(ds[more[i + 1].u]), s = FindSet(ds[more[i + 1].v]); if (r > s) swap(r, s); assert(r < MAXK && s < MAXK); Adj[r].pb({s, w1[r][s]}); Adj[s].pb({r, w1[r][s]}); } } res = 0; DFS(FindSet(ds[1]), 0, 0); ans = max(ans, res); rollback(sz); for (int i = 0; i < k; i++) { if (mask & (1 << i)) { int r = FindSet(ds[more[i + 1].u]), s = FindSet(ds[more[i + 1].v]); if (r > s) swap(r, s); assert(r < MAXK && s < MAXK); Adj[r].clear(); Adj[s].clear(); } } for (int i : out) { auto e = etplt[i]; int u = FindSet(e.fi), v = FindSet(e.se); if (u > v) swap(u, v); assert(u < MAXK && v < MAXK); w1[u][v] = 0; } } cout << ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); if (fopen(task".INP","r")) { freopen(task".INP","r",stdin); //freopen(task".OUT","w",stdout); } Input(); Solve(); }

컴파일 시 표준 에러 (stderr) 메시지

toll.cpp: In function 'void Solve()':
toll.cpp:188:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |         for (int i = 0; i < etplt.size(); i++)
      |                         ~~^~~~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:263:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  263 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...