Submission #544699

#	Time	Username	Problem	Language	Result	Execution time	Memory
544699		krit3379	Evacuation plan (IZhO18_plan)	C++17	100 / 100	643 ms	58868 KiB

plan

#include<bits/stdc++.h>
using namespace std;
#define N 100005

struct A{
    int a,w;
    bool operator<(const A& o)const{
        return w>o.w;
    }
};

struct B{
    int a,b,w;
    bool operator<(const B& o)const{
        return w>o.w;
    }
};

int dis[N],p[N],ans[N];
vector<A> g[N];
vector<B> edge;
set<int> s[N];
priority_queue<A> q;

int fp(int v){return (v==p[v])?v:p[v]=fp(p[v]);}

int main(){
    int n,m,qq,i,a,b,w;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)dis[i]=2e9,p[i]=i;
    for(i=1;i<=m;i++){
        scanf("%d %d %d",&a,&b,&w);
        g[a].push_back({b,w});
        g[b].push_back({a,w});
    }
    scanf("%d",&m);
    for(i=1;i<=m;i++){
        scanf("%d",&a);
        q.push({a,0});
        dis[a]=0;
    }
    scanf("%d",&qq);
    for(i=1;i<=qq;i++){
        scanf("%d %d",&a,&b);
        s[a].insert(i);
        s[b].insert(i);
    }
    while(!q.empty()){
        auto [a,w]=q.top();
        q.pop();
        if(w>dis[a])continue;
        for(auto x:g[a]){
            if(w+x.w<dis[x.a])q.push({x.a,w+x.w}),dis[x.a]=w+x.w;
        }
    }
    for(i=1;i<=n;i++){
        for(auto x:g[i])
            edge.push_back({i,x.a,min(dis[i],dis[x.a])});
    }
    sort(edge.begin(),edge.end());
    for(auto [a,b,w]:edge){
        a=fp(a),b=fp(b);
        if(a==b)continue;
        if(s[a].size()>s[b].size())swap(a,b);
        for(auto x:s[a]){
            if(s[b].count(x)){
                ans[x]=w;
                s[b].erase(x);
            }
            else s[b].insert(x);
        }
        p[a]=p[b];
    }
    for(i=1;i<=qq;i++)printf("%d\n",ans[i]);
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
plan.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%d %d %d",&a,&b,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
plan.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d",&m);
      |     ~~~~~^~~~~~~~~
plan.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         scanf("%d",&a);
      |         ~~~~~^~~~~~~~~
plan.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%d",&qq);
      |     ~~~~~^~~~~~~~~~
plan.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~

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