Submission #696052

#	Time	Username	Problem	Language	Result	Execution time	Memory
696052		vjudge1	Training (IOI07_training)	C++14	100 / 100	30 ms	20592 KiB

training

#include<bits/stdc++.h>
using namespace std;
int n,m,U[5010],V[5010],W[5010],lc[5010];
vector<int>g[1010],t[1010],q[5010];
int d[1010],f[1010];
void dfs(int x){
	for(int v:g[x])if(v!=f[x])f[v]=x,d[v]=d[x]+1,dfs(v); 
}
int lca(int u,int v){
	while(u!=v){if(d[u]<d[v])swap(u,v);u=f[u];}
	return u;
}
const int I=1e9+10;
int e[1<<10],c,so[12],z[12],is[1010];
int dp[1010][5010];
void ad(int &x,int y){x=max(x,y);}
int ok(int u,int x){
	while(d[u]-1>d[x])u=f[u];
	return u;
}
int all;
void dfs2(int x){
	for(int v:g[x])if(v!=f[x])dfs2(v);
	c=0;
	for(int v:g[x])if(v!=f[x])so[c++]=v;
	e[0]=0;
	for(int i=1;i<(1<<c);i++)e[i]=-I;
	for(int i=0;i<c;i++){
		int v=so[i],M=-I;
		is[v]=i;
		for(int j=0;j<=m;j++)ad(M,dp[v][j]);
		for(int s=0;s<(1<<c);s++)if(!((s>>i)&1))ad(e[s|(1<<i)],e[s]+M);
	}
	for(int o:t[x]){
		if(d[U[o]]<d[V[o]])swap(U[o],V[o]);
		if(V[o]==lc[o]){
			int a=ok(U[o],lc[o]);
			int z=dp[a][o]+W[o];
			for(int s=0;s<(1<<c);s++)if(!((s>>is[a])&1))ad(e[s|(1<<is[a])],e[s]+z);
		}
		else{
			int a=ok(U[o],lc[o]),b=ok(V[o],lc[o]);
			int z=dp[a][o]+dp[b][o]+W[o];
			for(int s=0;s<(1<<c);s++)if(!((s>>is[a])&1)&&!((s>>is[b])&1))
			ad(e[s|(1<<is[a])|(1<<is[b])],e[s]+z);
		}
	}
	if(x==1){
		printf("%d",all-e[(1<<c)-1]);
		return;
	}
	for(int i=0;i<=m;i++)dp[x][i]=-I;
	dp[x][0]=e[(1<<c)-1];
	for(int i:q[x])dp[x][i]=e[(1<<c)-1];
	for(int i=0;i<c;i++){
		int v=so[i];
		for(int j=1;j<=m;j++)ad(dp[x][j],e[((1<<c)-1)^(1<<i)]+dp[v][j]);
	}
	
}
int main(){
	memset(dp,0x3f,sizeof(dp));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&U[i],&V[i],&W[i]),all+=W[i];
		if(!W[i])g[U[i]].push_back(V[i]),g[V[i]].push_back(U[i]);
	}
	dfs(1);
	for(int i=1;i<=m;i++)if(W[i]&&!((d[U[i]]+d[V[i]])&1)){
		t[lc[i]=lca(U[i],V[i])].push_back(i);
		q[U[i]].push_back(i),q[V[i]].push_back(i); 
	}
	dfs2(1);
	return 0;
} 

Compilation message (stderr)

training.cpp: In function 'int main()':
training.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
training.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   scanf("%d%d%d",&U[i],&V[i],&W[i]),all+=W[i];
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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