| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 937391 |
2024-03-04T01:59:18 Z |
naneosmic |
Valley (BOI19_valley) |
C++14 |
|
191 ms |
50376 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;
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 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;
}
cout<<0<<endl;
}
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);
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);
cout<<endl;
while(q--)solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
26512 KB |
Output is correct |
| 2 |
Correct |
114 ms |
31824 KB |
Output is correct |
| 3 |
Correct |
153 ms |
40764 KB |
Output is correct |
| 4 |
Correct |
165 ms |
47124 KB |
Output is correct |
| 5 |
Correct |
170 ms |
47336 KB |
Output is correct |
| 6 |
Correct |
191 ms |
50376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
