제출 #1222644

#제출 시각아이디문제언어결과실행 시간메모리
1222644sam230609Training (IOI07_training)C++20
100 / 100
8 ms4680 KiB
#include <bits/stdc++.h> using namespace std; int n,m,sum,jump[1001][11],deg[1001],order[1001],lvl[1001],ptr,dp[1001][1<<10],mask1,mask2; pair<int,int> par[1001]; vector<int> paths[1001]; struct Edge{ int a,b,c,lca; bool operator <(Edge x) const {return order[lca]<order[x.lca];} }; vector <Edge> edges; void dfs(int pos=1, int p=1){ jump[pos][0]=p; for(auto el:paths[pos]){ if(el==p) continue; lvl[el]=lvl[pos]+1; par[el]={pos,1<<(deg[pos]++)}; dfs(el,pos); }order[pos]=ptr++; } int Jump(int a, int b){ for(int j=0;j<=10;j++) if(b&(1<<j)) a=jump[a][j]; return a; } int LCA(int a, int b){ if(lvl[a]<lvl[b]) swap(a,b); a=Jump(a,lvl[a]-lvl[b]); if(a==b) return a; for(int j=10;j>=0;j--) if(jump[a][j]!=jump[b][j]) a=jump[a][j],b=jump[b][j]; return jump[a][0]; } void solve(){ for(auto edge:edges){ int a=edge.a,b=edge.b,cur=edge.c,lca=edge.lca; if(lvl[a]%2 != lvl[b]%2 && cur!=0) continue; for(mask1=0; a!=lca; tie(a,mask1)=par[a]) cur+=dp[a][mask1]; for(mask2=0; b!=lca; tie(b,mask2)=par[b]) cur+=dp[b][mask2]; mask1|=mask2; for(int mask=(1<<deg[lca])-1;mask>=0;mask--){ if(mask&mask1) continue; dp[lca][mask]=max(dp[lca][mask],cur+dp[lca][mask|mask1]); } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >>n>>m; for(int i=1;i<=m;i++){ int a,b,c; cin >>a>>b>>c; if(!c){ paths[a].push_back(b); paths[b].push_back(a); }sum+=c; edges.push_back({a,b,c,0}); }par[1]={1,0}; dfs(); for(int j=1;j<=10;j++) for(int i=1;i<=n;i++) jump[i][j]=jump[jump[i][j-1]][j-1]; for(auto &edge:edges){ if(lvl[edge.a]%2 != lvl[edge.b]%2 && edge.c!=0) continue; edge.lca=LCA(edge.a,edge.b); }sort(edges.begin(),edges.end()); solve(); cout <<sum-dp[1][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...