Submission #316788

#	Time	Username	Problem	Language	Result	Execution time	Memory
316788		ajpiano	Evacuation plan (IZhO18_plan)	C++17	100 / 100	589 ms	43464 KiB

plan

#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

#define FOR(a,b) for(int a=0;a<b;a++)
#define F0R(a,b,c) for(int a = b; a<=c; a++)
#define f first
#define s second
#define m0(x) memset(x,0,sizeof(x))
#define all(x) x.begin(), x.end()

typedef pair<int,int> pi;
typedef long long ll;
typedef vector<int> vi;
typedef vector<pi> vpi;

const int large = 1e5;

struct path{
    int start, finish, val, cost;
    path(int s, int f, int c){
        start = s; finish = f; cost = c;
    }
    bool operator > (const path &b) const{
        return (val > b.val);
    }
    int other(int x){
        if(x == start) return finish;
        else return start;
    }
};

int n,m;
int cur;
vi edges[large+1];
vector<path> roads;
vi parents;
vi dist;
vi members[large+1];
vpi transfers[large+1];

int bpath(int a, int b){
    int asz = transfers[a].size();
    int bsz = transfers[b].size();
    if(asz > bsz){
        swap(a,b);
        swap(asz,bsz);
    }
    int ans = 0;
    F0R(i,1,asz){
        pi aval = transfers[a][asz-i];
        pi bval = transfers[b][bsz-i];
        if(aval.f != bval.f) break;
        ans = min(aval.s, bval.s);
//        cerr << "Group: " << aval.f << ", Meeting: " << aval.s << " " << bval.s << " - " << ans << "\n";
    }
    return ans;
}

void mergeNode(int a, int b){
    a = parents[a];
    b = parents[b];
    if(a == b) return;
    if(members[a].size() < members[b].size()) swap(a,b);
//    cerr << "Merge: " << b << " -> " << a << " : " << cur << "\n";
    while(!members[b].empty()){
        int node = members[b].back(); members[b].pop_back();
        members[a].push_back(node);
        parents[node] = a;
        transfers[node].push_back({a,cur});
    }
}

const int inf = 1e9;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    parents.resize(n+1); iota(all(parents),0);
    dist.resize(n+1,inf);
    F0R(i,1,n) members[i].push_back(i);
    F0R(i,1,n) transfers[i].push_back({i,inf});
    FOR(i,m){
        int a, b, w; cin >> a >> b >> w;
        roads.emplace_back(a,b,w);
        edges[a].push_back(i);
        edges[b].push_back(i);
    }
    //run dijkstra
    priority_queue<pi, vpi, greater<pi>> pq;
    int k; cin >> k;
    FOR(i,k){
        int a; cin >> a;
        dist[a] = 0;
        pq.push({0,a});
    }
    while(!pq.empty()){
        pi a = pq.top(); pq.pop();
        if(dist[a.s] < a.f) continue;
        for(int e: edges[a.s]){
            path &p = roads[e];
            int b = p.other(a.s);
            if(a.f+p.cost >= dist[b]) continue;
            dist[b] = a.f+p.cost;
            pq.push({dist[b], b});
        }
    }
    //assign values to paths
    FOR(i,m){
        path &a = roads[i];
        a.val = min(dist[a.start], dist[a.finish]);
    }
//    cerr << "Distances:\n";
//    F0R(i,1,n){
//        cerr << "Node: " << i << " : " << dist[i] << "\n";
//    }
//    cerr << "END Distances\n";
//    cerr << "Distances:\n";
//    FOR(i,m){
//        cerr << roads[i].start << " <--> " << roads[i].finish << " : " << roads[i].val << "\n";
//    }
//    cerr << "END Distances\n";
    //sort roads
    sort(all(roads), greater<path>());
    //go through roads and do dsu
    for(path &p : roads){
        cur = p.val;
        mergeNode(p.start, p.finish);
    }
    //answer queries
    int q; cin >> q;
    FOR(i,q){
        int a, b; cin >> a >> b;
//        cout << "Answer " << i << ": " << bpath(a,b) << "\n";
        cout << bpath(a,b) << "\n";
    }
    return 0;
}

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