oj.uz

Submission #123248

# Submission time Handle Problem Language Result Execution time Memory
123248 2019-06-30T16:35:11 Z miguel Valley (BOI19_valley) C++14
59 / 100
 438 ms 25828 KB 
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define sz size()
#define x first
#define y second
#define pi pair <int, int>
#define pii pair <pi, int>
#define vi vector <int>
const ll mod = 1000000007;
#define int ll
int n, s, q, e;
vector<int> d;
int f[100001], l[100001];
pi road[100001];
int dt[1001];
bitset<100001> sh;
vector <pi> g[100001];

void dfs(int p, int cur){
    d.pb(cur);
    for(pi i: g[cur]){
        if(i.x!=p) dfs(cur, i.x);
    }
    d.pb(cur);
}

void bfs(int rip1, int rip2, int p, int cur){
    for(pi i: g[cur]){
        if(i.x!=p && (min(cur, i.x)!=rip1 || max(cur, i.x)!=rip2)){
            dt[i.x]=dt[cur]+i.y;
            bfs(rip1, rip2, cur, i.x);
        }
    }
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>s>>q>>e;
    for(int i=1; i<=n-1; i++){
        int x, y, z;
        cin>>x>>y>>z;
        road[i]={x, y};
        g[x].pb({y, z});
        g[y].pb({x, z});
    }
    for(int i=1; i<=s; i++){
        int x;
        cin>>x;
        sh[x]=1;
    }
    dfs(0, e);
    for(int i=0; i<d.size(); i++){
        l[d[i]]=i+1;
        if(!f[d[i]]) f[d[i]]=i+1;
    }
    if(s==n){
        //for(int i=1; i<=n; i++){cout<<i<<" "<<f[i]<<" "<<l[i]<<endl;}
        for(int i=1; i<=q; i++){
            int rd, r;
            cin>>rd>>r;
            int x=road[rd].x, y=road[rd].y;
            if(f[x]<=f[r] && l[x]>=l[r] && f[y]<=f[r] && l[y]>=l[r]) cout<<0<<"\n";
            else cout<<"escaped\n";
        }
        return 0;
    }
    for(int i=1; i<=q; i++){
        int rd, r;
        cin>>rd>>r;
        int x=road[rd].x, y=road[rd].y;
        if(x>y) swap(x, y);
        if(f[x]<=f[r] && l[x]>=l[r] && f[y]<=f[r] && l[y]>=l[r]){
            for(int j=1; j<=n; j++) dt[j]=1e18;
            dt[r]=0;
            bfs(x, y, 0, r);
            int ans=1e18;
            for(int i=1; i<=n; i++){
                if(sh[i]) ans=min(ans, dt[i]);
            }
            if(ans!=1e18) cout<<ans<<"\n";
            else cout<<"oo\n";
        }
        else cout<<"escaped\n";
    }
}

Compilation message

valley.cpp: In function 'int32_t main()':
valley.cpp:57:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<d.size(); i++){
                  ~^~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2808 KB Output is correct
2 Correct 35 ms 2808 KB Output is correct
3 Correct 34 ms 2812 KB Output is correct
4 Correct 32 ms 2808 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2808 KB Output is correct
2 Correct 35 ms 2808 KB Output is correct
3 Correct 34 ms 2812 KB Output is correct
4 Correct 32 ms 2808 KB Output is correct
5 Correct 9 ms 2808 KB Output is correct
6 Correct 9 ms 2808 KB Output is correct
7 Correct 9 ms 2808 KB Output is correct
8 Correct 10 ms 2808 KB Output is correct
9 Correct 11 ms 2808 KB Output is correct
10 Correct 15 ms 2808 KB Output is correct
11 Correct 8 ms 2808 KB Output is correct
12 Correct 8 ms 2808 KB Output is correct
13 Correct 8 ms 2808 KB Output is correct
14 Correct 15 ms 2812 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 13388 KB Output is correct
2 Correct 438 ms 13396 KB Output is correct
3 Correct 416 ms 13288 KB Output is correct
4 Correct 424 ms 14360 KB Output is correct
5 Correct 421 ms 14436 KB Output is correct
6 Correct 427 ms 15460 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2808 KB Output is correct
2 Correct 35 ms 2808 KB Output is correct
3 Correct 34 ms 2812 KB Output is correct
4 Correct 32 ms 2808 KB Output is correct
5 Correct 9 ms 2808 KB Output is correct
6 Correct 9 ms 2808 KB Output is correct
7 Correct 9 ms 2808 KB Output is correct
8 Correct 10 ms 2808 KB Output is correct
9 Correct 11 ms 2808 KB Output is correct
10 Correct 15 ms 2808 KB Output is correct
11 Correct 8 ms 2808 KB Output is correct
12 Correct 8 ms 2808 KB Output is correct
13 Correct 8 ms 2808 KB Output is correct
14 Correct 15 ms 2812 KB Output is correct
15 Correct 410 ms 13388 KB Output is correct
16 Correct 438 ms 13396 KB Output is correct
17 Correct 416 ms 13288 KB Output is correct
18 Correct 424 ms 14360 KB Output is correct
19 Correct 421 ms 14436 KB Output is correct
20 Correct 427 ms 15460 KB Output is correct
21 Runtime error 94 ms 25828 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -