Submission #133427

#	Time	Username	Problem	Language	Result	Execution time	Memory
133427		Kastanda	Evacuation plan (IZhO18_plan)	C++11	100 / 100	651 ms	26100 KiB

plan

// ItnoE
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, m, q, k, D[N], P[N], S[N], R[N];
vector < pair < int , int > > Adj[N];
vector < pair < int , int > > Q[N];
inline bool CMP(int i, int j)
{
    return (D[i] > D[j]);
}
int Find(int v)
{
    return (P[v] < 0 ? v : (P[v] = Find(P[v])));
}
inline void Merge(int v, int u, int w)
{
    v = Find(v);
    u = Find(u);
    if (v == u)
        return ;
    if (Q[v].size() < Q[u].size())
        swap(v, u);
    for (auto X : Q[u])
        if (Find(X.first) == v)
            R[X.second] = w;
        else
            Q[v].push_back(X);
    Q[u].clear();
    P[u] = v;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i ++)
    {
        int v, u, w;
        scanf("%d%d%d", &v, &u, &w);
        Adj[v].push_back({u, w});
        Adj[u].push_back({v, w});
    }
    memset(D, 63, sizeof(D));
    priority_queue < pair < int , int > > Pq;
    scanf("%d", &k);
    for (int v; k; k --)
        scanf("%d", &v), D[v] = 0, Pq.push({0, v});
    while (Pq.size())
    {
        int v = Pq.top().second;
        int d = - Pq.top().first;
        Pq.pop();
        if (d > D[v]) continue;
        for (auto u : Adj[v])
            if (D[u.first] > D[v] + u.second)
                D[u.first] = D[v] + u.second,
                Pq.push({-D[u.first], u.first});
    }
    scanf("%d", &q);
    for (int i = 1; i <= q; i ++)
    {
        int v, u;
        scanf("%d%d", &v, &u);
        Q[v].push_back({u, i});
        Q[u].push_back({v, i});
    }
    memset(P, -1, sizeof(P));
    iota(S, S + n + 1, 0);
    sort(S + 1, S + n + 1, CMP);
    for (int j = 1; j <= n; j ++)
    {
        int v = S[j];
        for (auto u : Adj[v])
            if (D[u.first] >= D[v])
                Merge(v, u.first, D[v]);
    }
    for (int i = 1; i <= q; i ++)
        printf("%d\n", R[i]);
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:34: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:38:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &v, &u, &w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
plan.cpp:46:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &v), D[v] = 0, Pq.push({0, v});
         ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
plan.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &v, &u);
         ~~~~~^~~~~~~~~~~~~~~~

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