Submission #945414

#	Time	Username	Problem	Language	Result	Execution time	Memory
945414		LucaIlie	Valley (BOI19_valley)	C++17	100 / 100	271 ms	32112 KiB

valley

#include <bits/stdc++.h>

using namespace std;

struct edge {
    int u, v, w;

    int other( int x ) {
        return u ^ v ^ x;
    }
};

struct query {
    int v, e;
};

struct SegTree {
    int l, r;
    long long zero;
    vector<long long> aint;

    void init( int _l, int _r, long long _zero ) {
        l = _l;
        r = _r;
        zero = _zero;
        aint.resize( 4 * (r - l + 1) );
        for ( int v = 0; v < aint.size(); v++ )
            aint[v] = zero;
    }

    void update( int v, int l, int r, int p, long long x ) {
        if ( l > p || r < p )
            return;

        if ( l == r ) {
            aint[v] = x;
            return;
        }

        int mid = (l + r) / 2;
        update( v * 2 + 1, l, mid, p, x );
        update( v * 2 + 2, mid + 1, r, p, x );
        aint[v] = min( aint[v * 2 + 1], aint[v * 2 + 2] );
    }

    void update( int p, long long x ) {
        update( 0, l, r, p, x );
    }

    long long query( int v, int l, int r, int lq, int rq ) {
        if ( l > rq || r < lq )
            return zero;

        if ( lq <= l && r <= rq )
            return aint[v];

        int mid = (l + r) / 2;
        return min( query( v * 2 + 1, l, mid, lq, rq ), query( v * 2 + 2, mid + 1, r, lq, rq ) );
    }

    long long query( int lq, int rq ) {
        return query( 0, l, r, lq, rq );
    }
};

const int MAX_N = 1e5;
const int MAX_Q = 1e5;
const long long INF = 1e15;
bool isShop[MAX_N + 1];
int pos[MAX_N + 1];
long long depth[MAX_N + 1], distShop[MAX_N + 1], ans[MAX_Q + 1];
edge edges[MAX_N];
query queries[MAX_Q];
vector<int> adj[MAX_N + 1], queriesByVert[MAX_N + 1];
SegTree minDist;

void calc( int u, int p ) {
    distShop[u] = (isShop[u] ? 0 : INF);
    for ( int e: adj[u] ) {
        int v = edges[e].other( u ), w = edges[e].w;
        if ( v == p )
            continue;

        depth[v] = depth[u] + w;
        calc( v, u );
        distShop[u] = min( distShop[u], distShop[v] + w );
    }
}

void solve( int u, int p, int d ) {
    minDist.update( d, distShop[u] - depth[u] );
    pos[u] = d;
    for ( int e: adj[u] ) {
        int v = edges[e].other( u );
        if ( v == p )
            continue;
        solve( v, u, d + 1 );
    }

    for ( int q: queriesByVert[u] ) {
        int v = (depth[edges[queries[q].e].u] < depth[edges[queries[q].e].v] ? edges[queries[q].e].v : edges[queries[q].e].u);
        if ( pos[v] == 0 )
            ans[q] = -1;
        else
            ans[q] = minDist.query( pos[v], pos[u] ) + depth[u];
    }

    minDist.update( d, INF );
    pos[u] = 0;
}

int main() {
    int n, s, q, e;

    cin >> n >> s >> q >> e;
    for ( int i = 1; i <= n - 1; i++ ) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        adj[edges[i].u].push_back( i );
        adj[edges[i].v].push_back( i );
    }
    for ( int i = 0; i < s; i++ ) {
        int v;
        cin >> v;
        isShop[v] = true;
    }
    for ( int i = 0; i < q; i++ ) {
        cin >> queries[i].e >> queries[i].v;
        queriesByVert[queries[i].v].push_back( i );
    }

    minDist.init( 1, n, INF );
    calc( e, 0 );
    solve( e, 0, 1 );

    for ( int i = 0; i < q; i++ ) {
        if ( ans[i] == -1 )
            cout << "escaped\n";
        else if ( ans[i] == INF )
            cout << "oo\n";
        else
            cout << ans[i] << "\n";
    }

    return 0;
}

Compilation message (stderr)

valley.cpp: In member function 'void SegTree::init(int, int, long long int)':
valley.cpp:27:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for ( int v = 0; v < aint.size(); v++ )
      |                          ~~^~~~~~~~~~~~~

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