Submission #446494

#	Time	Username	Problem	Language	Result	Execution time	Memory
446494		MEGalodon	Valley (BOI19_valley)	C++14	0 / 100	190 ms	40084 KiB

valley

#include <iostream>
#include <vector>
#include <cstring>
#define ll long long
#define ii pair<int, ll>
#define MAXN 100001
#define INF 10000000000000000
using namespace std;
vector<ii> adj_lst[MAXN];
int shopExists[MAXN];
ii edgePairs[MAXN];
int tin[MAXN], tout[MAXN];
int counter = 0;
ll dist[MAXN], bjMagic[MAXN][20]; //bj magic doesnt include the last vertex on the path
ll magic[MAXN];
int par[MAXN][20];
void dfs(int i, int p=0){
    tin[i] = counter++;
    magic[i] = INF;
    if( shopExists[i] ) magic[i] = dist[i];
    for( auto j : adj_lst[i] ){
        if( j.first == p ) continue;
        dist[j.first] = dist[i]+j.second;
        par[j.first][0] = i;
        dfs(j.first, i);
        magic[i] = min(magic[i], magic[j.first]);
        if( magic[j.first] < INF ) bjMagic[j.first][0] = magic[j.first]-2*dist[j.first];
        else bjMagic[j.first][0] = INF;
    }
    //if( magic[i] < INF ) magic[i] -= 2*dist[i];
    tout[i] = counter-1;
}
int anc(int i, int j){ //is i an ancestor of j
    if( tin[i] <= tin[j] && tout[i] >= tout[j] ) return 1;
    return 0;
}
int lower(int e){
    int u = edgePairs[e].first, v = edgePairs[e].second;
    if( anc(u, v) )  return v;
    return u;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int nodes, shops, queries, E, edges;
    cin>>nodes>>shops>>queries>>E; edges = nodes-1;
    for( int i{1} ; i <= edges ; ++i ){
        int u, v, w;
        cin>>u>>v>>w;
        edgePairs[i] = ii(u, v);
        adj_lst[u].push_back(ii(v, w));
        adj_lst[v].push_back(ii(u, w));
    }
    memset(shopExists, 0, sizeof(shopExists));
    for( int i{1} ; i <= shops ; ++i ){ int s; cin>>s; shopExists[s] = 1; }
    dist[E] = 0; par[E][0] = 0;
    dfs(E); ///this significantly simplifies other parts of the code, rooting at E instead of the regular 1
    //for( int i{1} ; i <= nodes ; ++i ) cout<<tin[i]<<" "<<tout[i]<<'\n';
    //for( int i{1} ; i <= nodes ; ++i ) magic[i] -= 2*dist[i];
    bjMagic[E][0] = magic[E];
    for( int i{1} ; i < 20 ; ++i )
        for( int j{1} ; j <= nodes ; ++j ) {
            par[j][i] = par[par[j][i-1]][i-1];
           // bjMagic[i][j] = min(bjMagic[i][j], bjMagic[bjMagic[i][j - 1]][j - 1]);
            bjMagic[j][i] = min(bjMagic[j][i], bjMagic[par[j][i-1]][i-1]);
        }
    //for( int i{1} ; i <= nodes ; ++i ){
      //  cout<<i<<": ";
        //for( int j{0} ; j <= 3 ; ++j ) cout<<bjMagic[i][j]<<" "; cout<<'\n';
    //}
    //for( int i{1} ; i <= nodes ; ++i ) magic[i] -= 2*dist[i];
    while( queries-- ){
        int edgeNo, node;
        cin>>edgeNo>>node;
        int low = lower(edgeNo);
        //cout<<anc(1, 2)<<" "<<low<<'\n';
        if( !anc(low, node) ) cout<<"escaped\n";
        else{
            ll output = INF;
            int tmp = node;
            for( int i{19} ; i >= 0 ; --i ) {
                //cout<<par[node][i]<<" "<<anc(par[node][i], low)<<'\n';
                if (par[node][i] == low || (par[node][i] && !anc(par[node][i], low))) {
                    output = min(output, bjMagic[node][i]);
                    node = par[node][i];
                    //cout << output << " " << node << '\n';
                }
            }
            output = min(output, bjMagic[node][0]);
            output += dist[tmp];
            if( output < INF ) cout<<output<<'\n';
            else cout<<"oo\n";
        }
    }
    return 0;
}

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