Submission #544323

#	Time	Username	Problem	Language	Result	Execution time	Memory
544323		somo	Evacuation plan (IZhO18_plan)	C++14	100 / 100	570 ms	101684 KiB

plan

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define endl '\n'
#define pii pair<ll,ll>
#define F first
#define S second
#define double long double
#define all(x) (x).begin(),(x).end()

using namespace std;
using namespace __gnu_pbds;

typedef tree<ll , null_type , less_equal<ll> ,rb_tree_tag ,tree_order_statistics_node_update >ordered_set;

const int MOD = 1e9 + 7;
const int  N=5e5 + 7 ;
const ll INF= 1e18+10;

struct trp{ll F,S,T;};

ll po(ll x,ll y)
{
    ll ans = 1;
    while(y){
        if( y & 1 ) ans *=x;
        y /= 2;
        x *=x;
        x %= MOD;
        ans %= MOD;
    }
    return ans;
}

ll p[N];
ll vis[N];
ll ans[N];
bool is[N];
ll n , m , qu;
set<ll> dsu[N];
vector<pii>v[N];
vector<pii> que[N];

ll root(ll x)
{
    return p[x] == x ? x : p[x] = root(p[x]);
}

void mer(ll x,ll y,ll hehe)
{
    x = root(x);
    y = root(y);
    if(x == y) return;
    if(dsu[x].size() > dsu[y].size()) swap(x,y);
    for(auto i : dsu[x]){
        for(auto j : que[i]){
            if(dsu[y].find(j.F) != dsu[y].end()) ans[j.S] = hehe;
        }
    }
    for(auto i : dsu[x]) dsu[y].insert(i);
    p[x] = y;
}

bool cmp(pii a,pii b)
{
    return a.F < b.F;
}

void solve()
{
    cin >> n >> m ;
    for(ll i= 1; i <= m ; i ++){
        ll x,y,z;
        cin >> x >> y >> z;
        v[x].pb({y,z});
        v[y].pb({x,z});
    }
    for(ll i= 1; i <= n ; i ++){
        vis[i] = 1e17;
        p[i] = i;
        dsu[i].insert(i);
    }
    priority_queue<pii,vector<pii>,greater<pii>>q;
    ll k;
    cin >> k;
    while(k -- ){
        ll x;
        cin >> x;
        vis[x] = 0;
        q.push({0,x});
    }
    while(q.size()){
        pii x = q.top();
        q.pop();
        if(x.F != vis[x.S]) continue;
        for(auto i : v[x.S]){
            if(vis[i.F] > x.F + i.S){
                vis[i.F] = x.F + i.S;
                q.push({vis[i.F] , i.F});
            }
        }
    }
    vector<pii>vec;
    for(ll i= 1; i <= n ; i ++){
        vec.pb({vis[i] , i});
    }
    sort(all(vec) , cmp);
    cin >> qu;
    for(ll i= 1; i <= qu ; i ++){
        ll x,y;
        cin >> x >> y;
        que[x].pb({y,i});
        que[y].pb({x,i});
    }
    while(vec.size()){
        ll node = vec.back().S , hehe = vec.back().F;
        is[node] = 1;
        vec.pop_back();
        for(auto i : v[node]){
            if(!is[i.F]) continue;
            mer(node , i.F , hehe);
        }
    }
    for(ll i= 1; i <= qu ; i ++) cout << ans[i] << endl;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//freopen(".in" , "r" , stdin);freopen(".out" , "w" , stdout);
	int t = 1;
    //cin >> t;
	while(t--) {solve() ; }
}

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