제출 #512636

#제출 시각아이디문제언어결과실행 시간메모리
512636blueTraining (IOI07_training)C++17
100 / 100
33 ms1612 KiB
#include <iostream> #include <cassert> #include <vector> #include <algorithm> using namespace std; const int maxN = 1'000; const int logN = 10; using vi = vector<int>; using pii = pair<int, int>; using vvi = vector<vi>; #define sz(x) int(x.size()) struct trail { int a; int b; int c; }; int N, M; vector<trail> trails; vi edge[1+maxN]; vi par(1+maxN, 0); vvi anc(1+maxN, vi(1+logN, 0)); vector< vector< vi > > desc(1+maxN, vector<vi>(1+logN)); vi depth(1+maxN, 0); void dfs(int u) { for(int v: edge[u]) { if(v == par[u]) continue; par[v] = u; depth[v] = 1 + depth[u]; dfs(v); } } int ancestor(int u, int k) { for(int e = 0; e <= logN; e++) if(k & (1 << e)) u = anc[u][e]; return u; } int lca(int u, int v) { if(depth[u] > depth[v]) swap(u, v); v = ancestor(v, depth[v] - depth[u]); if(u == v) return u; for(int e = logN; e >= 0; e--) { if(anc[u][e] == anc[v][e]) continue; u = anc[u][e]; v = anc[v][e]; } return anc[u][0]; } struct vtrail { int v; int c; }; vector<vtrail> v_trails[1+maxN]; vector<trail> h_trails[1+maxN]; int basicCost = 0; int defaultCost = 0; vi strict(1+maxN, 0); vi loose(1+maxN, 0); vvi loose_lift(1+maxN, vi(1+logN, 0)); vi child_loose_sum(1+maxN, 0); vvi dp(1+maxN); int loose_query(int u, int k) { int ans = 0; for(int e = 0; e <= logN; e++) { if(k & (1 << e)) { ans += loose_lift[u][e]; u = anc[u][e]; } } return ans; } void binary_lift(int u, int e) { loose_lift[u][e] = loose_lift[anc[u][e-1]][e-1] + loose_lift[u][e-1]; for(int v: desc[u][e]) binary_lift(v, e+1); } vi inv_pow(2000); vi child_ind(1+maxN); void final_dfs(int u) { for(int v: desc[u][0]) { final_dfs(v); child_loose_sum[u] += loose[v]; } int z = sz(desc[u][0]); if(z > 0) { dp[u] = vi((1<<z), 0); for(int i = 0; i < z; i++) child_ind[desc[u][0][i]] = i; vi trail_occ[z]; int tz = sz(h_trails[u]); vi lc(tz), rc(tz); for(int i = 0; i < tz; i++) { lc[i] = child_ind[ancestor(h_trails[u][i].a, depth[h_trails[u][i].a] - depth[u] - 1)]; rc[i] = child_ind[ancestor(h_trails[u][i].b, depth[h_trails[u][i].b] - depth[u] - 1)]; if(lc[i] > rc[i]) swap(lc[i], rc[i]); trail_occ[lc[i]].push_back(i); trail_occ[rc[i]].push_back(i); } dp[u][0] = 0; for(int mask = 1; mask < (1<<z); mask++) { if(mask == (mask & -mask)) { dp[u][mask] = loose[ desc[u][0][ inv_pow[mask] ] ]; } else { int lb = inv_pow[mask & -mask]; dp[u][mask] = dp[u][mask - (mask&-mask)] + loose[ desc[u][0][lb] ]; for(int ti: trail_occ[lb]) { if(!(mask & (1 << rc[ti]))) continue; if(!(mask & (1 << lc[ti]))) continue; int newval = dp[u][mask - (1<<lc[ti]) - (1<<rc[ti])]; int a = h_trails[u][ti].a; int b = h_trails[u][ti].b; int c = h_trails[u][ti].c; newval += strict[a] + loose_query(a, depth[a] - depth[u] - 1); newval += strict[b] + loose_query(b, depth[b] - depth[u] - 1); newval += c; dp[u][mask] = max(dp[u][mask], newval); } } } strict[u] = dp[u][(1<<z) - 1]; for(int i = 0; i < z; i++) { int v = desc[u][0][i]; loose_lift[v][0] = dp[u][(1<<z) - 1 - (1<<i)]; for(int v2: desc[v][0]) binary_lift(v2, 1); } } loose[u] = strict[u]; for(vtrail vt: v_trails[u]) { loose[u] = max(loose[u], loose_query(vt.v, depth[vt.v] - depth[u]) + strict[vt.v] + vt.c); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> N >> M; for(int e = 1; e <= M; e++) { int a, b; int c; cin >> a >> b >> c; if(c != 0) trails.push_back({a, b, c}); else { edge[a].push_back(b); edge[b].push_back(a); } } dfs(1); for(int i = 1; i <= N; i++) anc[i][0] = par[i]; for(int e = 1; e <= logN; e++) for(int i = 0; i <= N; i++) anc[i][e] = anc[ anc[i][e-1] ][e-1]; for(int i = 0; i <= N; i++) for(int e = 0; e <= logN; e++) if(anc[i][e] != 0) desc[anc[i][e]][e].push_back(i); for(auto& t: trails) { if(depth[t.a] % 2 != depth[t.b] % 2) { basicCost += t.c; continue; } defaultCost += t.c; int l = lca(t.a, t.b); if(l == t.a) { v_trails[ancestor(t.b, depth[t.b] - depth[t.a] - 1)].push_back({t.b, t.c}); } else if(l == t.b) { v_trails[ancestor(t.a, depth[t.a] - depth[t.b] - 1)].push_back({t.a, t.c}); } else h_trails[l].push_back(t); } for(int e = 0; e < 10; e++) inv_pow[(1<<e)] = e; final_dfs(1); cout << basicCost + (defaultCost - strict[1]) << '\n'; }
#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...
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...