Submission #685158

#	Time	Username	Problem	Language	Result	Execution time	Memory
685158		speedyArda	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1014 ms	54348 KiB

plan

#include "bits/stdc++.h"

using namespace std;
const int MAXN = 1e5+5;
int par[MAXN], dist[MAXN];
vector < vector < pair<int, int> > > adj(MAXN);
vector < set<int> > elems(MAXN);
vector<int> ans(MAXN);
vector < set< pair< int, pair<int, int> > > > queries(MAXN);
vector< pair<int, int > > sorted;
int findset(int v)
{
    if(par[v] == v)
        return v;
    return par[v] = findset(par[v]);
}

void mergeset(int a, int b, int val)
{
    a = findset(a), b = findset(b);
    if(a == b)
        return;
    if(elems[a].size() < elems[b].size())
        swap(a, b);
    par[b] = a;
    for(int e : elems[b])
    {
        //elems[a].insert(e);
        int other = e;
        
        vector<pair<int, pair<int, int> > > toclear;
        for(pair<int, pair<int, int> > query : queries[e])
        {
            if(query.second.first != e)
                other = query.second.first;
            else
                other = query.second.second;
            //cout << e << " " << query.second.first << " " << query.second.second << "\n";
            if(elems[a].find(other) != elems[a].end())
            {
                ans[query.first] = val;
                toclear.push_back(query);
            }
        }
        //elems[a].insert(e);
        for(pair<int, pair<int, int> > l : toclear)
            queries[e].erase(l);
    }
    for(int e : elems[b])
        elems[a].insert(e);
    elems[b].clear();
}

int main() 
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        dist[i] = 1e9;
        par[i] = i;
        elems[i].insert(i);
    }
    for(int i = 1; i <= m; i++)
    {
        int f, s, w;
        cin >> f >> s >> w;
        adj[f].push_back({w, s});
        adj[s].push_back({w, f});
    }

    set< pair<int, int > > curr;
    int k;
    cin >> k;
    for(int i = 1; i <= k; i++)
    {
        int f;
        cin >> f;
        dist[f] = 0;
        curr.insert({0, f}); 
    }

    while(!curr.empty())
    {
        pair<int, int> v = *(curr.begin());
        curr.erase(curr.begin());
        sorted.push_back(v);
        for(pair<int, int> neigh : adj[v.second])
        {
            if(neigh.first + dist[v.second] < dist[neigh.second])
            {
                curr.erase({dist[neigh.second], neigh.second});
                dist[neigh.second] = neigh.first + dist[v.second];
                curr.insert({dist[neigh.second], neigh.second});
            }
        }
    }
    //cout << dist[6] << "\n";
    int q;
    cin >> q;
    for(int i = 1; i <= q; i++)
    {
        int s, t;
        cin >> s >> t;
        queries[s].insert({i, {s, t}});
        queries[t].insert({i, {s, t}});
    }

    sort(sorted.begin(), sorted.end());
    reverse(sorted.begin(), sorted.end());
    for(int i = 0; i < n; i++)
    {
        //cout << sorted[i].first << " " << sorted[i].second << "\n";
        for(pair<int, int> e : adj[sorted[i].second])
        {
            if(dist[e.second] < dist[sorted[i].second])
                continue;
            mergeset(e.second, sorted[i].second, sorted[i].first);
        }
    }

    for(int i = 1; i <= q; i++)
        cout << ans[i] << "\n";
}

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