oj.uz

Submission #836099

# Submission time Handle Problem Language Result Execution time Memory
836099 2023-08-24T07:20:25 Z yeediot Valley (BOI19_valley) C++14
100 / 100
 126 ms 50552 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void setIO(string s) {
   freopen((s + ".in").c_str(), "r", stdin);
   freopen((s + ".out").c_str(), "w", stdout);
}

const int mxn=1e5+5;
vector<pair<int,int>> adj[mxn];
pair<int,int> edgeid[mxn];
bool isshop[mxn]={false};
ll depth[mxn]={0},length[mxn]={0};
ll magic[mxn]={(ll)1e18};
ll jumping[20][mxn],jumpingans[20][mxn];
int st[mxn],en[mxn];
int parent[mxn];
int timer=0;

ll query(int top,int node){
   int x=node;
   int pathlength=depth[node]-depth[top];
   ll ans=magic[node];
   for(int i=0;i<20;i++){
       if(pathlength & (1<<i)){
           ans=min(ans,jumpingans[i][node]);
           node=jumping[i][node];
       }
   }
   return ans+length[x];
}

void dfs(int v,int p){
   st[v]=timer;
   timer++;
   parent[v]=p;
   for(auto u:adj[v]){
       if(u.f==p) continue;
       depth[u.f]=depth[v]+1;
       //cout<<v<<' '<<u.f<<' '<<u.s<<'\n';
       length[u.f]=length[v]+u.s;
       dfs(u.f,v);
   }
   en[v]=timer;
   timer++;
}

void dfs2(int v,int p){
   if(isshop[v]) magic[v]=length[v];
   else magic[v]=(ll)1e18;
   for(auto u:adj[v]){
       if(u.f==p) continue;
       dfs2(u.f,v);
       magic[v]=min(magic[v],magic[u.f]);
   }
}

int main() {_
   //setIO("wayne");
   int n,s,q,e;
   cin>>n>>s>>q>>e;
   for(int i=1;i<=n-1;i++){
       int a,b,w;
       cin>>a>>b>>w;
       adj[a].push_back({b,w});
       adj[b].push_back({a,w});
       edgeid[i]={a,b};
   }
   for(int i=0;i<s;i++){
       int x;
       cin>>x;
       isshop[x]=true;
   }
   dfs(e,0);
   dfs2(e,0);
   for(int i=1;i<=n;i++){
       magic[i]-=2*length[i];
   }
   for(int i=1;i<=n;i++){
       jumping[0][i]=parent[i];
       jumpingans[0][i]=magic[parent[i]];
   }
   for(int i=1;i<20;i++){
       for(int j=1;j<=n;j++){
           jumping[i][j]=jumping[i-1][jumping[i-1][j]];
           jumpingans[i][j]=min(jumpingans[i-1][j],jumpingans[i-1][jumping[i-1][j]]);
       }
   }
   for(int i=0;i<q;i++){
       int edge,node;
       cin>>edge>>node;
       int top=(depth[edgeid[edge].f]>depth[edgeid[edge].s]?edgeid[edge].f:edgeid[edge].s);
       if(st[top]<=st[node] and en[node]<=en[top]){
           if(query(top,node)<=(ll)1e14) cout<<query(top,node)<<'\n';
           else cout<<"oo"<<'\n';
       }
       else{
           cout<<"escaped"<<'\n';
       }
   }
   return 0;
}

Compilation message

valley.cpp: In function 'void setIO(std::string)':
valley.cpp:10:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |    freopen((s + ".in").c_str(), "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:11:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |    freopen((s + ".out").c_str(), "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3028 KB Output is correct
2 Correct 5 ms 3028 KB Output is correct
3 Correct 3 ms 3028 KB Output is correct
4 Correct 3 ms 3028 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3028 KB Output is correct
2 Correct 5 ms 3028 KB Output is correct
3 Correct 3 ms 3028 KB Output is correct
4 Correct 3 ms 3028 KB Output is correct
5 Correct 2 ms 3284 KB Output is correct
6 Correct 2 ms 3284 KB Output is correct
7 Correct 3 ms 3412 KB Output is correct
8 Correct 2 ms 3284 KB Output is correct
9 Correct 2 ms 3284 KB Output is correct
10 Correct 2 ms 3284 KB Output is correct
11 Correct 2 ms 3284 KB Output is correct
12 Correct 2 ms 3284 KB Output is correct
13 Correct 2 ms 3284 KB Output is correct
14 Correct 2 ms 3284 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 42956 KB Output is correct
2 Correct 102 ms 46368 KB Output is correct
3 Correct 96 ms 46280 KB Output is correct
4 Correct 105 ms 48072 KB Output is correct
5 Correct 100 ms 48196 KB Output is correct
6 Correct 126 ms 50104 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3028 KB Output is correct
2 Correct 5 ms 3028 KB Output is correct
3 Correct 3 ms 3028 KB Output is correct
4 Correct 3 ms 3028 KB Output is correct
5 Correct 2 ms 3284 KB Output is correct
6 Correct 2 ms 3284 KB Output is correct
7 Correct 3 ms 3412 KB Output is correct
8 Correct 2 ms 3284 KB Output is correct
9 Correct 2 ms 3284 KB Output is correct
10 Correct 2 ms 3284 KB Output is correct
11 Correct 2 ms 3284 KB Output is correct
12 Correct 2 ms 3284 KB Output is correct
13 Correct 2 ms 3284 KB Output is correct
14 Correct 2 ms 3284 KB Output is correct
15 Correct 83 ms 42956 KB Output is correct
16 Correct 102 ms 46368 KB Output is correct
17 Correct 96 ms 46280 KB Output is correct
18 Correct 105 ms 48072 KB Output is correct
19 Correct 100 ms 48196 KB Output is correct
20 Correct 126 ms 50104 KB Output is correct
21 Correct 95 ms 46112 KB Output is correct
22 Correct 79 ms 45776 KB Output is correct
23 Correct 84 ms 45764 KB Output is correct
24 Correct 119 ms 47760 KB Output is correct
25 Correct 100 ms 50552 KB Output is correct
26 Correct 74 ms 46196 KB Output is correct
27 Correct 79 ms 45828 KB Output is correct
28 Correct 89 ms 45768 KB Output is correct
29 Correct 107 ms 47440 KB Output is correct
30 Correct 124 ms 48608 KB Output is correct
31 Correct 78 ms 46268 KB Output is correct
32 Correct 83 ms 46040 KB Output is correct
33 Correct 94 ms 46004 KB Output is correct
34 Correct 104 ms 47820 KB Output is correct
35 Correct 112 ms 50492 KB Output is correct
36 Correct 91 ms 47948 KB Output is correct