Submission #309301

#	Time	Username	Problem	Language	Result	Execution time	Memory
309301		amunduzbaev	악어의 지하 도시 (IOI11_crocodile)	C++14	100 / 100	1444 ms	94644 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;
#include "crocodile.h"
//#include "grader.cpp"

const int N1 = 2e5+5 ;
const int INF = 1e9+7 ;

vector<pair<int, int> > v[N1];
multiset<int> d[N1];
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){

    for(int i=0;i<m;i++){
        v[r[i][0]].push_back({r[i][1],l[i]});
        v[r[i][1]].push_back({r[i][0],l[i]});
    }
    set<pair<int,int>>q;
    for(int i=0;i<k;i++){
        d[p[i]].insert(0);
        d[p[i]].insert(0);
        q.insert({0,p[i]});
    }
    for(int i=0;i<n;i++){
        if(d[i].empty()) {
            d[i].insert(INF);
            d[i].insert(INF);
        }
    }

    while(!q.empty()){

        auto a=*q.begin();
        q.erase(q.begin());
        int dist=a.first;
        int ex=a.second;
        auto d1 = d[ex].begin();
        d1++;
        //cout<<dist<<" "<<ex<<" "<< *d1<<"\n";
        int D = *d1;
        if(D < dist) continue;

        for (auto x: v[ex]){
            int ver=x.first;
            int len=x.second;

            auto s=d[ver].begin();
            s++;
            if(D+len >= *s) continue;

            d[ver].insert(D+len);
            auto s1=d[ver].begin();
            s1++;
            if(*s1 < INF)
            q.insert({*s1,ver});

        }
    }
    auto ans=d[0].begin();
    ans++;
    int an=*ans;
    return an;
}


/*

5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1
3
14


*/

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11