제출 #355302

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
355302		kshitij_sodani	Training (IOI07_training)	C++14	30 / 100	50 ms	45932 KiB

training

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
llo n,m;
vector<llo> adj[2001];
vector<pair<pair<llo,llo>,llo>> pre[2001];
vector<pair<llo,llo>> pre2[2001];
vector<pair<llo,llo>> pre3[2001];
vector<llo> pre4[2001];
llo dp[2001][5001];
llo par[2001][20];
llo lev[2001];
llo st[2001];
llo ww[5001];
llo endd[2001];
llo val[2001][2001];
llo val2[2001];
llo co=0;
llo dp2[2001];
llo ind2[2001];
void dfs(llo no,llo par2=-1,llo levv=0){
	//cout<<no<<",,"<<par2<<endl;
	par[no][0]=par2;//par2;
	lev[no]=levv;
	st[no]=co;
	co++;
	for(auto j:adj[no]){
		if(j!=par2){
			dfs(j,no,levv+1);
		}
	}
	endd[no]=co-1;
}
/*llo tree[2001];
void u(llo i,llo j){
	while(i<=2000){
		tree[i]+=j;
		i+=(i&-i);
	}
}
llo ss(llo i){
	llo su=0;
	while(i>0){
		su+=tree[i];
		i-=(i&-i);
	}
	return su;
}*/
void dfs2(llo no,llo par=-1){
	llo su=0;
	vector<llo> ac;
	for(auto j:adj[no]){
		if(j!=par){
			dfs2(j,no);
			su+=dp[j][0];
			ind2[j]=ac.size();
			ac.pb(j);
		}
	}
	dp[no][0]=su;
	for(auto j:ac){
		val2[j]=0;
		for(auto i:ac){
			val[j][i]=0;
		}
	}
	for(auto j:pre3[no]){
		val2[j.a]=max(val2[j.a],dp[j.a][j.b]+ww[j.b]);
	}
	for(auto j:pre[no]){
		val[j.a.a][j.a.b]=max(val[j.a.a][j.a.b],dp[j.a.a][j.b]+dp[j.a.b][j.b]+ww[j.b]);
		val[j.a.b][j.a.a]=val[j.a.a][j.a.b];
	}

	if(ac.size()){
		llo nn=ac.size();
		for(llo j=0;j<(1<<nn);j++){
			dp2[j]=0;
			for(llo i=0;i<nn;i++){
				if((1<<i)&j){
					dp2[j]=max(dp2[j],val2[ac[i]]+dp2[j-(1<<i)]);
				}
			}
			for(llo i=0;i<nn;i++){
				for(llo k=i+1;k<nn;k++){
					if((j&(1<<i)) and (j&(1<<k))){
						dp2[j]=max(dp2[j],dp2[j-(1<<i)-(1<<k)]+val[ac[i]][ac[k]]);
					}
				}
			}
		}
		dp[no][0]=max(dp[no][0],dp2[(1<<nn)-1]);
		for(auto j:pre2[no]){
			dp[no][j.b]=max(dp[no][j.b],dp2[(1<<nn)-1-(1<<ind2[j.a])]+dp[j.a][j.b]);
		}
	}
	for(auto j:pre4[no]){
		dp[no][j]=max(dp[no][j],dp[no][0]);
	}



	

/*	for(auto j:adj[no]){
		if(j!=par){
			u(st[no]+2,dp[j]);
			u(endd[no]+2,-dp[j]);
			u(st[j]+1,-dp[j]);
			u(endd[no]+2,dp[j]);
		}
	}*/
	/*llo xy=0;
	for(auto j:pre[no]){
		llo aa=j.a.a;
		llo bb=j.a.b;
		if(bb==no){
			swap(aa,bb);
		}
		if(aa==no){
			dp[no]=max(dp[no],ss(st[bb]+1)+j.b);
		}
		else{
			llo cur=j.b;
			cur+=ss(st[bb]+1);
			cur+=ss(st[aa]+1);
			cur-=dp[pre2[no][xy].a];
			cur-=dp[pre2[no][xy].b];
			dp[no]=max(dp[no],cur);
		}
		xy++;
	}*/
	/*for(int i=0;i<=m-(n-1);i++){
		cout<<dp[no][i]<<",";
	}
	cout<<endl;
	cout<<no<<","<<dp[no][0]<<endl;*/
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	vector<pair<pair<llo,llo>,llo>> ed;
	for(llo i=0;i<m;i++){
		llo aa,bb,cc;
		cin>>aa>>bb>>cc;
		aa--;
		bb--;
		if(cc==0){
			adj[aa].pb(bb);
			adj[bb].pb(aa);
		}
		else{
			ed.pb({{aa,bb},cc});
		}
	}
	/*llo cur=0;
	for(llo i=0;i<n;i++){
		if(adj[i].size()==1){
			cur=i;
		}
	}*/
/*	for(llo i=0;i<n;i++){
		cout<<par[i][0]<<":";
	}
	cout<<endl;*/
	dfs(0);
	/*for(llo i=0;i<n;i++){
		cout<<par[i][0]<<":";
	}
	cout<<endl;
*/
	for(llo j=1;j<20;j++){
		for(llo i=0;i<n;i++){
			if(par[i][j-1]==-1){
				par[i][j]=-1;
			}
			else{
				par[i][j]=par[par[i][j-1]][j-1];
			}
		}
	}
	llo ans=0;

	llo xy=0;;
	for(auto j:ed){
		xy++;
		ww[xy]=j.b;
		if((lev[j.a.a]+lev[j.a.b])%2==1){
			ans+=j.b;
		}
		else{
			llo aa=j.a.a;
			llo bb=j.a.b;
			if(lev[aa]>lev[bb]){
				swap(aa,bb);
			}
			llo aa2=aa;
			llo bb2=bb;
			llo dif=lev[bb]-lev[aa];
			for(llo j=0;j<20;j++){
				if((1<<j)&dif){
					bb=par[bb][j];
				}
			}
			if(aa==bb){
				llo cur=bb2;

				while(par[cur][0]!=aa){
					pre2[par[cur][0]].pb({cur,xy});
					cur=par[cur][0];
				}
				pre3[aa].pb({cur,xy});
				pre4[bb2].pb(xy);
			//	pre[aa2].pb({{aa2,bb2},j.b});
			//	pre2[aa2].pb({-1,-1});
			//	cout<<aa2<<","<<bb2<<","<<-1<<endl;
			}
			else{

				for(llo j=19;j>=0;j--){
					if(par[aa][j]!=par[bb][j]){
						aa=par[aa][j];
						bb=par[bb][j];
					}
				}
				llo xx=par[aa][0];
				llo cur=aa2;
				while(cur!=aa){
					pre2[par[cur][0]].pb({cur,xy});
					cur=par[cur][0];
				}
				cur=bb2;
				while(cur!=bb){
					pre2[par[cur][0]].pb({cur,xy});
					cur=par[cur][0];
				}
				pre[par[aa][0]].pb({{aa,bb},xy});

				pre4[aa2].pb(xy);
				pre4[bb2].pb(xy);

				/*pre[par[aa][0]].pb({{aa2,bb2},j.b});
				pre2[par[aa][0]].pb({aa,bb});*/
				//cout<<aa2<<","<<bb2<<","<<aa<<","<<bb<<","<<par[aa][0]<<endl;
			}


		/*	if(ind[j.a.a]<ind[j.a.b]){
				pre[j.a.b].pb({j.a.a,j.b});
			}
			else{
				pre[j.a.a].pb({j.a.b,j.b});
			}*/
			ans+=j.b;
		}
	}
	dfs2(0);

/*	for(llo i=0;i<n;i++){

		for(auto j:pre[ss[i]]){
			dp[i+1]=max(dp[i+1],dp[ind[j.a]]+j.b);
			ans+=j.b;
		}
		dp[i+1]=max(dp[i+1],dp[i]);
	}*/
	ans-=dp[0][0];
	cout<<ans<<endl;





	
 
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

training.cpp: In function 'int main()':
training.cpp:234:9: warning: unused variable 'xx' [-Wunused-variable]
  234 |     llo xx=par[aa][0];
      |         ^~

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