Submission #229204

#	Time	Username	Problem	Language	Result	Execution time	Memory
229204		DodgeBallMan	Evacuation plan (IZhO18_plan)	C++14	0 / 100	635 ms	62820 KiB

plan

#include <bits/stdc++.h>
#define pii pair<long long, long long>
#define x first
#define y second

using namespace std;

const int N = 1e5 + 10;
long long n, m, dp[21][2*N], d[2*N], mn[2*N], dep[2*N], k, Q, par[2*N], cnt;
vector<long long> t[2*N];
vector<pii> g[N], all;
priority_queue<pii> q;

void dijk() {
    while( !q.empty() ) {
        pii temp = q.top(); q.pop();
        for( pii i : g[temp.y] ) {
            int v = i.x, di = i.y - temp.x;
            if( di < d[v] ) { d[v] = di; q.emplace( -1*di, v ); }
        }
    }
}

void dfs( int u, int p ) {
    dp[0][u] = p;
    dep[u] = dep[p] + 1;
    for( int i = 1 ; i < 20 ; i++ ) dp[i][u] = dp[i-1][dp[i-1][u]];
    for( int v : t[u] ) if( v != p ) dfs( v, u );
}

int lca( int a, int b ) {
    if( dep[a] < dep[b] ) swap( a, b );
    for( int i = 19 ; i >= 0 ; i-- ) if( dep[dp[i][a]] >= dep[b] ) a = dp[i][a];
    if( a == b ) return a;
    for( int i = 19 ; i >= 0 ; i-- ) if( dp[i][a] != dp[i][b] ) a = dp[i][a], b = dp[i][b];
    return dp[0][a];
}

int findroot( int a ) {
    if( a == par[a] ) return a;
    else return par[a] = findroot( par[a] );
}

int main()
{
    scanf("%lld %lld",&n,&m);
    for( int i = 0, a ; i < m ; i++ ) {
        long long b, c;
        scanf("%d %lld %lld",&a,&b,&c);
        g[a].emplace_back( pii( b, c ) ), g[b].emplace_back( pii( a, c ) );
    }
    scanf("%lld",&k);
    fill( d, d+2*N, 1e17 );
    for( int i = 0 ; i < k ; i++ ) {
        long long a;
        scanf("%lld",&a);
        d[a] = 0;
        q.emplace( 0, a );
    }
    dijk();
    //printf("HEY");
    for( int i = 1 ; i <= n ; i++ ) all.emplace_back( pii( d[i], i ) );
    sort( all.begin(), all.end(), greater<pii>() );
    for( int i = 1 ; i <= 2*n ; i++ ) par[i] = i;
    for( pii i : all ) {
        int u = i.y, di = i.x;
        for( pii x : g[u] ) {
            int v = x.x;
            if( d[v] > d[u] ) {
                int a = findroot( u ), b = findroot( v );
                if( a == b ) continue ;
                par[b] = a;
                t[a].emplace_back( b ), t[b].emplace_back( a );
            }
        }
    }
    fill( mn, mn+2*N, 1e17 );
    dfs( all.back().y, 0 );
    scanf("%d",&Q);
    for( int i = 0, a, b ; i < Q ; i++ ) {
        scanf("%d %d",&a,&b);
        int c = lca( a, b );
        printf("%lld\n",d[c] );
    }
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:66:22: warning: unused variable 'di' [-Wunused-variable]
         int u = i.y, di = i.x;
                      ^~
plan.cpp:79:18: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
     scanf("%d",&Q);
                ~~^
plan.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~~~~~
plan.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %lld %lld",&a,&b,&c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&k);
     ~~~~~^~~~~~~~~~~
plan.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&a);
         ~~~~~^~~~~~~~~~~
plan.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&Q);
     ~~~~~^~~~~~~~~
plan.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46