Submission #76763

#	Time	Username	Problem	Language	Result	Execution time	Memory
76763		antimirage	Evacuation plan (IZhO18_plan)	C++17	35 / 100	496 ms	22124 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], u[N];

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

vector < vector <int> > r;

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

priority_queue <pair <int, int> > q;

void dfs (int v, int porog)
{
    u[v] = 1;
    for (auto to : g[v])
    {
        if (u[to.fr] || ar[to.fr] < porog) continue;
        dfs(to.fr, porog);
    }
}

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 ) );
            }
        }
    }
    cin >> m;
    while (m--)
    {
        scanf("%d%d", &x, &y);

        if (n > 1000)
        {
            printf("%d\n", min(ar[x], ar[y]) );
        }
        else
        {
            int l = 0, r = 1e9 + 7;
            while (r - l > 1)
            {
                int md = (l + r) >> 1;
                dfs(x, md);
                if (ar[x] >= md && u[y])
                    l = md;
                else
                    r = md;

                for (int j = 1; j <= n; j++) u[j] = 0;
            }
            printf("%d\n", l);
        }
    }
}
/**
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:34:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
plan.cpp: In function 'int main()':
plan.cpp:42: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:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~
plan.cpp:73: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: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46