Submission #946293

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
946293	2024-03-14 13:25:46	PM1	LOSTIKS (INOI20_lostiks)	C++17	100 / 100	1390 ms	345140 KiB

Main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 23 / 23
• Subtask 2: 36 / 36
• Subtask 3: 41 / 41