제출 #37177

#제출 시각아이디문제언어결과실행 시간메모리
37177DoanPhuDuc통행료 (APIO13_toll)C++98
16 / 100
3 ms37676 KiB
#include <bits/stdc++.h> #define FOR(x, a, b) for (int x = a; x <= b; ++x) #define FOD(x, a, b) for (int x = a; x >= b; --x) #define REP(x, a, b) for (int x = a; x < b; ++x) #define DEBUG(X) { cout << #X << " = " << X << endl; } #define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; } #define PR0(A, n) { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; } #define BitCount(x) __builtin_popcount(x) using namespace std; typedef long long LL; typedef pair <int, int> II; typedef pair <LL, int> LLI; const int N = 1e5 + 10; int n, m, q; int a[N], h[N], b[N], wei[N], par[N]; int p[N][25], f[N][25]; bool fre[N]; LL ans = 0; LL c[N]; vector <II> pos[N]; vector <int> L; set <II> adj[N]; map <int, bool> change[N]; struct DSU { int p[N]; void Init() { memset(p, -1, sizeof p); } int Root(int u) { return p[u] < 0 ? u : p[u] = Root(p[u]); } bool Union(int u, int v) { u = Root(u); v = Root(v); if (u == v) return false; if (p[u] > p[v]) swap(u, v); p[u] += p[v]; p[v] = u; return true; } } DSU; struct Edge { int u, v, w; Edge () {} Edge (int u, int v, int w) : u(u), v(v), w(w) {} bool operator < (const Edge &that) const { return w < that.w; } } E[N]; void DFS(int u) { for (set <II> :: iterator it = adj[u].begin(); it != adj[u].end(); ++it) { int v = it -> first, w = it -> second; if (v == p[u][0]) continue; a[v] = w; h[v] = h[u] + 1; p[v][0] = u; f[v][0] = v; DFS(v); } } int InitLCA() { for (int j = 1; 1 << j <= n; ++j) FOR(i, 1, n) { p[i][j] = p[p[i][j - 1]][j - 1]; int x = f[i][j - 1], y = f[p[i][j - 1]][j - 1]; if (a[x] < a[y]) f[i][j] = y; else f[i][j] = x; } } II LCA(int u, int v) { if (h[u] < h[v]) swap(u, v); int k = 0; FOD(i, 20, 0) if (h[u] - (1 << i) >= h[v]) { if (a[f[u][i]] > a[k]) k = f[u][i]; u = p[u][i]; } if (u == v) return II(u, k); FOD(i, 20, 0) if (p[u][i] != p[v][i]) { if (a[f[u][i]] > a[k]) k = f[u][i]; if (a[f[v][i]] > a[k]) k = f[v][i]; u = p[u][i]; v = p[v][i]; } if (a[f[u][0]] > a[k]) k = f[u][0]; if (a[f[v][0]] > a[k]) k = f[v][0]; return II(p[u][0], k); } void DP(int u) { c[u] = b[u]; for (set <II> :: iterator it = adj[u].begin(); it != adj[u].end(); ++it) { int v = it -> first, w = it -> second; if (v == par[u]) continue; par[v] = u; wei[v] = w; if (change[u][v] == true) fre[v] = true; DP(v); c[u] += c[v]; } } LL Compute() { FOR(i, 1, n) fre[i] = false; DP(1); LL ans = 0; FOR(i, 1, n) if (fre[i] == true) ans += (LL)wei[i] * c[i]; return ans; } void Try(int i) { if (i >= L.size()) { ans = max(ans, Compute()); return; } Try(i + 1); int pu = p[L[i]][0], pv = L[i]; adj[pu].erase(II(pv, a[L[i]])); adj[pv].erase(II(pu, a[L[i]])); REP(k, 0, pos[L[i]].size()) { int u = pos[L[i]][k].first, v = pos[L[i]][k].second; adj[u].insert(II(v, a[L[i]])); adj[v].insert(II(u, a[L[i]])); change[u][v] = change[v][u] = true; Try(i + 1); change[u][v] = change[v][u] = false; adj[u].erase(II(v, a[L[i]])); adj[v].erase(II(u, a[L[i]])); } } int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif // LOCAL scanf("%d%d%d", &n, &m, &q); FOR(i, 1, m) { int u, v, w; scanf("%d%d%d", &u, &v, &w); E[i] = Edge(u, v, w); } sort(E + 1, E + m + 1); DSU.Init(); FOR(i, 1, m) { int u = E[i].u, v = E[i].v, w = E[i].w; if (DSU.Union(u, v) == true) { adj[u].insert(II(v, w)); adj[v].insert(II(u, w)); } } DFS(1); InitLCA(); FOR(i, 1, q) { int x, y; scanf("%d%d", &x, &y); II res = LCA(x, y); pos[res.second].push_back(II(x, y)); } FOR(i, 1, n) scanf("%d", &b[i]); FOR(i, 1, n) if (pos[i].size()) L.push_back(i); Try(0); cout << ans; return 0; }

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

toll.cpp: In function 'int InitLCA()':
toll.cpp:80:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
toll.cpp: In function 'void Try(int)':
toll.cpp:122:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i >= L.size()) {
           ^
toll.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
toll.cpp:130:5: note: in expansion of macro 'REP'
     REP(k, 0, pos[L[i]].size()) {
     ^
toll.cpp: In function 'int main()':
toll.cpp:147:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &q);
                                ^
toll.cpp:149:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v, w; scanf("%d%d%d", &u, &v, &w);
                                                 ^
toll.cpp:164:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x, y; scanf("%d%d", &x, &y);
                                        ^
toll.cpp:168:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 1, n) scanf("%d", &b[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...