Submission #93205

#	Time	Username	Problem	Language	Result	Execution time	Memory
93205		SamAnd	Evacuation plan (IZhO18_plan)	C++17	100 / 100	939 ms	50928 KiB

plan

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 100005;
const int INF = 1000000007;
struct ban
{
    int x, d;
    ban(){}
    ban(int x, int d)
    {
        this->x = x;
        this->d = d;
    }
};
bool operator<(const ban& a, const ban& b)
{
    return a.d > b.d;
}

int n, m;
vector<ban> a[N];
int k;
int b[N];

int d[N];
bool c[N];
void djk()
{
    priority_queue<ban> q;
    for (int i = 0; i < k; ++i)
    {
        q.push(ban(b[i], 0));
    }
    while (1)
    {
        ban t;
        do
        {
            if (q.empty())
                return;
            t = q.top();
            q.pop();
        } while (c[t.x]);
        c[t.x] = true;
        d[t.x] = t.d;
        for (int i = 0; i < a[t.x].size(); ++i)
        {
            ban h = a[t.x][i];
            h.d += t.d;
            if (!c[h.x])
                q.push(h);
        }
    }
}

int p[N];
int fi(int x)
{
    if (p[x] == x)
        return x;
    return p[x] = fi(p[x]);
}

void kpc(int x, int y)
{
    x = fi(x);
    y = fi(y);
    p[x] = y;
}

vector<ban> g[N];
void kru()
{
    vector<pair<int, pair<int, int> > > v;
    for (int x = 1; x <= n; ++x)
    {
        for (int i = 0; i < a[x].size(); ++i)
        {
            int y = a[x][i].x;
            v.push_back(m_p(min(d[x], d[y]), m_p(x, y)));
        }
    }
    sort(v.begin(), v.end());
    for (int i = 1; i <= n; ++i)
        p[i] = i;
    for (int i = v.size() - 1; i >= 0; --i)
    {
        int x = v[i].second.first;
        int y = v[i].second.second;
        int z = v[i].first;
        if (fi(x) == fi(y))
            continue;
        kpc(x, y);
        g[x].push_back(ban(y, z));
        g[y].push_back(ban(x, z));
    }
}

int l = 20;
int pp[N][30], minu[N][30];
int tim;
int tin[N], tout[N];
void dfs(int x, int cp, int ck)
{
    tin[x] = tim++;
    pp[x][0] = cp;
    minu[x][0] = ck;
    for (int i = 1; i <= l; ++i)
    {
        pp[x][i] = pp[pp[x][i - 1]][i - 1];
        minu[x][i] = min(minu[x][i - 1], minu[pp[x][i - 1]][i - 1]);
    }
    for (int i = 0; i < g[x].size(); ++i)
    {
        ban h = g[x][i];
        if (h.x == cp)
            continue;
        dfs(h.x, x, h.d);
    }
    tout[x] = tim++;
}

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

int go(int x, int y)
{
    if (par(x, y))
        return INF;
    int res = INF;
    for (int i = l; i >= 0; --i)
    {
        if (!par(pp[x][i], y))
        {
            res = min(res, minu[x][i]);
            x = pp[x][i];
        }
    }
    res = min(res, minu[x][0]);
    return res;
}

int qry(int x, int y)
{
    return min(go(x, y), go(y, x));
}

int main()
{
    //freopen("input2.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        a[x].push_back(ban(y, z));
        a[y].push_back(ban(x, z));
    }
    scanf("%d", &k);
    for (int i = 0; i < k; ++i)
        scanf("%d", &b[i]);
    djk();
    kru();
    dfs(1, 1, INF);
    int q;
    scanf("%d", &q);
    while (q--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%d\n", qry(x, y));
    }
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'void djk()':
plan.cpp:47:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < a[t.x].size(); ++i)
                         ~~^~~~~~~~~~~~~~~
plan.cpp: In function 'void kru()':
plan.cpp:78:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < a[x].size(); ++i)
                         ~~^~~~~~~~~~~~~
plan.cpp: In function 'void dfs(int, int, int)':
plan.cpp:114:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:154: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:158:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &x, &y, &z);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:162:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
plan.cpp:164:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b[i]);
         ~~~~~^~~~~~~~~~~~~
plan.cpp:169:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
plan.cpp:173: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: 19 / 19
• Subtask 5: 46 / 46