Submission #118465

#	Time	Username	Problem	Language	Result	Execution time	Memory
118465		DystoriaX	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1446 ms	28588 KiB

plan

#include <bits/stdc++.h>
 
using namespace std;
 
int n, m, q, k;
int par[100010];
int dist[100010];
vector<pair<int, int> > adj[100010];
vector<tuple<int, int, int> > edges;
bitset<100010> vis;
priority_queue<pair<int, int> > pq;
int to[100010], lo[100010], hi[100010];
map<int, int> comp;
pair<int, int> queries[100010];
vector<int> mids[100010];
 
void init(){
    for(int i = 1; i <= n; i++) par[i] = i;
}
 
int findR(int x){
    return par[x] == x ? x : par[x] = findR(par[x]);
}
 
void join(int a, int b){
    par[findR(a)] = findR(b);
}

bool cmp(int a, int b){
    return dist[a] > dist[b];
}
 
int main(){
    scanf("%d%d", &n, &m);
 
    while(m--){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
 
    for(int i = 1; i <= n; i++) dist[i] = 1e9;
 
    scanf("%d", &k);
    while(k--){
        int x; scanf("%d", &x);
        pq.push({0, x});
        dist[x] = 0;
    }
 
    //Dijkstra
    while(!pq.empty()){
        int u, w;
        tie(w, u) = pq.top(); pq.pop(); w = -w;
 
        if(vis[u]) continue;
        vis[u] = 1;
 
        for(auto k : adj[u]){
            int v, w; tie(v, w) = k;
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                pq.push({-dist[v], v});
            }
        }
    }

    vector<int> v;
    for(int i = 1; i <= n; i++) v.emplace_back(dist[i]);

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int i = 0; i < (int) v.size(); i++){
        to[i] = v[i];
        comp[v[i]] = i;
    }
    const int mx = v.size() - 1;

    for(int i = 1; i <= n; i++) dist[i] = comp[dist[i]];
 
    scanf("%d", &q);
 
    for(int i = 0; i < q; i++){
        int u, v;
        scanf("%d%d", &u, &v);
        queries[i] = {u, v};
        mids[mx >> 1].emplace_back(i);
        lo[i] = 0, hi[i] = mx;
    }

    v.clear();
    v.resize(n);
    iota(v.begin(), v.end(), 1);
    sort(v.begin(), v.end(), cmp);

    int id = 0;
    while(true){
        init();
        bool diff = false;
        id = 0;

        for(int i = mx; i >= 0; i--){
            while(id < n && dist[v[id]] == i){
                for(auto x : adj[v[id]]) if(dist[x.first] >= i) join(x.first, v[id]);
                ++id;
            }

            while(!mids[i].empty()){
                diff = true;
                int u, v;
                int idx = mids[i].back();
                tie(u, v) = queries[idx];

                mids[i].pop_back();

                if(findR(u) == findR(v)){
                    lo[idx] = i + 1;
                } else {
                    hi[idx] = i - 1;
                }

                int m = (lo[idx] + hi[idx]) >> 1;

                if(lo[idx] <= hi[idx]) mids[m].emplace_back(idx);
            }
        }

        if(!diff) break;
    }

    for(int i = 0; i < q; i++) printf("%d\n", to[hi[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", &u, &v, &w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
plan.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
plan.cpp:47:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x; scanf("%d", &x);
                ~~~~~^~~~~~~~~~
plan.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
plan.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~

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