Submission #575154

#	Time	Username	Problem	Language	Result	Execution time	Memory
575154		Antekb	Training (IOI07_training)	C++14	100 / 100	54 ms	24636 KiB

training

#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
using pii = pair<int, int>;
const int K=10, N=1<<K;
vector<int> E[N], lca[N];
int id[N], d[N], par[N], pre[N], post[N];
int wsk;
int opt[N][K][K];//?
int dp[N][1<<K];//used subtrees
int dp2[N][5*N];//vert, out edg
int n, m;
vector<pair<int, pii > > edg, edg2;
vector<int> dob;
void dfs(int v, int p){
	pre[v]=wsk++;
	par[v]=p;
	d[v]=d[p]+1;
	for(int i=0; i<E[v].size(); i++)if(E[v][i]==p)swap(E[v][i], E[v].back());
	if(p!=0)E[v].pop_back();
	for(int i=0; i<E[v].size(); i++){
		id[E[v][i]]=i;
		dfs(E[v][i], v);
	}
	post[v]=wsk;
}
void dfs2(int v){
	for(int u:E[v]){
		dfs2(u);
		dp[v][1<<id[u]]=dp2[u][0];
	}
	for(int e:lca[v]){
		int u=edg[e].nd.st, w=edg[e].nd.nd;
		while(par[w]!=v)w=par[w];
		if(u==v){
			dp[v][1<<id[w]]=max(edg[e].st + dp2[w][e], dp[v][1<<id[w]]);
		}
		else{
			while(par[u]!=v)u=par[u];
			if(v==1 && e==7){
				//cout<<id[u]<<" "<<id[w]<<"\n";
				//cout<<dp2[u][e]<<" "<<dp2[w][e]<<"\n";
				//cout<<edg2[7].nd.st<<" "<<edg2[7].nd.nd<<"\n";
			}
			dp[v][(1<<id[u])+(1<<id[w])]=max(edg[e].st+dp2[u][e]+dp2[w][e], dp[v][(1<<id[u])+(1<<id[w])]);
		}
	}
	for(int i=0; i<(1<<E[v].size()); i++){
		for(int j=i; ; j=(j-1)&i){
			dp[v][i]=max(dp[v][i], dp[v][j]+dp[v][i-j]);
			if(j==0)break;
		}
	}
	for(int e:dob){
		if(edg[e].nd.st==v && pre[edg[e].nd.nd]>=post[v]){
			dp2[v][e]=dp[v][(1<<E[v].size())-1];
		}
		if(edg[e].nd.nd==v){
			dp2[v][e]=dp[v][(1<<E[v].size())-1];
		}
		if(par[edg2[e].nd.st]==v ^ par[edg2[e].nd.nd]==v){
			if(par[edg2[e].nd.st]==v){
				if(v==2 && e==7){
					//cout<<"a";
					//cout<<dp2[edg2[e].nd.st][e]<<" "<<dp[v][(1<<E[v].size())-1-(1<<id[edg2[e].nd.st])]<<" ";
				}
				dp2[v][e]=dp[v][(1<<E[v].size())-1-(1<<id[edg2[e].nd.st])]+dp2[edg2[e].nd.st][e];
				if(v==2 && e==7){
					//cout<<dp2[v][e];
				}
				edg2[e].nd.st=v;
			}
			if(par[edg2[e].nd.nd]==v){
				dp2[v][e]=dp[v][(1<<E[v].size())-1-(1<<id[edg2[e].nd.nd])]+dp2[edg2[e].nd.nd][e];
				edg2[e].nd.nd=v;
			}
		}
	}
	dp2[v][0]=dp[v][(1<<E[v].size())-1];
}
int main(){
	cin>>n>>m;
	int sum=0;
	for(int i=0; i<m; i++){
		int u, v, w;
		cin>>u>>v>>w;
		sum+=w;
		edg.push_back({w, {u, v}});
		if(w==0){
			E[u].push_back(v);
			E[v].push_back(u);
		}
	}
	dfs(1, 0);
	sort(edg.begin(), edg.end());
	for(int i=n-1; i<m; i++){
		if(pre[edg[i].nd.st]>pre[edg[i].nd.nd])swap(edg[i].nd.st, edg[i].nd.nd);
		int u=edg[i].nd.st, v=edg[i].nd.nd;
		if((d[u]&1)!=(d[v]&1)){
			continue;
		}
		if(d[u]<d[v])swap(u, v);
		while(d[u]>d[v]){
			u=par[u];
		}
		while(u!=v){
			u=par[u];
			v=par[v];
		}
		dob.push_back(i);
		lca[u].push_back(i);
	}
	edg2=edg;
	dfs2(1);
	/*for(int i=1; i<=n; i++){
		cout<<i<<" "<<E[i].size()<<"\n";
		for(int j=0; j<(1<<E[i].size()); j++)cout<<dp[i][j]<<" ";
		cout<<"\n";
		for(int j=0; j<edg.size(); j++)cout<<dp2[i][j]<<" ";
			cout<<"\n";
	}*/
	cout<<sum-dp2[1][0];
}

Compilation message (stderr)

training.cpp: In function 'void dfs(int, int)':
training.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i=0; i<E[v].size(); i++)if(E[v][i]==p)swap(E[v][i], E[v].back());
      |               ~^~~~~~~~~~~~
training.cpp:22:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i=0; i<E[v].size(); i++){
      |               ~^~~~~~~~~~~~
training.cpp: In function 'void dfs2(int)':
training.cpp:62:24: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   62 |   if(par[edg2[e].nd.st]==v ^ par[edg2[e].nd.nd]==v){
      |      ~~~~~~~~~~~~~~~~~~^~~

• 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