Submission #1271206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271206		efeg	Valley (BOI19_valley)	C++20	100 / 100	196 ms	85672 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]; 
int binCost[N][40]; 
vector<viii> adj;
viii edges;  
vi cost,v,vis,depth,dist,cnt; 

void dfs(int node){
    if (vis[node]) return;
    vis[node] = true; 
    cost[node] = 1e18; 

    
    if (v[node]) {
        cost[node] = dist[node]; 
        cnt[node]++; 
    }
    for (auto tp : adj[node]){
        int to,d,idx; tie(to,d,idx) = tp;
        if (!vis[to]){
            binlift[to][0] = node;  
            dist[to] = dist[node] + d; 
            depth[to] = depth[node] + 1; 
            dfs(to);
            cnt[node] += cnt[to]; 
            cost[node] = min(cost[node],cost[to]); 
        }
    }
    binCost[node][0] = cost[node] - 2*dist[node]; 
}

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);  
    dist.assign(n+10,0); 
    cost.assign(n+10,0);
    cnt.assign(n+10,0); 
    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; 
    dist[e] = 0; 
    dfs(e); 
    for (int j = 1; j < 32; j++){
        for (int i = 0; i < n; i++){
            int nxt = binlift[i][j-1];
            if (nxt == -1){
                binCost[i][j] = binCost[i][j-1]; 
                binlift[i][j] = -1; 
            }
            else {
                binCost[i][j] = min(binCost[i][j-1], binCost[nxt][j-1]);
                binlift[i][j] = binlift[nxt][j-1];  
            }
        }
    }
    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 || lift(qr,diff) != a) cout << "escaped" << endl;
        else {  
            if (!cnt[a]) cout << "oo" << endl;
            else {
                int mn = 1e18,curr = qr;
                for (int j = 0; j < 32; j++){
                    if ((diff+1) & (1 << j)){
                        mn = min(mn,binCost[curr][j]);
                        curr = binlift[curr][j];
                        if (curr == -1) break; 
                    }
                }
                cout << mn + dist[qr] << endl; 
            }
        }
    }
	return 0;
}	

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