Submission #1040369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040369		Yang8on	Evacuation plan (IZhO18_plan)	C++14	100 / 100	613 ms	54432 KiB

plan

#include <bits/stdc++.h>
#define Y8o "Evacuation plan"
#define maxn (int) 1e5 + 5
#define ll long long
#define pii pair<ll, ll>
#define gb(i, j) ((i >> j) & 1)
#define all(x) x.begin(), x.end()
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r

//#define f first
//#define s second

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r) (rng);
}
void iof() {
    if(fopen(Y8o".inp", "r"))
    {
        freopen(Y8o".inp", "r", stdin);
//        freopen(Y8o".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);
}
void ctime() {
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}


int n, m, k, Q, a[maxn];
pii qr[maxn];
vector<pii> o[maxn], st;

int lim[maxn];
void dij() {
    for(int i = 1; i <= n; i ++) lim[i] = 1e9;
    priority_queue<pii> q;
    for(int i = 1; i <= k; i ++) {
        lim[ a[i] ] = 0, q.push({ -lim[a[i]], a[i] });
    }

    while(q.size()) {
        int val = -q.top().first, u = q.top().second;
        q.pop();

        if(lim[u] != val) continue;

        for(pii x : o[u]) {
            int v, w; tie(v, w) = x;
            if(lim[v] > lim[u] + w) {
                lim[v] = lim[u] + w;
                q.push({ -lim[v], v });
            }
        }
    }
}

vector<int> cur[maxn];
int L[maxn], R[maxn];
int dd[maxn], root[maxn], sz[maxn];
int get(int x) { return x == root[x] ? x : root[x] = get(root[x]); }
void uni(int u, int v) {
    int p = get(u), q = get(v);
    if(p != q) {
        if(sz[p] < sz[q]) swap(p, q);
        sz[p] += sz[q], root[q] = p;
    }
}

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i ++) {
        int u, v, w; cin >> u >> v >> w;
        o[u].push_back({ v, w }), o[v].push_back({ u, w });
    }
    cin >> k;
    for(int i = 1; i <= k; i ++) {
        cin >> a[i];
    }
    cin >> Q;
    for(int i = 1; i <= Q; i ++) {
        int u, v; cin >> u >> v;
        qr[i] = {u, v};
    }

    dij();

    for(int i = 1; i <= n; i ++) {
        st.push_back({ lim[i], i });
    }
    sort(all(st), greater<pii>());

    for(int i = 1; i <= Q; i ++) L[i] = 0, R[i] = n - 1;
    while(1) {
        int ok = 1;
        for(int i = 1; i <= Q; i ++) if(L[i] <= R[i]) {
            ok = 0;
            cur[(L[i] + R[i]) >> 1].push_back(i);
        }
        if(ok) break;

        for(int i = 1; i <= n; i ++) dd[i] = 0, root[i] = i, sz[i] = 1;
        for(int i = 0; i <= st.size() - 1; i ++) {
            int u = st[i].second, val = st[i].first;
            dd[u] = 1;
            for(pii x : o[u]) if(dd[x.first]) {
                uni(u, x.first);
            }

            while(cur[i].size()) { /// ans for query
                int id = cur[i].back();
                cur[i].pop_back();

                int u, v; tie(u, v) = qr[id];
                if(get(u) == get(v)) R[id] = i - 1;
                else L[id] = i + 1;
            }
        }
    }

    for(int i = 1; i <= Q; i ++) cout << st[ L[i] ].first << '\n';
}


int main()
{
    iof();

    int nTest = 1;
//    cin >> nTest;

    while(nTest --) {
        solve();
    }

    ctime();
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'void solve()':
plan.cpp:108:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for(int i = 0; i <= st.size() - 1; i ++) {
      |                        ~~^~~~~~~~~~~~~~~~
plan.cpp:109:35: warning: unused variable 'val' [-Wunused-variable]
  109 |             int u = st[i].second, val = st[i].first;
      |                                   ^~~
plan.cpp: In function 'void iof()':
plan.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen(Y8o".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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