# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
937713 |
2024-03-04T11:48:25 Z |
vjudge1 |
Valley (BOI19_valley) |
C++17 |
|
316 ms |
63692 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define int long long
#define endl "\n"
using namespace std;
vector<vector<pair<int,int>>>tree;
vector<bool>village;
vector<pair<int,int>>edges;
vector<int>depth;
vector<int>closest;
vector<int>visited;
vector<vector<pair<int,int>>>lifting;
vector<vector<int>>lifting2;
int n,e;
void dfs(int i,int k){
if(visited[i]==true)return;
visited[i]=true;
depth[i]=k;
int N=tree[i].size();
for(int j=0;j<N;j++){
dfs(tree[i][j].first,k+1);
}
}
int dfs2(int i){
if(visited[i]==true)return -1;
visited[i]=true;
int N=tree[i].size();
int distance=LLONG_MAX;
for(int j=0;j<N;j++){
pair<int,int>a=tree[i][j];
int current=dfs2(a.first);
if(current!=-1&¤t!=LLONG_MAX){
current+=a.second;
distance=min(current,distance);
}
}
if(village[i]==true){
return closest[i]=0;
}
closest[i]=distance;
return distance;
}
void dfs3(int i,int p,int l){
if(visited[i]==true)return;
visited[i]=true;
if(i!=e){
pair<int,int>a=make_pair(p,l);
int lim=1;
while(lim<=depth[i]){
lifting[i].push_back(a);
int N1=lifting[i].size();
int N2=lifting[a.first].size();
if(N1<=N2){
a.second+=lifting[a.first][N1-1].second;
a.first=lifting[a.first][N1-1].first;
}
lim*=2;
}
}
int N=tree[i].size();
for(int j=0;j<N;j++){
pair<int,int>a=tree[i][j];
dfs3(a.first,i,a.second);
}
}
int bit(int k){
for(int i=62;i>=0;i--){
if(((1LL<<i)&k)!=0){
return i;
}
}
return -1;
}
pair<int,int>lift(int i,int k){
pair<int,int>ans;
if(k==0){
return make_pair(i,0);
}else if(k==1){
return lifting[i][0];
}else{
int l=bit(k);
int b=(1LL<<l);
ans=lifting[i][l];
pair<int,int>c=lift(ans.first,k-b);
ans.first=c.first;
ans.second+=c.second;
}
return ans;
}
void dfs4(int i){
if(visited[i]==true)return;
visited[i]=true;
if(i!=e){
int ancestor=i;
int a=closest[i];
int lim=1;
while(lim<=depth[i]){
lifting2[i].push_back(a);
int N1=lifting2[i].size();
ancestor=lifting[i][N1-1].first;
int val=lifting[i][N1-1].second;
int N2=lifting2[ancestor].size();
if(N1<=N2){
int x=lifting2[ancestor][N1-1];
if(x!=LLONG_MAX){
a=min(x+val,lifting2[i][N1-1]);
}
}
lim*=2;
}
}
int N=tree[i].size();
for(int j=0;j<N;j++){
pair<int,int>g=tree[i][j];
dfs4(g.first);
}
}
int end(int i,int k){
int l=bit(k);
int b=(1LL<<l);
if(k==b){
return lifting2[i][l];
}
int ans=lifting2[i][l];
int NODE=lifting[i][l].first;
int DIST=lifting[i][l].second;
int sec=end(NODE,k-b);
ans=min(ans,max(sec,sec+DIST));
return ans;
}
void solve(){
int r,i;
cin>>r>>i;
r--;
i--;
pair<int,int>edge=edges[r];
int node;
if(depth[edge.first]>depth[edge.second]){
node=edge.first;
}else{
node=edge.second;
}
int d1=depth[i];
int d2=depth[node];
if(d1<d2){
cout<<"escaped\n";
return;
}
int dist=d1-d2;
pair<int,int>par=lift(i,dist);
if(par.first!=node){
cout<<"escaped\n";
return;
}
if(closest[node]==LLONG_MAX){
cout<<"oo\n";
return;
}
cout<<end(i,dist+1)<<endl;
return;
}
signed main(){
cin.tie(NULL);
cout.tie(NULL);
ios_base::sync_with_stdio(false);
int s,q;
cin>>n>>s>>q>>e;
e--;
tree.resize(n);
edges.resize(n-1);
village.resize(n,false);
visited.resize(n,false);
depth.resize(n);
closest.resize(n);
lifting.resize(n);
lifting2.resize(n);
for(int i=0;i<n-1;i++){
int a,b,w;
cin>>a>>b>>w;
a--;
b--;
pair<int,int>a1=make_pair(a,w);
pair<int,int>b1=make_pair(b,w);
tree[a].push_back(b1);
tree[b].push_back(a1);
edges[i]=make_pair(a,b);
}
for(int i=0;i<s;i++){
int a;
cin>>a;
a--;
village[a]=true;
}
village[e]=true;
dfs(e,0);
for(int i=0;i<n;i++)visited[i]=false;
dfs2(e);
for(int i=0;i<n;i++)visited[i]=false;
dfs3(e,0,0);
for(int i=0;i<n;i++)visited[i]=false;
dfs4(e);
while(q--)solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
348 KB |
Output is correct |
4 |
Correct |
2 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
348 KB |
Output is correct |
4 |
Correct |
2 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
139 ms |
29508 KB |
Output is correct |
2 |
Correct |
171 ms |
37908 KB |
Output is correct |
3 |
Correct |
211 ms |
51360 KB |
Output is correct |
4 |
Correct |
255 ms |
59764 KB |
Output is correct |
5 |
Correct |
228 ms |
59732 KB |
Output is correct |
6 |
Correct |
313 ms |
62700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
348 KB |
Output is correct |
4 |
Correct |
2 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
860 KB |
Output is correct |
15 |
Correct |
139 ms |
29508 KB |
Output is correct |
16 |
Correct |
171 ms |
37908 KB |
Output is correct |
17 |
Correct |
211 ms |
51360 KB |
Output is correct |
18 |
Correct |
255 ms |
59764 KB |
Output is correct |
19 |
Correct |
228 ms |
59732 KB |
Output is correct |
20 |
Correct |
313 ms |
62700 KB |
Output is correct |
21 |
Correct |
125 ms |
29784 KB |
Output is correct |
22 |
Correct |
146 ms |
37428 KB |
Output is correct |
23 |
Correct |
167 ms |
44012 KB |
Output is correct |
24 |
Correct |
233 ms |
59476 KB |
Output is correct |
25 |
Correct |
304 ms |
63692 KB |
Output is correct |
26 |
Correct |
119 ms |
29812 KB |
Output is correct |
27 |
Correct |
153 ms |
37208 KB |
Output is correct |
28 |
Correct |
175 ms |
51268 KB |
Output is correct |
29 |
Correct |
239 ms |
59404 KB |
Output is correct |
30 |
Correct |
316 ms |
61372 KB |
Output is correct |
31 |
Correct |
138 ms |
30032 KB |
Output is correct |
32 |
Correct |
154 ms |
37968 KB |
Output is correct |
33 |
Correct |
188 ms |
49488 KB |
Output is correct |
34 |
Correct |
271 ms |
60496 KB |
Output is correct |
35 |
Correct |
284 ms |
63516 KB |
Output is correct |
36 |
Correct |
279 ms |
60752 KB |
Output is correct |