Submission #76740

#	Time	Username	Problem	Language	Result	Execution time	Memory
76740		antimirage	Evacuation plan (IZhO18_plan)	C++17	19 / 100	851 ms	52104 KiB

plan

#include <bits/stdc++.h>

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 1e5 + 5;

int n, m, x, y, w, ar[N], p[N], sz[N], up[20][N], mn[20][N], tin[N], tout[N], tiktak;

vector < vector <pair <int, int> > > g;

vector < vector <int> > r;

vector < pair <int, pair <int, int> > > vec;

priority_queue <pair <int, int> > q;

int get (int x)
{
    return x == p[x] ? x : p[x] = get(p[x]);
}
void unite (int x, int y)
{
    if (sz[x] > sz[y]) swap(x, y);

    sz[y] += sz[x];
    p[x] = y;
}
void dfs (int v, int pr = 0)
{
    tin[v] = ++tiktak;
    up[0][v] = pr;
    mn[0][v] = min(ar[pr], ar[v]);
    for (int i = 1; i < 20; i++)
    {
        up[i][v] = up[i - 1][ up[i - 1][v] ];
        mn[i][v] = min(  mn[i - 1][v], mn[i - 1][ up[i - 1][v] ] );
    }
    for (auto to : r[v])
    {
        if (to == pr) continue;
        dfs(to, v);
    }
    tout[v] = ++tiktak;
}
bool upper (int a, int b)
{
    return tin[a] <= tin[b] && tout[b] <= tout[a];
}
int ans (int a, int b)
{
    int res = min(ar[a], ar[b]), v = a;
    for (int i = 19; i >= 0; i--)
    {
        if ( up[i][a] && !upper( up[i][a], b ) )
            res = min(res, mn[i][a]), a = up[i][a];
    }
    res = min(res, ar[ up[0][a] ]);
    a = v;
    for (int i = 19; i >= 0; i--)
    {
        if ( up[i][b] && !upper( up[i][b], a ) )
            res = min(res, mn[i][b]), b = up[i][b];
    }
    return res;
}
main()
{
    cin >> n >> m;
    g.resize(n + 1);
    r.resize(n + 1);

    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &x, &y, &w);
        g[x].pb( mk(y, w) );
        g[y].pb( mk(x, w) );
    }
    memset( ar, 0x3f3f3f3f, sizeof(ar) );
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d", &x);
        q.push( mk( 0, x ) );
        ar[x] = 0;
    }
    while (!q.empty())
    {
        w = -q.top().fr, x = q.top().sc;
        q.pop();

        if (ar[x] < w) continue;

        for (auto to : g[x])
        {
            if (ar[x] + to.sc < ar[to.fr])
            {
                ar[to.fr] = ar[x] + to.sc;
                q.push( mk( -ar[to.fr], to.fr ) );
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        p[i] = i;
        sz[i] = 1;
        for (auto to : g[i])
            vec.pb( mk( min( ar[i], ar[to.fr] ), mk( i, to.fr ) ) );
    }
    sort( all(vec), greater < pair <int, pair <int, int> > >() );

    for (auto it : vec)
    {
        x = it.sc.fr, y = it.sc.sc;
        if (get(x) != get(y))
        {
            r[x].pb(y);
            r[y].pb(x);
            unite(get(x), get(y) );
        }
    }
    dfs(1);
    cin >> m;
    while (m--)
    {
        scanf("%d%d", &x, &y);
        printf("%d\n", ans(x, y));
    }
}
/**
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
**/

Compilation message (stderr)

plan.cpp:73:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
plan.cpp: In function 'int main()':
plan.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &x, &y, &w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~
plan.cpp:132:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

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