Submission #881058

#	Time	Username	Problem	Language	Result	Execution time	Memory
881058		anha3k25cvp	Evacuation plan (IZhO18_plan)	C++14	100 / 100	545 ms	36644 KiB

plan

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>

using namespace std;

const int N = 5 + 1e5;
const int inf = 7 + 1e9;

struct Edge {
    int u, v, w;
    bool operator <(const Edge &O) const {
        return w > O.w;
    }
};

struct Query {
    int u, v, id, lo, hi, mid;
    bool operator <(const Query &O) const {
        return mid > O.mid;
    }
};

struct Dsu {
    int n;
    vector <int> root;
    Dsu (int _n = 0) : n(_n) {
        root.assign(n + 1, 0);
        for (int i = 1; i <= n; i ++)
            root[i] = i;
    }
    int getroot(int u) {
        return u == root[u] ? u : root[u] = getroot(root[u]);
    }
    void unite(int u, int v) {
        u = getroot(u); v = getroot(v);
        if (u == v)
            return;
        root[v] = u;
    }
};

int main() {
#define TASKNAME ""
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    if ( fopen( TASKNAME".inp", "r" ) ) {
        freopen (TASKNAME".inp", "r", stdin);
        freopen (TASKNAME".out", "w", stdout);
    }
    int n, m;
    cin >> n >> m;
    vector <vector <II>> adj(n + 1);
    vector <Edge> E(m + 1);
    for (int i = 1; i <= m; i ++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        E[i] = {u, v, 0};
    }
    vector <int> f(n + 1, inf);
    priority_queue <II> q;
    int k;
    cin >> k;
    while (k --) {
        int u;
        cin >> u;
        q.push({-(f[u] = 0), u});
    }
    while (!q.empty()) {
        int du = -q.top().st, u = q.top().nd;
        q.pop();
        if (f[u] < du)
            continue;
        for (auto z : adj[u]) {
            int v = z.st, w = z.nd;
            if (du + w < f[v])
                q.push({-(f[v] = du + w), v});
        }
    }
    for (int i = 1; i <= m; i ++)
        E[i].w = min(f[E[i].u], f[E[i].v]);
    sort(E.begin() + 1, E.end());
    int t;
    cin >> t;
    vector <Query> e(t + 1);
    for (int i = 1; i <= t; i ++) {
        cin >> e[i].u >> e[i].v;
        e[i].id = i;
        e[i].lo = 0;
        e[i].hi = inf;
    }
    while (1) {
        int check = 0;
        for (int i = 1; i <= t; i ++)
            if (e[i].lo < e[i].hi) {
                e[i].mid = (e[i].lo + e[i].hi + 1) / 2;
                check = 1;
            }
        if (!check)
            break;
        sort(e.begin() + 1, e.end());
        Dsu D(n);
        int pos = 1;
        for (int i = 1; i <= t; i ++) {
            while (pos <= m && E[pos].w >= e[i].mid) {
                D.unite(E[pos].u, E[pos].v);
                pos ++;
            }
            if (D.getroot(e[i].u) == D.getroot(e[i].v))
                e[i].lo = e[i].mid;
            else
                e[i].hi = e[i].mid - 1;
        }
    }
    vector <int> ans(t + 1, 0);
    for (int i = 1; i <= t; i ++)
        ans[e[i].id] = e[i].lo;
    for (int i = 1; i <= t; i ++)
        cout << ans[i] << '\n';
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:52:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen (TASKNAME".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:53:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen (TASKNAME".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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