oj.uz

Submission #696052

# Submission time Handle Problem Language Result Execution time Memory
696052 2023-02-05T09:23:15 Z vjudge1 Training (IOI07_training) C++14
100 / 100
 30 ms 20592 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20180 KB Output is correct
2 Correct 8 ms 20280 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20288 KB Output is correct
2 Correct 10 ms 20296 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 20428 KB Output is correct
2 Correct 18 ms 20564 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20288 KB Output is correct
2 Correct 9 ms 20228 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20256 KB Output is correct
2 Correct 10 ms 20288 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20260 KB Output is correct
2 Correct 8 ms 20284 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20308 KB Output is correct
2 Correct 14 ms 20292 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20344 KB Output is correct
2 Correct 13 ms 20424 KB Output is correct
3 Correct 14 ms 20352 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 20540 KB Output is correct
2 Correct 24 ms 20556 KB Output is correct
3 Correct 23 ms 20552 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20436 KB Output is correct
2 Correct 14 ms 20428 KB Output is correct
3 Correct 30 ms 20436 KB Output is correct
4 Correct 29 ms 20328 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 20592 KB Output is correct
2 Correct 30 ms 20564 KB Output is correct
3 Correct 25 ms 20580 KB Output is correct
4 Correct 24 ms 20508 KB Output is correct