oj.uz

Submission #946277

# Submission time Handle Problem Language Result Execution time Memory
946277 2024-03-14T13:17:13 Z PM1 LOSTIKS (INOI20_lostiks) C++17
36 / 100
 787 ms 232604 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fr first
#define sc second
const int mxn=1e6+5,sz=(1<<22);
int n,dis[40][40],par[mxn][22],c[mxn],key[25],door[25],cnt=0,d[mxn];
ll dp[sz][25],ans=1e9;
vector<pair<int,int>>v[mxn];
void dfs(int z,int f=0){
	for(int i=1;i<=20;i++)
		par[z][i]=par[par[z][i-1]][i-1];
	for(auto i:v[z]){
		if(par[z][0]!=i.fr){
			par[i.fr][0]=z;
			c[i.fr]=c[z];
			d[i.fr]=d[z]+1;
			if(i.sc){
				door[++cnt]=z;
				key[cnt]=i.sc;
				c[i.fr]|=(1<<(cnt-1));
			}
			dfs(i.fr);
		}
	}
}
int lca(int x,int y){
	if(x==0 || y==0)return 0;
	if(d[x]<d[y])swap(x,y);
	int res=0;
	for(int i=20;i>=0;i--){
		if((1<<i)<=d[x]-d[y])x=par[x][i],res+=(1<<i);
	}
	if(x==y)return res;
	for(int i=20;i>=0;i--){
		if(par[x][i]!=par[y][i])x=par[x][i],y=par[y][i],res+=(1<<(i+1));
	}
	return res+2;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	cin>>door[21]>>key[21];
	for(int i=1;i<n;i++){
		int x,y,w;
		cin>>x>>y>>w;
		v[x].push_back({y,w});
		v[y].push_back({x,w});
	}
	dfs(door[21]);
	for(int i=1;i<=21;i++){
		for(int j=1;j<=21;j++){
			dis[i][j]=lca(door[i],key[j]);
		}
	}
	for(int i=0;i<cnt;i++){
		if(!c[door[i+1]] && !c[key[i+1]])
			dp[(1<<i)][i]=dis[21][i+1]+dis[i+1][i+1];
		else
			dp[(1<<i)][i]=1e9;
	}
	for(int i=1;i<(1<<cnt);i++){
		for(int j=0;j<cnt;j++){
			if(__builtin_popcount(i)!=1)dp[i][j]=1e9;
			if((i&(1<<j)) && (i&c[door[j+1]])==c[door[j+1]] && (i&c[key[j+1]])==c[key[j+1]]) {
				for(int w=0;w<cnt;w++){
					if(i&(1<<w)){
						if(w!=j  && dp[i-(1<<j)][w]!=1e9){
							dp[i][j]=min(dp[i][j],dis[j+1][j+1]+dis[w+1][j+1]+dp[i-(1<<j)][w]);
							
						}
					}
				}
				if((i&(c[key[21]]))==c[key[21]]){
					ans=min(ans,dp[i][j]+dis[j+1][21]);
				}
			}
		}
	
	}
	if(c[key[21]]==0)ans=dis[21][21];
	assert(cnt<=20);
	cout<<ans;
	return 0;
}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27340 KB Output is correct
2 Correct 6 ms 27344 KB Output is correct
3 Correct 67 ms 41428 KB Output is correct
4 Correct 64 ms 41364 KB Output is correct
5 Correct 68 ms 41304 KB Output is correct
6 Correct 77 ms 41400 KB Output is correct
7 Correct 79 ms 41608 KB Output is correct
8 Correct 68 ms 41592 KB Output is correct
9 Correct 63 ms 41792 KB Output is correct
10 Correct 55 ms 41436 KB Output is correct
11 Correct 79 ms 41604 KB Output is correct
12 Correct 76 ms 43008 KB Output is correct
13 Correct 75 ms 42456 KB Output is correct
14 Correct 73 ms 42116 KB Output is correct
15 Incorrect 77 ms 43164 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27228 KB Output is correct
2 Correct 6 ms 27228 KB Output is correct
3 Correct 6 ms 27228 KB Output is correct
4 Correct 6 ms 27260 KB Output is correct
5 Correct 149 ms 130748 KB Output is correct
6 Correct 127 ms 130692 KB Output is correct
7 Correct 166 ms 130660 KB Output is correct
8 Correct 143 ms 130640 KB Output is correct
9 Correct 144 ms 130644 KB Output is correct
10 Correct 94 ms 130808 KB Output is correct
11 Correct 95 ms 130644 KB Output is correct
12 Correct 91 ms 130640 KB Output is correct
13 Correct 93 ms 130640 KB Output is correct
14 Correct 95 ms 130796 KB Output is correct
15 Correct 129 ms 130640 KB Output is correct
16 Correct 157 ms 130668 KB Output is correct
17 Correct 141 ms 130656 KB Output is correct
18 Correct 96 ms 130900 KB Output is correct
19 Correct 102 ms 130900 KB Output is correct
20 Correct 92 ms 130896 KB Output is correct
21 Correct 91 ms 130968 KB Output is correct
22 Correct 93 ms 131148 KB Output is correct
23 Correct 91 ms 131152 KB Output is correct
24 Correct 92 ms 131288 KB Output is correct
25 Correct 787 ms 232604 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27340 KB Output is correct
2 Correct 6 ms 27344 KB Output is correct
3 Correct 67 ms 41428 KB Output is correct
4 Correct 64 ms 41364 KB Output is correct
5 Correct 68 ms 41304 KB Output is correct
6 Correct 77 ms 41400 KB Output is correct
7 Correct 79 ms 41608 KB Output is correct
8 Correct 68 ms 41592 KB Output is correct
9 Correct 63 ms 41792 KB Output is correct
10 Correct 55 ms 41436 KB Output is correct
11 Correct 79 ms 41604 KB Output is correct
12 Correct 76 ms 43008 KB Output is correct
13 Correct 75 ms 42456 KB Output is correct
14 Correct 73 ms 42116 KB Output is correct
15 Incorrect 77 ms 43164 KB Output isn't correct
16 Halted 0 ms 0 KB -