Submission #167420

# Submission time Handle Problem Language Result Execution time Memory
167420 2019-12-08T13:22:34 Z muhammad_hokimiyon Evacuation plan (IZhO18_plan) C++14
0 / 100
805 ms 53504 KB
#include <bits/stdc++.h>

//#pragma GCC optimize("Ofast")

#define fi first
#define se second
#define ll long long

using namespace std;

const int N = 1e5 + 7;
const int mod = 1e9 + 7;

int n,m,q,k;
int l = 1;
int cnt;
int a[N];
int d[N];
int p[N];
int tin[N];
int dep[N];
int tout[N];
bool used[N];
vector < int > g[N];
vector < vector < int > > up;
vector < vector < int > > mn;
vector < pair < int , int > > v[N];

int get( int x )
{
    return (x == p[x] ? x : p[x] = get(p[x]));
}

void dfs( int x , int p )
{
    mn[x][0] = d[x];
    up[x][0] = p;
    tin[x] = ++cnt;
    for( int i = 1; i <= l; i++ ){
        up[x][i] = up[up[x][i - 1]][i - 1];
        mn[x][i] = min( mn[x][i - 1] , mn[up[x][i - 1]][i - 1] );
    }
    for( auto y : g[x] ){
        if( y != p ){
            dep[y] = dep[x] + 1;
            dfs(y , x);
        }
    }
    tout[x] = cnt;
}

bool upper( int x , int y )
{
    return (tin[x] <= tin[y] && tout[x] >= tout[y]);
}

int lca( int x , int y )
{
    if( upper(x , y) )return x;
    if( upper(y , x) )return y;
    for( int i = l; i >= 0; i-- ){
        if( !upper(up[x][i] , y) ){
            x = up[x][i];
        }
    }
    return up[x][0];
}

int get( int x , int y )
{
    int ans = 1e9;
    for( int i = l; i >= 0; i-- ){
        if( y >= (1 << i) ){
            y -= (1 << i);
            ans = min( ans , mn[x][i] );
            x = up[x][i];
        }
    }
    return ans;
}

void solve()
{
    cin >> n >> m;
    while( (1 << l) <= n )l++;
    up.resize(n + 10);
    mn.resize(n + 10);
    for( int i = 0; i <= n; i++ ){
        up[i].resize(l + 10);
        mn[i].resize(l + 10);
        p[i] = i;
        d[i] = 1e9;
    }
    for( int i = 1; i <= m; i++ ){
        int x,y,z;
        cin >> x >> y >> z;
        v[x].push_back({y , z});
        v[y].push_back({x , z});
    }
    set < pair < int , int > > s;
    cin >> k;
    for( int i = 1; i <= k; i++ ){
        int x;
        cin >> x;
        d[x] = 0;
        s.insert({0 , x});
    }
    while( !s.empty() ){
        auto x = s.begin()->se;
        s.erase(s.begin());
        for( auto y : v[x] ){
            if( d[x] + y.se < d[y.fi] ){
                s.erase({d[y.fi] , y.fi});
                d[y.fi] = d[x] + y.se;
                s.insert({d[y.fi] , y.fi});
            }
        }
    }
    vector < pair < int , int > > vv;
    for( int i = 1; i <= n; i++ ){
        vv.push_back({d[i] , i});
    }
    int start = 0;
    sort( vv.rbegin() , vv.rend() );
    for( auto y : vv ){
        used[y.se] = true;
        for( auto z : v[y.se] ){
            int xx = get(z.fi);
            int yy = get(y.se);
            if( used[z.fi] && xx != yy ){
                p[yy] = xx;
                if( !start )start = y.se;
                g[z.fi].push_back(y.se);
                g[y.se].push_back(z.fi);
            }
        }
    }
    dfs(start , start);
    cin >> q;
    for( int i = 1; i <= q; i++ ){
        int x,y;
        cin >> x >> y;
        int c = lca(x , y);
        cout << min( get( x , dep[x] - dep[c] ) , get( y , dep[y] - dep[c] ) ) << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen( "input.txt" , "r" , stdin );
    //freopen( "output.txt" , "w" , stdout );

    int t = 1;//cin >> t;
    while( t-- ){
        solve();
    }
}
# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5100 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5100 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 397 ms 46616 KB Output is correct
2 Correct 805 ms 53428 KB Output is correct
3 Correct 723 ms 53404 KB Output is correct
4 Correct 275 ms 48536 KB Output is correct
5 Correct 710 ms 53344 KB Output is correct
6 Correct 734 ms 53400 KB Output is correct
7 Correct 728 ms 53440 KB Output is correct
8 Correct 704 ms 53360 KB Output is correct
9 Correct 741 ms 53428 KB Output is correct
10 Correct 746 ms 53460 KB Output is correct
11 Correct 717 ms 53448 KB Output is correct
12 Correct 737 ms 53428 KB Output is correct
13 Correct 783 ms 53360 KB Output is correct
14 Correct 746 ms 53388 KB Output is correct
15 Correct 714 ms 53360 KB Output is correct
16 Correct 703 ms 53484 KB Output is correct
17 Correct 746 ms 53372 KB Output is correct
18 Correct 757 ms 53504 KB Output is correct
19 Incorrect 285 ms 48600 KB Output isn't correct
20 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5100 KB Output isn't correct
2 Halted 0 ms 0 KB -