oj.uz

Submission #946256

# Submission time Handle Problem Language Result Execution time Memory
946256 2024-03-14T13:08:09 Z PM1 LOSTIKS (INOI20_lostiks) C++17
36 / 100
 764 ms 231228 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<<20);
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][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(ans<1e9);
	cout<<ans;
	return 0;
}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27256 KB Output is correct
2 Correct 6 ms 27228 KB Output is correct
3 Correct 54 ms 41372 KB Output is correct
4 Correct 57 ms 42708 KB Output is correct
5 Correct 70 ms 43272 KB Output is correct
6 Correct 54 ms 42836 KB Output is correct
7 Correct 57 ms 42776 KB Output is correct
8 Correct 57 ms 42748 KB Output is correct
9 Correct 62 ms 43140 KB Output is correct
10 Correct 58 ms 42772 KB Output is correct
11 Correct 62 ms 42852 KB Output is correct
12 Correct 59 ms 44356 KB Output is correct
13 Correct 72 ms 43956 KB Output is correct
14 Correct 64 ms 43320 KB Output is correct
15 Incorrect 59 ms 44476 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 5 ms 27228 KB Output is correct
2 Correct 6 ms 27228 KB Output is correct
3 Correct 6 ms 27236 KB Output is correct
4 Correct 6 ms 27228 KB Output is correct
5 Correct 164 ms 130844 KB Output is correct
6 Correct 125 ms 130752 KB Output is correct
7 Correct 162 ms 130760 KB Output is correct
8 Correct 130 ms 130740 KB Output is correct
9 Correct 137 ms 130784 KB Output is correct
10 Correct 94 ms 130900 KB Output is correct
11 Correct 92 ms 130900 KB Output is correct
12 Correct 94 ms 130852 KB Output is correct
13 Correct 96 ms 130776 KB Output is correct
14 Correct 94 ms 131076 KB Output is correct
15 Correct 125 ms 130756 KB Output is correct
16 Correct 155 ms 130900 KB Output is correct
17 Correct 140 ms 130732 KB Output is correct
18 Correct 96 ms 130952 KB Output is correct
19 Correct 95 ms 130996 KB Output is correct
20 Correct 93 ms 130900 KB Output is correct
21 Correct 89 ms 130900 KB Output is correct
22 Correct 95 ms 131156 KB Output is correct
23 Correct 91 ms 131156 KB Output is correct
24 Correct 96 ms 131156 KB Output is correct
25 Correct 764 ms 231228 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27256 KB Output is correct
2 Correct 6 ms 27228 KB Output is correct
3 Correct 54 ms 41372 KB Output is correct
4 Correct 57 ms 42708 KB Output is correct
5 Correct 70 ms 43272 KB Output is correct
6 Correct 54 ms 42836 KB Output is correct
7 Correct 57 ms 42776 KB Output is correct
8 Correct 57 ms 42748 KB Output is correct
9 Correct 62 ms 43140 KB Output is correct
10 Correct 58 ms 42772 KB Output is correct
11 Correct 62 ms 42852 KB Output is correct
12 Correct 59 ms 44356 KB Output is correct
13 Correct 72 ms 43956 KB Output is correct
14 Correct 64 ms 43320 KB Output is correct
15 Incorrect 59 ms 44476 KB Output isn't correct
16 Halted 0 ms 0 KB -