Submission #1233119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233119		fermat	Evacuation plan (IZhO18_plan)	C++20	100 / 100	452 ms	52096 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, h[N];

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)
{
    h[v] = h[pr] + 1;
    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 lca (int a, int b)
{
    if(upper(a, b)) return a;
    if(upper(b, a)) return b;

    for (int i = 19; i >= 0; i--)
    {
        if ( up[i][a] && !upper( up[i][a], b ) )
            a = up[i][a];
    }
    return up[0][a];
}
int minjump(int v, int d)
{
    if (d == 0)
  return ar[v];

 int res = ar[v];
 for (int i = 0; d; i++, d >>= 1) {
  if (d & 1) {
   res = min(res, mn[i][v]);
   v = up[i][v];
  }
 }
 return res;
}
int ans (int a, int b)
{
    int c = lca(a, b);

    return min( minjump( a, h[a] - h[c]), minjump( b, h[b] - h[c]) );
}
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));
    }
}

Compilation message (stderr)

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

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