oj.uz

Submission #946272

# Submission time Handle Problem Language Result Execution time Memory
946272 2024-03-14T13:15:25 Z PM1 LOSTIKS (INOI20_lostiks) C++17
36 / 100
 793 ms 232492 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(dis[21][21]<1e9);
	cout<<ans;
	return 0;
}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27224 KB Output is correct
2 Correct 6 ms 27480 KB Output is correct
3 Correct 54 ms 41324 KB Output is correct
4 Correct 57 ms 41480 KB Output is correct
5 Correct 52 ms 41296 KB Output is correct
6 Correct 55 ms 41508 KB Output is correct
7 Correct 54 ms 41564 KB Output is correct
8 Correct 65 ms 41424 KB Output is correct
9 Correct 57 ms 41552 KB Output is correct
10 Correct 57 ms 41608 KB Output is correct
11 Correct 65 ms 41600 KB Output is correct
12 Correct 60 ms 42832 KB Output is correct
13 Correct 60 ms 42580 KB Output is correct
14 Correct 59 ms 42064 KB Output is correct
15 Incorrect 65 ms 43024 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 27340 KB Output is correct
3 Correct 6 ms 27228 KB Output is correct
4 Correct 6 ms 27228 KB Output is correct
5 Correct 149 ms 131040 KB Output is correct
6 Correct 135 ms 130792 KB Output is correct
7 Correct 167 ms 130684 KB Output is correct
8 Correct 128 ms 130640 KB Output is correct
9 Correct 139 ms 130736 KB Output is correct
10 Correct 92 ms 130692 KB Output is correct
11 Correct 96 ms 130640 KB Output is correct
12 Correct 94 ms 130644 KB Output is correct
13 Correct 91 ms 130712 KB Output is correct
14 Correct 93 ms 130692 KB Output is correct
15 Correct 125 ms 130704 KB Output is correct
16 Correct 159 ms 130796 KB Output is correct
17 Correct 147 ms 130644 KB Output is correct
18 Correct 96 ms 130900 KB Output is correct
19 Correct 101 ms 130836 KB Output is correct
20 Correct 96 ms 130824 KB Output is correct
21 Correct 94 ms 130924 KB Output is correct
22 Correct 92 ms 131308 KB Output is correct
23 Correct 92 ms 131172 KB Output is correct
24 Correct 93 ms 131176 KB Output is correct
25 Correct 793 ms 232492 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27224 KB Output is correct
2 Correct 6 ms 27480 KB Output is correct
3 Correct 54 ms 41324 KB Output is correct
4 Correct 57 ms 41480 KB Output is correct
5 Correct 52 ms 41296 KB Output is correct
6 Correct 55 ms 41508 KB Output is correct
7 Correct 54 ms 41564 KB Output is correct
8 Correct 65 ms 41424 KB Output is correct
9 Correct 57 ms 41552 KB Output is correct
10 Correct 57 ms 41608 KB Output is correct
11 Correct 65 ms 41600 KB Output is correct
12 Correct 60 ms 42832 KB Output is correct
13 Correct 60 ms 42580 KB Output is correct
14 Correct 59 ms 42064 KB Output is correct
15 Incorrect 65 ms 43024 KB Output isn't correct
16 Halted 0 ms 0 KB -