Submission #229190

#	Time	Username	Problem	Language	Result	Execution time	Memory
229190		DodgeBallMan	Evacuation plan (IZhO18_plan)	C++14	31 / 100	629 ms	50668 KiB

plan

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

using namespace std;

const int N = 1e5 + 10;
int n, m, dp[21][2*N], d[2*N], mn[2*N], dep[2*N], k, Q, par[2*N], cnt;
vector<int> t[2*N];
vector<pii> g[N], all;
priority_queue<pii> q;
void dijk() {
    //fill( d, d+N, 2e9 );
    while( !q.empty() ) {
        pii temp = q.top(); q.pop();
        //printf("%d\n",temp.y);
        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 = cnt, int p = 0 ) {
    //printf("%d\n",u);
    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 );
        if( u > n ) mn[u] = min( mn[u], mn[v] );
    }
}

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("%d %d",&n,&m);
    for( int i = 0, a, b, c ; i < m ; i++ ) {
        scanf("%d %d %d",&a,&b,&c);
        g[a].emplace_back( pii( b, c ) ), g[b].emplace_back( pii( a, c ) );
    }
    scanf("%d",&k);
    fill( d, d+2*N, 2e9 );
    for( int i = 0, a ; i < k ; i++ ) {
        scanf("%d",&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;
    cnt = n;
    //printf("NODE : ");
    for( pii i : all ) {
        int u = i.y, di = i.x;
        //printf("%d ",u);
        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[a] = par[b] = ++cnt;
                t[cnt].emplace_back( a ), t[cnt].emplace_back( b );
            }
        }
    }
    /*printf("\n");
    for( int i = 1 ; i <= cnt ; i++ ) {
        printf("%d : ",i);
        for( int v : t[i] ) printf("%d ",v);
        printf("\n");
    }*/
    for( int i = 1 ; i <= cnt ; i++ ) mn[i] = d[i];
    dfs();
    /*for( int i = 1 ; i <= n ; i++ ) printf("%d ",d[i]);
    printf("\n");
    for( int i = 1 ; i <= cnt ; i++ ) printf("%d ",mn[i]);
    printf("\n");*/
    scanf("%d",&Q);
    for( int i = 0, a, b ; i < Q ; i++ ) {
        scanf("%d %d",&a,&b);
        int c = lca( a, b );
        printf("%d\n", mn[c] );
    }
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:71:22: warning: unused variable 'di' [-Wunused-variable]
         int u = i.y, di = i.x;
                      ^~
plan.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~
plan.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&a,&b,&c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~
plan.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&k);
     ~~~~~^~~~~~~~~
plan.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a);
         ~~~~~^~~~~~~~~
plan.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&Q);
     ~~~~~^~~~~~~~~
plan.cpp:97: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: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 0 / 46