제출 #907535

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
907535		I_FloPPed21	Valley (BOI19_valley)	C++14	23 / 100	194 ms	51716 KiB

valley

#include <iostream>
#include <vector>
using namespace std;

int n, s, q, e ;
vector<pair<int,int>> edge [200005];
long long tin[200005], tout [200005], shop [200005], ext[200005];
long long rev[ 200005];
vector<int> v;
void dfs ( int nod,int p )
{
    v.push_back(nod);
    if (tin[nod] == 0 )
    {
        tin [nod] = v.size() ;
    }
    for ( auto u : edge[nod] )
    {
        if ( u.first != p)
        {
            dfs (u.first, nod );
            v.push_back(nod);
        }
    }

    tout[nod] = v.size();
}

long long jmp[ 200005 ][ 19] ;

void dfs4(int nod, int p )
{

    for ( auto u :edge[nod])
    {
        if ( u.first != p )
        {
            rev[u.first] = rev[nod] + u.second;
            dfs4(u.first,nod);
        }
    }

}
void dfs2 ( int nod, int p )
{
    for ( auto u : edge[nod])
    {
        if ( u.first != p )
        {
            dfs2 (u.first, nod);
        }
    }

    if (shop [nod] == 1 )
        ext[nod] = rev[nod];
    else
        ext[nod] = 1e18 ;

    for ( auto u : edge[nod] )
    {
        if ( u.first != p )
        {
            ext[nod] = min ( ext[nod], ext[u.first]);
        }
    }
}
long long mag[200005][18];
void dfs3 ( int nod, int p )
{
    jmp[nod][0] = p;
    mag[nod][0] = ext[nod];

    for ( int k = 1 ; k <= 18 ; k ++ )
    {
        jmp[nod][k] = jmp[jmp[nod][k-1]][k-1];
        mag[nod][k] = min(mag[nod][k-1], mag[jmp[nod][k-1]][k-1]);
    }

    for ( auto u : edge[nod] )
    {
        if (u .first != p)
            dfs3(u.first,nod);
    }
}
vector<pair<int,int>> qr;
long long jumps( int nod, int p )
{

    long long ans = 1e18 ;
    long long u = nod ;
    for ( int k = 18 ; k >= 0 ; k -- )
    {
        int a = tin[p];
        int b = tout[p];
        int c = tin[jmp[u][k]];
        int d = tout[jmp[u][k] ] ;

        if( a <= c && d <= b)
        {
            ans = min ( ans, mag[u][k]);
            u = jmp[u][k];
        }
    }

    ans = min ( ans, ext[p]);

    return ans ;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> s >> q >> e;

    for ( int i =1; i < n ; i ++ )
    {
        int a, b,c;
        cin >> a >> b>>c;
        edge[a].push_back({b,c});
        edge[b].push_back({a,c});
        qr.push_back({a,b});
    }
    for( int i = 1; i <= s; i ++ )
    {
        int val;
        cin >> val ;
        shop [val] = 1;
    }
    dfs(e,0);
    dfs4(e,0);
    dfs2(e,0);
    dfs3(e,0);

    for ( int i = 1; i <= n ; i ++ )
        ext [i] -= 2 * rev[i];



    //cout << ext[4] << " " << " hsb" << '\n';
    for ( int i = 1; i <= q; i ++ )
    {
        int l, r;
        cin >> l >> r ;
        l -- ;
        int  a = qr[l].first;
        int b = qr[l].second;

        int tg ;

        if ( tin[a] < tin[b] && tout[a] > tout[b])
            tg =b ;
        else
            tg = a;

        if ( tin[tg] <= tin[r] && tout[tg] >= tout[r])
        {

        }
        else
        {
            cout << "escaped" << '\n';
            continue ;
        }

        long long ans = jumps(r,tg) ;

        ans += rev[r];
        ans = min ( ans , ext[r] + rev[ r]) ;
        if ( ans >= 1e17 )
        {
            cout << "oo" << '\n';
            continue;
        }

        cout << ans  << '\n';

    }


    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

valley.cpp: In function 'void dfs3(int, int)':
valley.cpp:76:21: warning: iteration 17 invokes undefined behavior [-Waggressive-loop-optimizations]
   76 |         mag[nod][k] = min(mag[nod][k-1], mag[jmp[nod][k-1]][k-1]);
      |         ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:73:25: note: within this loop
   73 |     for ( int k = 1 ; k <= 18 ; k ++ )
      |                       ~~^~~~~

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