oj.uz

답안 #355347

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
355347 2021-01-22T11:44:14 Z kshitij_sodani Training (IOI07_training) C++14
100 / 100
 78 ms 66668 KB 
//#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[5001];
vector<pair<pair<llo,llo>,llo>> pre[5001];
vector<pair<llo,llo>> pre2[5001];
vector<pair<llo,llo>> pre3[5001];
vector<llo> pre4[2001];
llo dp[5001][5001];
llo par[5001][20];
llo lev[5001];
llo st[5001];
llo ww[5001];
llo endd[5001];
llo val[5001][5001];
llo val2[5001];
llo co=0;
llo dp2[5001];
llo ind2[5001];
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]=dp[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];
			}

		}
	}
/*	cout<<par[5][1]<<",,"<<par[5][0]<<",,"<<par[2][0]<<endl;
	cout<<par[par[5][0]][0]<<endl;*/
	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];
		//	cout<<aa<<"::::"<<bb<<",,"<<dif<<endl;;
			for(llo j=0;j<20;j++){
				if((1<<j)&dif){
					bb=par[bb][j];
				}
			}
		//	cout<<aa<<"::::"<<bb<<endl;
			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});
				//cout<<aa<<",,,"<<cur<<endl;
				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;



	//cout<<dp[1][0]<<","<<endl;

	//cout<<dp[2][0]<<","<<endl;
 	//cout<<par[2][0]<<endl;
	return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1004 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1420 KB Output is correct
2 Correct 1 ms 1516 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 31980 KB Output is correct
2 Correct 35 ms 35052 KB Output is correct

Subtask #4
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1004 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1260 KB Output is correct
2 Correct 1 ms 1132 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1900 KB Output is correct
2 Correct 2 ms 1900 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4716 KB Output is correct
2 Correct 5 ms 5356 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 13164 KB Output is correct
2 Correct 11 ms 13216 KB Output is correct
3 Correct 12 ms 13056 KB Output is correct

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 37760 KB Output is correct
2 Correct 30 ms 35564 KB Output is correct
3 Correct 27 ms 37484 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 11216 KB Output is correct
2 Correct 13 ms 15084 KB Output is correct
3 Correct 53 ms 49004 KB Output is correct
4 Correct 18 ms 16672 KB Output is correct

Subtask #11
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 45932 KB Output is correct
2 Correct 78 ms 66668 KB Output is correct
3 Correct 47 ms 46188 KB Output is correct
4 Correct 35 ms 37612 KB Output is correct