Submission #85337

#	Time	Username	Problem	Language	Result	Execution time	Memory
85337		mra2322001	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1902 ms	49020 KiB

plan

#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)

using namespace std;
typedef long long ll;
const int N = 100002;

int n, m, dist[N], parent[N];
pair <int, pair <int, int> > ed[N*5];
vector <vector <int> > v;
vector <vector <pair <int, int> > > a;

struct data{
    int u, v, l, r, ans;
} Q[N];

void dijkstra(){
    priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > q;
    f1(i, n) if(dist[i]==0) q.push({0, i});
    while(q.size()){
        int u = q.top().second, du = q.top().first;
        q.pop();
        if(du != dist[u]) continue;
        for(auto x:a[u]){
            if(dist[x.first] > du + x.second){
                dist[x.first] = du + x.second;
                q.push({dist[x.first], x.first});
            }
        }
    }
}

bool cmp(pair <int, pair <int, int> > a1, pair <int, pair <int, int> > a2){
    int x1 = min(dist[a1.second.first], dist[a1.second.second]);
    int x2 = min(dist[a2.second.first], dist[a2.second.second]);
    return x1 > x2;
}

int getroot(int u){
    if(parent[u]==u) return u;
    if(parent[u]==0) return u;
    parent[u] = getroot(parent[u]);
    return parent[u];
}

int Merge(int u, int v){
    parent[getroot(v)] = getroot(u);
}

int main(){
    ios_base::sync_with_stdio(0);

    cin >> n >> m;
    a.resize(n + 1);
    f1(i, m){
        int u, v, w; cin >> u >> v >> w;
        a[u].emplace_back(v, w);
        a[v].emplace_back(u, w);
        ed[i] = {w, {u, v}};
    }
    int len; cin >> len;
    memset(dist, 0x3f3f3f, sizeof(dist));
    while(len--){
        int x; cin >> x;
        dist[x] = 0;
    }
    dijkstra();
    sort(ed + 1, ed + m + 1, cmp);
    int q; cin >> q;
    f1(i, q){
        int u, v; cin >> u >> v;
        Q[i] = {u, v, 1, m, 0};
    }
    bool ok = 1;
    int g = 20;
    v.resize(m + 1);
    while(g--){
        f1(i, m) v[i].clear();
        ok = 0;
        f1(i, q){
            if(Q[i].l <= Q[i].r){
                int mid = (Q[i].l + Q[i].r)/2;
                v[mid].emplace_back(i);
                ok = 1;
            }
        }
        f1(i, n) parent[i] = 0;
        f1(i, m){
            Merge(ed[i].second.first, ed[i].second.second);
            for(auto x:v[i]){
                if(getroot(Q[x].u)==getroot(Q[x].v)){
                    Q[x].ans = i;
                    Q[x].r = i - 1;
                }
                else{
                    Q[x].l = i + 1;
                }
            }
        }
    }
    f1(i, q) cout << min(dist[ed[Q[i].ans].second.first], dist[ed[Q[i].ans].second.second]) << endl;
}

Compilation message (stderr)

plan.cpp: In function 'int Merge(int, int)':
plan.cpp:49:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
plan.cpp: In function 'int main()':
plan.cpp:75:10: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
     bool ok = 1;
          ^~

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