Submission #598766

#	Time	Username	Problem	Language	Result	Execution time	Memory
598766		Bobaa	Training (IOI07_training)	C++17	0 / 100	1093 ms	512 KiB

training

#include<bits/stdc++.h>
using namespace std;

#define st first
#define nd second

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 dp[N][1<<K];
int dp2[N][5*N];
int n, m;
vector<pair<int, pair<int, int>>> edg, edg2;
vector<int> dob;

void dfs(int v, int p){
	pre[v]=wsk++;
	par[v]=p;
	d[v]=d[p]+1;
	int sz=E[v].size(); 
	for(int i=0; i<sz; 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<sz; 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];
			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){
				dp2[v][e]=dp[v][(1<<E[v].size())-1-(1<<id[edg2[e].nd.st])]+dp2[edg2[e].nd.st][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(){
	ios_base::sync_with_stdio(false); 
	cin.tie(nullptr); 
	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);
	cout<<sum-dp2[1][0];
}

Compilation message (stderr)

training.cpp: In function 'void dfs2(int)':
training.cpp:53:24: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   53 |   if(par[edg2[e].nd.st]==v ^ par[edg2[e].nd.nd]==v){
      |      ~~~~~~~~~~~~~~~~~~^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 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