oj.uz

답안 #718567

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
718567 2023-04-04T10:43:02 Z fdnfksd Valley (BOI19_valley) C++14
100 / 100
 242 ms 58316 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll dp[maxN],in[maxN],out[maxN],tg=0;
bool c[maxN];
ll P[maxN][18];
const ll inf2=1e18;
struct qq
{
    ll fi,se,id;
};
vector<qq>g[maxN];
ll h[maxN],d[maxN];
ll val[maxN];
ll pos[maxN];
void cc(ll u,ll p)
{
    P[u][0]=p;
    for(int i=1;i<=17;i++) P[u][i]=P[P[u][i-1]][i-1];
    for(auto vv:g[u])
    {
        if(vv.fi!=p)
        {
            cc(vv.fi,u);
        }
    }
}
void dfs(ll u,ll p)
{
    dp[u]=inf;
    if(c[u]==1) dp[u]=0;
    in[u]=++tg;
    vector<pli>cc;
    for(auto vv:g[u])
    {
        if(vv.fi!=p)
        {
            pos[vv.id]=vv.fi;
            h[vv.fi]=h[u]+1;
            d[vv.fi]=d[u]+vv.se;
            dfs(vv.fi,u);
            dp[u]=min(dp[u],dp[vv.fi]+vv.se);
            cc.pb({dp[vv.fi]+vv.se,vv.fi});
        }
    }
    sort(cc.begin(),cc.end());
    if(c[u]==1)
    {
        for(auto vv:g[u])
        {
            if(vv.fi!=p)
            {
                val[vv.fi]=-d[u];
            }
        }
    }
    else
    {
        for(int i=0;i<min(2,(int)cc.size());i++)
        {
            for(auto vv:g[u])
            {
                if(vv.fi!=p&&vv.fi!=cc[i].se)
                {
                    val[vv.fi]=min(val[vv.fi],-d[u]+cc[i].fi);

                }
            }
        }
    }
    out[u]=tg;
}
ll mn[maxN][18];
void dfs2(ll u,ll p)
{
    mn[u][0]=val[u];
    for(int i=1;i<=17;i++) mn[u][i]=min(mn[u][i-1],mn[P[u][i-1]][i-1]);
    for(auto vv:g[u])
    {
        if(vv.fi!=p)
        {
            dfs2(vv.fi,u);
        }
    }
}
ll get(ll u,ll p)
{
    ll d=h[u]-h[p];
    ll ans=inf;
    for(int i=17;i>=0;i--)
    {
        if(d>>i&1)
        {
            ans=min(ans,mn[u][i]);
            u=P[u][i];
        }
    }
    return ans;
}
ll n,q,s,e;
bool ipar(ll u,ll p)
{
    return (in[p]<=in[u]&&out[u]<=out[p]);
}
void solve()
{
    cin >> n >> s >>  q >> e;
    for(int i=1;i<n;i++)
    {
        ll u,v,w;
        cin >> u >> v >> w;
        g[u].pb({v,w,i});
        g[v].pb({u,w,i});
    }
    for(int i=1;i<=n;i++) val[i]=inf,c[i]=0;
    for(int i=1;i<=s;i++)
    {
        ll u;
        cin >> u;
        c[u]=1;
    }
    cc(e,e);
    dfs(e,e);
    dfs2(e,e);
    while(q--)
    {
        ll id,u;
        cin >> id >> u;
        ll v=pos[id];
        if(ipar(u,v))
        {
            ll ans=inf;
            ans=min(ans,dp[u]);
            ans=min(ans,get(u,v)+d[u]);
            if(ans>=inf2) cout <<"oo\n";
            else cout << ans<<'\n';
        }
        else
        {
            cout <<"escaped\n";
        }
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 5 ms 5172 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 5 ms 5172 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 4 ms 5428 KB Output is correct
6 Correct 3 ms 5416 KB Output is correct
7 Correct 4 ms 5460 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 4 ms 5424 KB Output is correct
10 Correct 4 ms 5436 KB Output is correct
11 Correct 4 ms 5460 KB Output is correct
12 Correct 4 ms 5460 KB Output is correct
13 Correct 4 ms 5460 KB Output is correct
14 Correct 4 ms 5460 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 153 ms 45808 KB Output is correct
2 Correct 174 ms 45860 KB Output is correct
3 Correct 194 ms 46156 KB Output is correct
4 Correct 229 ms 49548 KB Output is correct
5 Correct 203 ms 49452 KB Output is correct
6 Correct 228 ms 53452 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 5 ms 5172 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 4 ms 5428 KB Output is correct
6 Correct 3 ms 5416 KB Output is correct
7 Correct 4 ms 5460 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 4 ms 5424 KB Output is correct
10 Correct 4 ms 5436 KB Output is correct
11 Correct 4 ms 5460 KB Output is correct
12 Correct 4 ms 5460 KB Output is correct
13 Correct 4 ms 5460 KB Output is correct
14 Correct 4 ms 5460 KB Output is correct
15 Correct 153 ms 45808 KB Output is correct
16 Correct 174 ms 45860 KB Output is correct
17 Correct 194 ms 46156 KB Output is correct
18 Correct 229 ms 49548 KB Output is correct
19 Correct 203 ms 49452 KB Output is correct
20 Correct 228 ms 53452 KB Output is correct
21 Correct 160 ms 49108 KB Output is correct
22 Correct 192 ms 49124 KB Output is correct
23 Correct 191 ms 49456 KB Output is correct
24 Correct 225 ms 53252 KB Output is correct
25 Correct 218 ms 58316 KB Output is correct
26 Correct 148 ms 49172 KB Output is correct
27 Correct 180 ms 49148 KB Output is correct
28 Correct 198 ms 49388 KB Output is correct
29 Correct 216 ms 51936 KB Output is correct
30 Correct 242 ms 54604 KB Output is correct
31 Correct 172 ms 49160 KB Output is correct
32 Correct 187 ms 49256 KB Output is correct
33 Correct 203 ms 49632 KB Output is correct
34 Correct 217 ms 52944 KB Output is correct
35 Correct 225 ms 58032 KB Output is correct
36 Correct 199 ms 53196 KB Output is correct