Submission #492353

#	Time	Username	Problem	Language	Result	Execution time	Memory
492353		phamhoanghiep	Evacuation plan (IZhO18_plan)	C++14	100 / 100	958 ms	28604 KiB

plan

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
const int maxn=1e5+5;
const int inf=1e9+7;
int n,m,q,k;
int dist[maxn];
vector<int> qry[maxn*2];
ii qr[maxn];
int ans[maxn];
int l[maxn];
int r[maxn];
vector<ii> AdjList[maxn];
priority_queue<ii,vector<ii>,greater<ii>> pq;
void dijkstra() {
    while(!pq.empty()) {
        ii tmp=pq.top();
        pq.pop();
        int d=tmp.first;
        int u=tmp.second;
        if(d>dist[u]) continue;
        for(ii x: AdjList[u]) {
            int v=x.first;
            int w=x.second;
            if(dist[v]>d+w) {
                dist[v]=d+w;
                pq.push(ii(dist[v],v));
            }
        }
    }
}
// dsu
int pset[maxn];
int sz[maxn];
vector<iii> edges;
void init() {
    for(int i=1 ; i<=n ; i++) {
        pset[i]=i;
        sz[i]=1;
    }
}
int find_set(int s) {
    if(s==pset[s]) return s;
    else return pset[s]=find_set(pset[s]);
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i=1 ; i<=m ; i++) {
        int u,v,w;
        cin>>u>>v>>w;
        AdjList[u].push_back(ii(v,w));
        AdjList[v].push_back(ii(u,w));
    }
    for(int i=1 ; i<=n ; i++) dist[i]=inf;
    cin>>k;
    for(int i=1 ; i<=k ; i++) {
        int u;
        cin>>u;
        dist[u]=0;
        pq.push(ii(0,u));
    }
    dijkstra();
    cin>>q;
    for(int i=1 ; i<=q ; i++) {
        cin>>qr[i].first>>qr[i].second;
        l[i]=0;
        r[i]=inf;
    }
    vector<ii> vertex;
    for(int i=1 ; i<=n ; i++) {
        vertex.push_back(ii(dist[i],i));
    }
    sort(vertex.rbegin(),vertex.rend());
    for(int step=0 ; step<30 ; step++) {
        vector<ii> queries;
        init();
        for(int i=1 ; i<=q ; i++) {
            int mid=(l[i]+r[i]+1)/2;
            queries.push_back(ii(mid,i));
        }
        sort(queries.rbegin(),queries.rend());
        int id=0;
        for(ii x: queries) {
            while(id<n&&vertex[id].first>=x.first) {
                for(ii tmp: AdjList[vertex[id].second]) {
                    if(dist[tmp.first]<dist[vertex[id].second]) continue;
                    int u=find_set(tmp.first);
                    int v=find_set(vertex[id].second);
                    if(u!=v) {
                        if(sz[u]>sz[v]) swap(u,v);
                        sz[v]+=sz[u];
                        pset[u]=v;
                    }
                }
                id++;
            }
            if(find_set(qr[x.second].first)==find_set(qr[x.second].second)) {
                l[x.second]=x.first;
            }
            else r[x.second]=x.first-1;
        }
    }
    for(int i=1 ; i<=q ; i++) {
        cout<<l[i]<<'\n';
    }
}

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