Submission #897683

#TimeUsernameProblemLanguageResultExecution timeMemory
897683LudisseyTraining (IOI07_training)C++14
20 / 100
442 ms524288 KiB
#include <bits/stdc++.h> using namespace std; int n,m; const int LOG=11; #define LSOne(S) (S & (-S)) vector<vector<int>> paved; vector<vector<int>> child; vector<vector<int>> indN; vector<vector<pair<int,int>>> memo2; vector<int> depth; vector<vector<int>> parent; vector<vector<pair<pair<int,int>,int>>> edges; vector<vector<int>> memo; vector<int> maskCalc; int lca(int a, int b){ if(depth[b]>depth[a]) swap(a,b); int k=depth[a]-depth[b]; for (int j = LOG-1; j >= 0; j--) if(k&(1<<j)) a=parent[a][j]; if(a==b) return a; for (int j = LOG-1; j >= 0; j--) { if(parent[a][j]!=parent[b][j]) { a=parent[a][j]; b=parent[b][j]; } } return parent[a][0]; } int dp(int x, int mask, int prev){ if(memo[x][mask]!=-1) return memo[x][mask]; if(child[x].size()==0) return memo[x][mask]=0; int mx=0; if(prev==-1){ if(maskCalc[x]==-1){ for (int i = 0; i < child[x].size(); i++) { if((mask&(1<<i))!=0) continue; mx+=dp(child[x][i],0,-1); } maskCalc[x]=mx; }else{ int dfMask=mask; mx=maskCalc[x]; while(dfMask>0) { int ls=LSOne(dfMask); mx-=dp(child[x][ls-1],0,-1); dfMask-=(1<<(ls-1)); } } } prev=mx; for(auto u : edges[x]) { int a=u.first.first; int b=u.first.second; int c=u.second; int d=(depth[a]+depth[b])-2*depth[x]; if(d%2!=0) continue; if(memo2[a][b].first==-1){ int ap=a; int bp=b; int sum=0; while((parent[ap][0]!=x&&ap!=x)||(parent[bp][0]!=x&&bp!=x)){ if((parent[ap][0]!=x&&ap!=x)){ int bitmaskA=(1<<indN[parent[ap][0]][ap]); sum+=dp(parent[ap][0],bitmaskA,-1); ap=parent[ap][0]; } if((parent[bp][0]!=x&&bp!=x)){ int bitmaskB=(1<<indN[parent[bp][0]][bp]); sum+=dp(parent[bp][0],bitmaskB,-1); bp=parent[bp][0]; } } int bitmask=0; if(a!=x) { sum+=dp(a,0,-1); bitmask+=(1<<indN[x][ap]); } if(b!=x) { sum+=dp(b,0,-1); bitmask+=(1<<indN[x][bp]); } memo2[a][b]={sum,bitmask}; } if((memo2[a][b].second&mask)!=0) continue; int new_prev=prev; if(a!=x) new_prev-=dp(a,0,-1); if(b!=x) new_prev-=dp(b,0,-1); mx=max(mx,memo2[a][b].first+c+dp(x,memo2[a][b].second,new_prev)); } return memo[x][mask]=mx; } signed main() { // Input: ios::sync_with_stdio(false); cin.tie(nullptr); cin>>n>>m; paved.resize(n+1); depth.resize(n+1); maskCalc.resize(n+1,-1); parent.resize(n+1, vector<int>(LOG, 0)); indN.resize(n+1, vector<int>(n+1, -1)); memo2.resize(n+1, vector<pair<int,int>>(n+1,{-1,-1})); memo.resize(n+1, vector<int>(pow(2,10)+1,-1)); edges.resize(n+1); child.resize(n+1); int sum=0; vector<pair<pair<int,int>, int>> edgesTOPROCESS; for (int i = 0; i < m; i++) { int a,b,c; cin >> a >> b >> c; sum+=c; if(a>b) swap(a,b); if(c==0) { paved[a].push_back(b); paved[b].push_back(a); } else { edgesTOPROCESS.push_back({{a,b},c}); } } queue<int> q; q.push(1); parent[1][0]=1; depth[1]=0; vector<bool> visited(n+1); while(!q.empty()){ int x=q.front(); q.pop(); visited[x]=true; for (auto u: paved[x]) { if(visited[u]) continue; q.push(u); indN[x][u]=child[x].size(); child[x].push_back(u); parent[u][0]=x; depth[u]=depth[x]+1; } } for (int j = 1; j < LOG; j++) for (int i = 1; i <= n; i++) parent[i][j]=parent[parent[i][j-1]][j-1]; for (int i = 0; i < m-(n-1); i++) { int a=edgesTOPROCESS[i].first.first; int b=edgesTOPROCESS[i].first.second; int c=edgesTOPROCESS[i].second; int lc=lca(a,b); int d=(depth[a]+depth[b])-2*depth[lc]; if(d%2!=0) continue; edges[lc].push_back({{a,b},c}); } cout << sum-dp(1,0,-1) << "\n"; return 0; }

Compilation message (stderr)

training.cpp: In function 'int dp(int, int, int)':
training.cpp:38:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             for (int i = 0; i < child[x].size(); 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...
#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...