Submission #1222644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222644		sam230609	Training (IOI07_training)	C++20	100 / 100	8 ms	4680 KiB

training

#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];
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 7 / 7
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9