Submission #441451

#	Time	Username	Problem	Language	Result	Execution time	Memory
441451		cpp219	Valley (BOI19_valley)	C++14	100 / 100	281 ms	53500 KiB

valley

#pragma GCC optimization O2
#pragma GCC optimization "unroll-loop"
#pragma target ("avx2")

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e5 + 9;
const ll Log2 = 20;
const ll inf = 1e18 + 7;
const ll lim = 1e16 + 7;

vector<LL> g[N];
LL edge[N];
ll n,S,Q,E,x,y,w,par[N][20],d[N],dp[N][20],val[N],dep[N];
ll nTime,L[N],R[N];

void DFS(ll u,ll p){
    L[u] = R[u] = nTime; nTime++;
    for (auto i : g[u]){
        ll v = i.fs,L = i.sc;
        if (v == p) continue;
        d[v] = d[u] + 1; dep[v] = dep[u] + L; par[v][0] = u;
        DFS(v,u); R[u] = max(R[u],R[v]);
        val[u] = min(val[u],L + val[v]);
    }
}

void reDFS(ll u,ll p){
    //cout<<u<<" "<<p<<"\n";
    //cout<<g[u][0].fs; exit(0);
    for (ll i = 1;i < Log2;i++) if ((1 << i) <= d[u])
        par[u][i] = par[par[u][i - 1]][i - 1],
        dp[u][i] = min(dp[u][i - 1],dp[par[u][i - 1]][i - 1]);
    for (auto i : g[u]) if (i.fs != p){
        dp[i.fs][0] = val[u] - dep[u];
        reDFS(i.fs,u);
    }
}

ll Jump(ll node,ll step){
    ll res = val[node] - dep[node];
    for (ll i = Log2 - 1;i >= 0;i--){
        if ((1 << i) > step) continue;
        res = min(res,dp[node][i]); node = par[node][i];
        step -= (1 << i);
    }
    //cout<<val[2] - dep[2]; exit(0);
    return res;
}

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        freopen(task".OUT","w",stdout);
    }
    cin>>n>>S>>Q>>E; fill(val,val + n + 1,inf);
    for (ll i = 1;i < n;i++){
        cin>>x>>y>>w; edge[i] = {x,y};
        g[x].push_back({y,w}); g[y].push_back({x,w});
    }
    for (ll i = 1;i <= S;i++) cin>>x,val[x] = 0;
    DFS(E,0); reDFS(E,0); //cout<<dp[4][0]; return 0;
    while(Q--){
        cin>>x>>y;
        if (d[edge[x].fs] < d[edge[x].sc]) swap(edge[x].fs,edge[x].sc);
        ll l = edge[x].fs;
        if (L[l] <= L[y] && R[y] <= R[l]){
            ll kq = Jump(y,d[y] - d[l]); //cout<<kq; return 0;
            if (kq > lim) cout<<"oo";
            else cout<<kq + dep[y];
        }
        else cout<<"escaped";
        cout<<"\n";
    }
}

Compilation message (stderr)

valley.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization O2
      | 
valley.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
valley.cpp:3: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    3 | #pragma target ("avx2")
      | 
valley.cpp: In function 'int main()':
valley.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
valley.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen(task".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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