Submission #565568

#	Time	Username	Problem	Language	Result	Execution time	Memory
565568		milisav	Evacuation plan (IZhO18_plan)	C++14	100 / 100	558 ms	75500 KiB

plan

#include<bits/stdc++.h>
#define maxn 600000
using namespace std;
vector<pair<int,int> > a[maxn];
int d[maxn];
priority_queue<pair<int,int> > pq;
bool vis[maxn];
int ans[maxn];
vector<pair<int,int> > queries[maxn];
int comp[maxn];
vector<int> incomp[maxn];
pair<int,int> dng[maxn];
void merge_components(int u,int v,int dg) {
    if(comp[u]==comp[v]) return;
    if(incomp[comp[u]].size()>incomp[comp[v]].size()) {
        swap(u,v);
    }
    for(auto x:incomp[comp[u]]) {
        for(auto q:queries[x]) {
            if(comp[q.first]==comp[v]) {
                ans[q.second]=dg;
            }
        }
    }
    int cc=comp[u];
    for(auto x:incomp[cc]) {
        comp[x]=comp[v];
        incomp[comp[v]].push_back(x);
    }

}
int main() {
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++) {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        a[u].push_back({v,w});
        a[v].push_back({u,w});
    }
    for(int i=1;i<=n;i++) {
        d[i]=1e9;
    }
    int k;
    scanf("%d",&k);
    for(int i=0;i<k;i++) {
        int g;
        scanf("%d",&g);
        d[g]=0;
        pq.push({-d[g],g});
    }
    while(!pq.empty()) {
        int u=pq.top().second;
        pq.pop();
        if(!vis[u]) {
            vis[u]=true;
            for(auto eg:a[u]) {
                int v=eg.first;
                int w=eg.second;
                if(d[v]>d[u]+w) {
                    d[v]=d[u]+w;
                    pq.push({-d[v],v});
                }
            }
        }
    }
    /*for(int i=1;i<=n;i++) {
        printf("d[%d]=%d\n",i,d[i]);
    }*/
    int q;
    scanf("%d",&q);
    for(int i=1;i<=q;i++) {
        int s,t;
        scanf("%d %d",&s,&t);
        queries[s].push_back({t,i});
        queries[t].push_back({s,i});
    }
    for(int i=1;i<=n;i++) {
        dng[i]={d[i],i};
        comp[i]=i;
        incomp[i].push_back(i);
        vis[i]=false;
    }
    sort(dng+1,dng+n+1);
    reverse(dng+1,dng+n+1);
    for(int i=1;i<=n;i++) {
        int u=dng[i].second;
        for(auto eg:a[u]) {
            int v=eg.first;
            if(vis[v]) {
                merge_components(u,v,dng[i].first);
            }
        }
        vis[u]=true;
    }

    for(int i=1;i<=q;i++) {
        printf("%d\n",ans[i]);
    }
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
plan.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d %d %d",&u,&v,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
plan.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d",&k);
      |     ~~~~~^~~~~~~~~
plan.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf("%d",&g);
      |         ~~~~~^~~~~~~~~
plan.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
plan.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         scanf("%d %d",&s,&t);
      |         ~~~~~^~~~~~~~~~~~~~~

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