oj.uz

답안 #650284

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
650284 2022-10-13T10:31:40 Z MEGalodon Valley (BOI19_valley) C++14
23 / 100
 404 ms 22300 KB 
#include <bits/stdc++.h>
#define MAXN 100001
using namespace std;
vector<int> adj_lst[MAXN];
int depth[MAXN];
int par[MAXN][20];
void dfs(int i){
    for( int j : adj_lst[i] ){
        if( depth[j] ) continue;
        par[j][0] = i; depth[j] = depth[i]+1;
        dfs(j);
    }
}
vector<pair<int, int>> edgeList;
int jmp(int i, int diff){
    for( int k{19} ; k >= 0 ; --k ) if( diff&(1<<k) ) i = par[i][k];
    return i;
}
int main(){
    int nodes, edges, shops, Q, E;
    cin>>nodes>>shops>>Q>>E; edges = nodes-1;
    while( edges-- ){
        int u, v, w;
        cin>>u>>v>>w;
        adj_lst[u].push_back(v);
        adj_lst[v].push_back(u);
        edgeList.push_back({u, v});
    }
    depth[E] = 1;
    dfs(E);
    //for( int i{1} ; i <= nodes ; ++i ) cout<<depth[i]<<" "; cout<<'\n';
    while( shops-- ){ int x; cin>>x; }
    for( int k{1} ; k < 20 ; ++k ) for( int i{1} ; i <= nodes ; ++i ) par[i][k] = par[par[i][k-1]][k-1];
    while( Q-- ){
        int i, r;
        cin>>i>>r;
        auto x = edgeList[i-1];
        int u = x.first, v = x.second;
        if( depth[u] < depth[v] ) swap(u, v);
        if( depth[r] < depth[u] ) cout<<"escaped\n";
        else{
            int diff = depth[r] - depth[u];
            int rch = jmp(r, diff);
            //cout<<diff<<" "<<rch<<'\n';
            if( rch == u ) cout<<"0"<<'\n';
            else cout<<"escaped\n";
        }
    }
    return 0;
}

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 373 ms 15672 KB Output is correct
2 Correct 334 ms 19224 KB Output is correct
3 Correct 404 ms 19308 KB Output is correct
4 Correct 380 ms 20624 KB Output is correct
5 Correct 385 ms 20676 KB Output is correct
6 Correct 391 ms 22300 KB Output is correct

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 17 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -