Submission #907552

#	Time	Username	Problem	Language	Result	Execution time	Memory
907552		I_FloPPed21	Valley (BOI19_valley)	C++14	0 / 100	11 ms	33372 KiB

valley

#include <fstream>
#include <vector>
using namespace std;
ifstream cin("file.in");
ofstream cout("file.out");
int n, s, q, e ;
vector<pair<int,int>> edge [1000005];
long long tin[1000005], tout [1000005], shop [1000005], ext[1000005];
long long rev[ 1000005];
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[ 600005 ][ 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[600005][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);

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





    //cout << mag[2][0] << " " << " 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 ;
        }

        int dd ;

        if ( tg == a )
            dd = b;
        else
            dd = a;

        long long ans = jumps(r,dd) ;

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

        cout << ans  << '\n';

    }


    return 0;
}

Compilation message (stderr)

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

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