oj.uz

Submission #914051

# Submission time Handle Problem Language Result Execution time Memory
914051 2024-01-21T00:10:29 Z Jasiekstrz LOSTIKS (INOI20_lostiks) C++17
100 / 100
 1823 ms 288468 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e6;
const int M=20;
const int INF=1e9+7;
vector<pair<int,int>> e[N+10];
int dep[N+10];
int jmp[N+10][M+2];
int keys[N+10];
int doors[M+10];
int dp[(1<<M)+10][M+2];
int dk[M+2][M+2];
int wh_k[M+2];
int wh_d[M+2];
void find_doors(int x,int p,int msk,int t)
{
	if(x==t)
		doors[M]=msk;
	dep[x]=dep[p]+1;
	jmp[x][0]=p;
	for(int i=1;jmp[x][i-1]!=-0;i++)
		jmp[x][i]=jmp[jmp[x][i-1]][i-1];
	for(int i=0;i<M;i++)
	{
		if(keys[x]&(1<<i))
			doors[i]|=msk;
	}
	for(auto [v,c]:e[x])
	{
		if(v==p)
			continue;
		for(int i=0;i<M;i++)
		{
			if(c&(1<<i))
			{
				wh_d[i]=x;
				doors[i]|=msk;
			}
		}
		find_doors(v,x,msk|c,t);
	}
	return;
}
int dis(int x,int y)
{
	int ans=0;
	if(dep[x]<dep[y])
		swap(x,y);
	for(int i=M;i>=0;i--)
	{
		if(dep[jmp[x][i]]>=dep[y])
		{
			x=jmp[x][i];
			ans+=(1<<i);
		}
	}
	if(x==y)
		return ans;
	for(int i=M;i>=0;i--)
	{
		if(jmp[x][i]!=jmp[y][i])
		{
			x=jmp[x][i];
			y=jmp[y][i];
			ans+=(2<<i);
		}
	}
	return ans+2;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m=0;
	int s,t;
	int ans=INF;
	cin>>n;
	cin>>s>>t;
	for(int i=1;i<n;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		if(c!=0)
		{
			wh_k[m]=c;
			keys[c]|=(1<<m);
			c=(1<<m);
			m++;
		}
		e[a].emplace_back(b,c);
		e[b].emplace_back(a,c);
	}
	find_doors(s,0,0,t);
	wh_k[m]=t;
	wh_d[m]=s;
	for(int i=0;i<=m;i++)
	{
		for(int j=0;j<=m;j++)
			dk[i][j]=dis(wh_d[i],wh_k[j]);
	}
	for(int i=0;i<m;i++)
		dp[0][i]=INF;
	for(int msk=1;msk<(1<<m);msk++)
	{
		for(int i=0;i<=m;i++)
		{
			dp[msk][i]=INF;
			if((msk&(1<<i))==0 || ((msk^(1<<i))|doors[i])!=(msk^(1<<i)))
				continue;
			for(int j=0;j<=m;j++)
				dp[msk][i]=min(dp[msk][i],dp[msk^(1<<i)][j]+dk[j][i]);
			dp[msk][i]+=dk[i][i];
		}
		if((msk|doors[M])==msk)
		{
			for(int i=0;i<=m;i++)
				ans=min(ans,dp[msk][i]+dk[i][m]);
		}
	}
	if(doors[M]==0)
		ans=min(ans,dk[m][m]);
	cout<<(ans==INF ? -1:ans)<<"\n";
	return 0;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29276 KB Output is correct
2 Correct 9 ms 29276 KB Output is correct
3 Correct 61 ms 46008 KB Output is correct
4 Correct 71 ms 46020 KB Output is correct
5 Correct 62 ms 46088 KB Output is correct
6 Correct 63 ms 45916 KB Output is correct
7 Correct 60 ms 46044 KB Output is correct
8 Correct 58 ms 46152 KB Output is correct
9 Correct 59 ms 46168 KB Output is correct
10 Correct 59 ms 45908 KB Output is correct
11 Correct 59 ms 45904 KB Output is correct
12 Correct 63 ms 47448 KB Output is correct
13 Correct 58 ms 46932 KB Output is correct
14 Correct 57 ms 46740 KB Output is correct
15 Correct 59 ms 47700 KB Output is correct
16 Correct 61 ms 48208 KB Output is correct
17 Correct 61 ms 48460 KB Output is correct
18 Correct 62 ms 48720 KB Output is correct
19 Correct 80 ms 52796 KB Output is correct
20 Correct 65 ms 52820 KB Output is correct
21 Correct 63 ms 52560 KB Output is correct
22 Correct 8 ms 29528 KB Output is correct
23 Correct 8 ms 29396 KB Output is correct
24 Correct 8 ms 29276 KB Output is correct
25 Correct 8 ms 29500 KB Output is correct
26 Correct 8 ms 29368 KB Output is correct

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29272 KB Output is correct
2 Correct 8 ms 29276 KB Output is correct
3 Correct 9 ms 29532 KB Output is correct
4 Correct 8 ms 29532 KB Output is correct
5 Correct 81 ms 77068 KB Output is correct
6 Correct 77 ms 77080 KB Output is correct
7 Correct 87 ms 76884 KB Output is correct
8 Correct 74 ms 77088 KB Output is correct
9 Correct 78 ms 77096 KB Output is correct
10 Correct 61 ms 77140 KB Output is correct
11 Correct 64 ms 77132 KB Output is correct
12 Correct 62 ms 77140 KB Output is correct
13 Correct 64 ms 76884 KB Output is correct
14 Correct 61 ms 77092 KB Output is correct
15 Correct 73 ms 76884 KB Output is correct
16 Correct 86 ms 77864 KB Output is correct
17 Correct 76 ms 76880 KB Output is correct
18 Correct 62 ms 77136 KB Output is correct
19 Correct 61 ms 77140 KB Output is correct
20 Correct 60 ms 77280 KB Output is correct
21 Correct 66 ms 77412 KB Output is correct
22 Correct 61 ms 77580 KB Output is correct
23 Correct 61 ms 77392 KB Output is correct
24 Correct 61 ms 77396 KB Output is correct
25 Correct 299 ms 117720 KB Output is correct

Subtask #3
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29276 KB Output is correct
2 Correct 9 ms 29276 KB Output is correct
3 Correct 61 ms 46008 KB Output is correct
4 Correct 71 ms 46020 KB Output is correct
5 Correct 62 ms 46088 KB Output is correct
6 Correct 63 ms 45916 KB Output is correct
7 Correct 60 ms 46044 KB Output is correct
8 Correct 58 ms 46152 KB Output is correct
9 Correct 59 ms 46168 KB Output is correct
10 Correct 59 ms 45908 KB Output is correct
11 Correct 59 ms 45904 KB Output is correct
12 Correct 63 ms 47448 KB Output is correct
13 Correct 58 ms 46932 KB Output is correct
14 Correct 57 ms 46740 KB Output is correct
15 Correct 59 ms 47700 KB Output is correct
16 Correct 61 ms 48208 KB Output is correct
17 Correct 61 ms 48460 KB Output is correct
18 Correct 62 ms 48720 KB Output is correct
19 Correct 80 ms 52796 KB Output is correct
20 Correct 65 ms 52820 KB Output is correct
21 Correct 63 ms 52560 KB Output is correct
22 Correct 8 ms 29528 KB Output is correct
23 Correct 8 ms 29396 KB Output is correct
24 Correct 8 ms 29276 KB Output is correct
25 Correct 8 ms 29500 KB Output is correct
26 Correct 8 ms 29368 KB Output is correct
27 Correct 8 ms 29272 KB Output is correct
28 Correct 8 ms 29276 KB Output is correct
29 Correct 9 ms 29532 KB Output is correct
30 Correct 8 ms 29532 KB Output is correct
31 Correct 81 ms 77068 KB Output is correct
32 Correct 77 ms 77080 KB Output is correct
33 Correct 87 ms 76884 KB Output is correct
34 Correct 74 ms 77088 KB Output is correct
35 Correct 78 ms 77096 KB Output is correct
36 Correct 61 ms 77140 KB Output is correct
37 Correct 64 ms 77132 KB Output is correct
38 Correct 62 ms 77140 KB Output is correct
39 Correct 64 ms 76884 KB Output is correct
40 Correct 61 ms 77092 KB Output is correct
41 Correct 73 ms 76884 KB Output is correct
42 Correct 86 ms 77864 KB Output is correct
43 Correct 76 ms 76880 KB Output is correct
44 Correct 62 ms 77136 KB Output is correct
45 Correct 61 ms 77140 KB Output is correct
46 Correct 60 ms 77280 KB Output is correct
47 Correct 66 ms 77412 KB Output is correct
48 Correct 61 ms 77580 KB Output is correct
49 Correct 61 ms 77392 KB Output is correct
50 Correct 61 ms 77396 KB Output is correct
51 Correct 299 ms 117720 KB Output is correct
52 Correct 1384 ms 178512 KB Output is correct
53 Correct 1329 ms 178512 KB Output is correct
54 Correct 1270 ms 176212 KB Output is correct
55 Correct 1474 ms 173748 KB Output is correct
56 Correct 1344 ms 174520 KB Output is correct
57 Correct 1385 ms 176124 KB Output is correct
58 Correct 8 ms 29276 KB Output is correct
59 Correct 8 ms 29276 KB Output is correct
60 Correct 8 ms 29276 KB Output is correct
61 Correct 1431 ms 176308 KB Output is correct
62 Correct 1367 ms 185848 KB Output is correct
63 Correct 1356 ms 179536 KB Output is correct
64 Correct 77 ms 49232 KB Output is correct
65 Correct 77 ms 47700 KB Output is correct
66 Correct 1468 ms 176524 KB Output is correct
67 Correct 1467 ms 176352 KB Output is correct
68 Correct 1113 ms 219076 KB Output is correct
69 Correct 1115 ms 219376 KB Output is correct
70 Correct 1077 ms 218740 KB Output is correct
71 Correct 1080 ms 216656 KB Output is correct
72 Correct 1064 ms 216608 KB Output is correct
73 Correct 1152 ms 220344 KB Output is correct
74 Correct 1150 ms 221108 KB Output is correct
75 Correct 1132 ms 220772 KB Output is correct
76 Correct 1148 ms 221716 KB Output is correct
77 Correct 1153 ms 220568 KB Output is correct
78 Correct 1245 ms 223256 KB Output is correct
79 Correct 1171 ms 223168 KB Output is correct
80 Correct 1219 ms 221760 KB Output is correct
81 Correct 1421 ms 236016 KB Output is correct
82 Correct 1510 ms 239488 KB Output is correct
83 Correct 1494 ms 237324 KB Output is correct
84 Correct 1506 ms 250936 KB Output is correct
85 Correct 1792 ms 288468 KB Output is correct
86 Correct 1823 ms 287568 KB Output is correct
87 Correct 1720 ms 285208 KB Output is correct