oj.uz

답안 #609061

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
609061 2022-07-27T12:00:50 Z mayureshpatle Valley (BOI19_valley) C++17
23 / 100
 211 ms 48816 KB 
/**************************************************************
Submitted By: Mayuresh N. Patle
Written On: Wednesday, July 27, 2022
**************************************************************/

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define mod1 998244353
#define rep(i,s,e) for(i=s;i<e;++i)
#define repr(i,s,e) for(i=s;i>e;--i)
#define fp(i) fixed<<setprecision(i)
#define in(a) for(auto &ghe:a) cin>>ghe;
#define in2d(a) for(auto &ghe:a) for(auto &he:ghe) cin>>he;
#define out(a) for(auto &ghe:a) cout<<ghe<<" ";cout<<endl;
#define out2d(a) {for(auto &he:a) {out(he)}}
#define loop(i,a) for(auto &i:a)
#define inrange(i,j,k) (((i)<=(j)) && ((j)<(k)))
#define make(a,i) memset(a,i,sizeof(a))
#define chk(x) cerr<<(#x)<<":"<<(x)<<endl;
#define chk2(x,y) cerr<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<endl;
#define chk3(x,y,z) cerr<<(#x)<<":"<<(x)<<" "<<(#y)<<":"<<(y)<<" "<<(#z)<<":"<<(z)<<endl;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector <ll> vll;
typedef vector <float> vf;
typedef vector <ld> vld;
#define pb push_back
#define pob() pop_back()
typedef pair <ll,ll> pll;
#define F first
#define S second
#define mp(a,b) make_pair(a,b)
typedef vector <pll> vp;
typedef vector <bool> flags;
#define all(v) begin(v),end(v)
#define amin(var, val) var = (val)<var ? (val) : var
#define amax(var, val) var = (val)>var ? (val) : var

class edge
{
    public:
    ll u,v,w;
    edge (){}
    edge (ll u, ll v, ll w): u(u), v(v), w(w){}
    ll op(ll x) {return x^u^v;}
};

const ll N=1e5+1, h=18, oo=1e18;
vll G[N];
vector <edge> e;

ll up[N][h], dp[N][h], val[N];
ll dist[N], tin[N], tout[N], _t=0;

ll sd[N], s[N];

void dfs(ll v, ll p)
{
    tin[v] = ++_t;

    up[v][0] = p;
    dist[v] += dist[p];

    sd[v] = oo;
    if(s[v]) sd[v] = dist[v];

    loop(i, G[v])
    {
        ll u=e[i].op(v), w=e[i].w;
        if(u==p) continue;
        dist[u] = w;     
        dfs(u,v);
        e[i].v = u;
        e[i].u = v;
        amin(sd[v], sd[u]);
    }

    dp[v][0] = oo;
    if(sd[v]!=oo) dp[v][0] = sd[v] - 2ll*dist[v];
    val[v] = dp[v][0];

    tout[v] = ++_t;
}

bool is_anc(ll p, ll v)
{
    return tin[p]<=tin[v] and tout[p]>=tout[v];
}

ll get(ll v,ll p)
{
    ll i, ans=val[p];
    rep(i,0,h)
    {
        if(is_anc(p, up[v][i])) amin(ans, dp[v][i]), v=up[v][i];
    }

    return ans;
}


void preprocess()
{
    
    return;
}

void solve()
{
    ll n,m,q,r,i;

    cin>>n>>m>>q>>r;
    rep(i,1,n)
    {
        ll u,v,w;
        cin>>u>>v>>w;
        G[u].pb(e.size());
        G[v].pb(e.size());
        e.pb(edge(u,v,w));
    }

    while(m--) cin>>i, s[i]=1;

    loop(v, dp) loop(i, v) i=oo;

    dfs(r, 0);

    rep(i,1,h) rep(r,1,n+1) 
    {
        dp[r][i] = min(dp[r][i-1], dp[up[r][i-1]][i-1]);
        up[r][i] = up[up[r][i-1]][i-1];
    }

    while(q--)
    {
        cin>>i>>r;
        --i;
        ll v = e[i].v;
        if(!is_anc(v, r)) cout<<"escaped\n";
        else
        {
            ll ans = get(r, v);
            if(ans==oo) cout<<"oo\n";
            else cout<<ans+dist[r]<<"\n";
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll T=1,i;
    //cin>>T;
    preprocess();
    rep(i,0,T)
    {
        //cout<<"Case #"<<i+1<<": ";
        solve();
    }
    return 0;
}

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 16864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 16864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 148 ms 42360 KB Output is correct
2 Correct 211 ms 45088 KB Output is correct
3 Correct 186 ms 45000 KB Output is correct
4 Correct 190 ms 46784 KB Output is correct
5 Correct 188 ms 46892 KB Output is correct
6 Correct 209 ms 48816 KB Output is correct

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 16864 KB Output isn't correct
2 Halted 0 ms 0 KB -