Submission #1270981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270981		efeg	Valley (BOI19_valley)	C++20	23 / 100	150 ms	49204 KiB

valley

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#define int long long 
#define F first
#define S second 
#define pb push_back
#define endl '\n'
#define all(v) v.begin(),v.end()
#define gcd(a,b) __gcd(a,b)
#define mt make_tuple
#define pqueue priority_queue


typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<iii> viii;
typedef set<int> si;
typedef vector<ii> vii;				
typedef vector<vi> vvi;
typedef vector<si> vsi;
typedef vector<vb> vvb;
typedef vector<vc> vvc;

const int MOD = 1e9 + 7;
const int N = 1e5 + 100;

int n,s,q,e; 
int binlift[N][40]; 
vector<viii> adj;
viii edges;  
vi v,vis,depth;

void dfs(int node){
    if (vis[node]) return;
    vis[node] = true; 
    for (int j = 1; j < 32; j++){
        int nxt = binlift[node][j-1]; 
        if (nxt == -1) binlift[node][j] = -1;
        else binlift[node][j] = binlift[nxt][j-1]; 
    }

    for (auto tp : adj[node]){
        int to,d,idx; tie(to,d,idx) = tp;
        if (!vis[to]){
            binlift[to][0] = node;  
            depth[to] = depth[node] + 1; 
            dfs(to);
        }
    }
}

int lift(int node,int k){
    for (int j = 0; j < 32; j++){
        if (k & (1 << j)){
            node = binlift[node][j];
            if (node == -1) return node; 
        }
    }
    return node; 
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	
    cin >> n >> s >> q >> e; e--; 
    adj.assign(n+10,viii()); 
    edges.clear(); 
    v.assign(n+10,false); 
    depth.assign(n+10,false);
    vis.assign(n+10,false);  
    for (int i = 0; i < n-1; i++){
        int a,b,w; cin >> a >> b >> w;
        a--; b--;
        adj[a].emplace_back(b,w,i); 
        adj[b].emplace_back(a,w,i); 
        edges.emplace_back(a,b,w);  
    }

    for (int i = 0; i < s; i++){
        int x; cin >> x; x--;
        v[x] = true; 
    }
    binlift[e][0] = -1; 
    depth[e] = 0; 
    dfs(e); 

    for (int i = 0; i < q; i++){
        int qi,qr; cin >> qi >> qr; qi--; qr--; 
        int a,b,w; tie(a,b,w) = edges[qi]; 
        if (depth[a] < depth[b]) swap(a,b);
        int diff = depth[qr] - depth[a]; 
        if (diff < 0) cout << "escaped" << endl;
        else if (lift(qr,diff) == a) cout << "0" << endl;
        else cout << "escaped" << endl;  
    }

    
/*

    for (int i = 0; i < q; i++){
        cin >> qi >> qr; qi--; qr--; 
        pqueue<ii,vii,greater<ii>> pq;
        vis.assign(n + 10, INT_MAX); 
        pq.push({0,qr}); 
        
        bool escaped = false; 
        int ans = -1; 
        while (!pq.empty()){
            int d,node; tie(d,node) = pq.top(); pq.pop(); 
            if (vis[node] != INT_MAX) continue;
            vis[node] = d;
            if (node == e){
                escaped = true;
                break; 
            }
            if (v[node] && ans == -1) ans = d;
    
            for (auto tp : adj[node]){
                int to,w,idx; tie(to,w,idx) = tp;
                if (idx == qi) continue;
                if (vis[node] != INT_MAX) pq.push({d + w ,to}); 
            }
        }
        if (escaped) cout << "escaped" << endl;
        else {
            if (ans != -1) cout << ans << endl;
            else cout << "oo" << endl; 
        }
    
    
    }
*/ 

	return 0;
}	

• Subtask 1: 0 / 9
• Subtask 2: 0 / 27
• Subtask 3: 23 / 23
• Subtask 4: 0 / 41