Submission #140730

#	Time	Username	Problem	Language	Result	Execution time	Memory
140730		rzbt	Evacuation plan (IZhO18_plan)	C++14	0 / 100	1215 ms	54988 KiB

plan

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 100005
typedef long long ll;

using namespace std;

int n,m,k;

vector<pair<int,int> > niz[MAXN];
vector<pair<int,pair<int,int> > >grane;
set<pair<int,int> > s;
int udaljenost[MAXN];
bool obidjen[MAXN];

void dijkstra(){
    while(!s.empty()){
        auto t=*(s.begin());
        s.erase(s.begin());
        if(obidjen[t.S])continue;
        obidjen[t.S]=true;
        udaljenost[t.S]=t.F;
        for(auto x:niz[t.S]){
            if(obidjen[x.first])continue;
            s.insert(mp(x.S+t.F,x.F));
        }
    }
}

bool aktivan[MAXN];
vector<pair<int,int> > istorija[MAXN];
vector<int> dsu[MAXN];
int trenutni[MAXN];

void spoji(int a,int b,int tezina){
    if(trenutni[a]==trenutni[b])return;
    a=trenutni[a];
    b=trenutni[b];
    if(dsu[b].size()>dsu[a].size())swap(a,b);

    for(auto x:dsu[b]){
        istorija[x].pb(mp(a,tezina));
        dsu[a].pb(x);
        trenutni[x]=a;
    }


}

bool comp(int a,int b){
    return udaljenost[a] > udaljenost[b];
}
vector<int> lol;


int main()
{
    scanf("%d %d", &n, &m);
    for(int i=1;i<=m;i++){
        int t1,t2,t3;
        scanf("%d %d %d", &t1, &t2, &t3);
        niz[t1].pb(mp(t2,t3));
        niz[t2].pb(mp(t1,t3));
        grane.pb(mp(t3,mp(t1,t2)));
    }
    scanf("%d", &k);
    for(int i=1;i<=k;i++){
        int t;
        scanf("%d", &t);
        s.insert(mp(0,t));

    }
    dijkstra();
    for(int i=1;i<=n;i++)lol.pb(i);
    sort(all(lol),comp);
    for(auto t:lol){
        //printf("   %d %d\n",t,udaljenost[t]);
        aktivan[t]=true;
        dsu[t].pb(t);
        istorija[t].pb(mp(t,1e9+8));
        trenutni[t]=t;
        for(auto x:niz[t]){

            if(!aktivan[x.F])continue;
            //printf("           %d %d\n",t,x.F);
            spoji(t,x.F,udaljenost[t]);
        }
    }
    int qq;
    scanf("%d", &qq);
    for(int qqq=0;qqq<qq;qqq++){
        int a,b;
        scanf("%d %d", &a, &b);
        int i=1;
        while(istorija[a][istorija[a].size()-i]==istorija[b][istorija[b].size()-i])i++;
        printf("%d\n",min(istorija[a][istorija[a].size()-i].S,istorija[b][istorija[b].size()-i].S));


    }


    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
plan.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &t1, &t2, &t3);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &k);
     ~~~~~^~~~~~~~~~
plan.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &t);
         ~~~~~^~~~~~~~~~
plan.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &qq);
     ~~~~~^~~~~~~~~~~
plan.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~

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