Submission #899365

#TimeUsernameProblemLanguageResultExecution timeMemory
899365NonozeTraining (IOI07_training)C++17
30 / 100
19 ms24668 KiB
#include <bits/stdc++.h> #define int long long #define sz(x) (int)(x.size()) using namespace std; const int LOG=12; int n, m; //LSONE int LSOne(int i) { return i&(-i); } //LCA vector<vector<int>> child; vector<vector<int>> up; vector<int> depth; void dfs(int s, int last=-1) { for (auto u: child[s]) { if (u==last) continue; depth[u]=depth[s]+1; up[u][0]=s; for (int i=1; i<LOG; i++) { up[u][i]=up[ up[u][i-1] ][ i-1 ]; } dfs(u, s); } } int getlca(int a, int b) { if (a==b) return a; if (depth[a] < depth[b]) swap(a, b); int k = depth[a] - depth[b]; for (int j = LOG-1; j >= 0; j--) { if (k & (1<<j)) { a=up[a][j]; } } if (a==b) return a; for (int j = LOG-1; j >= 0; j--) { if (up[a][j] != up[b][j]) { a=up[a][j]; b=up[b][j]; } } return up[a][0]; } //DP vector<vector<int>> memo; vector<vector<pair<pair<int, int>, int>>> adj; vector<vector<int>> val; vector<vector<int>> memo2; int dp(int s, int mask) { if (__builtin_popcount(mask)>=child[s].size()) return 0; if (memo[s][mask]!=-1) return memo[s][mask]; int ans=0; if (mask==0) { for (auto u: child[s]) { ans=max(ans, dp(u, 0)); } } for (auto u: adj[s]) { int a=u.first.first, b=u.first.second, c=u.second; if (mask&val[a][b]) continue; if (memo2[a][b]!=-1) { int sum=memo2[a][b]; ans=max(ans, sum+dp(s, (mask|val[a][b]))); continue; } int aa=a, bb=b; int sum=c; int prec=-1; while (a!=s) { int bitmask=0; for (int i=0; i<sz(child[a]); i++) { if (child[a][i]==prec) { bitmask+=(1<<i); } } sum+=dp(a, bitmask); prec=a; a=up[a][0]; } prec=-1; while (b!=s) { int bitmask=0; for (int i=0; i<sz(child[b]); i++) { if (child[b][i]==prec) { bitmask+=(1<<i); } } sum+=dp(b, bitmask); prec=b; b=up[b][0]; } memo2[aa][bb]=sum; ans=max(ans, sum+dp(s, (mask|val[aa][bb]))); } return memo[s][mask]=ans; } void solve() { cin >> n >> m; memo.clear(); memo.resize(n, vector<int>(1<<10, -1)); memo2.clear(); memo2.resize(n, vector<int>(n, -1)); val.clear(); val.resize(n, vector<int>(n)); adj.clear(); adj.resize(n); child.clear(); child.resize(n); up.clear(); up.resize(n, vector<int>(LOG)); depth.clear(); depth.resize(n); vector<pair<pair<int, int>, int>> temp; vector<int> vaut(n+5); for (int i=0; i<m; i++) { int u, v, c; cin >> u >> v >> c; u--, v--; if (c==0) { child[u].push_back(v); child[v].push_back(u); } else { temp.push_back({{u, v}, c}); } } depth[0]=0; dfs(0); for (int s=0; s<n; s++) { for (int i=0; i<sz(child[s]); i++) { auto u=child[s][i]; if (u==up[s][0]) { child[s].erase(child[s].begin()+i); } } } int ans=0; for (auto tempp: temp) { int u=tempp.first.first, v=tempp.first.second; int c=tempp.second; int lca=getlca(u, v); if (u!=v && (depth[u]+depth[v]-2*depth[lca])%2==0) { adj[lca].push_back({{u, v}, c}); val[u][v]=0; for (int j=0; j<sz(child[lca]); j++) { auto s=child[lca][j]; if (getlca(s, u)==s || getlca(s, v)==s) { val[u][v]+=(1<<j); } } } ans+=c; } cout << ans-dp(0, 0) << endl; return; } signed main() { ios::sync_with_stdio(0); cin.tie(0); int tt=1;// cin >> tt; while(tt--) solve(); return 0; }
#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...