Submission #400626

#	Time	Username	Problem	Language	Result	Execution time	Memory
400626		MOUF_MAHMALAT	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	886 ms	60132 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef int ll;
//ll N1,M1,K1,R1[1000000][2],L1[1000000],P1[100000],solution;
ll x,y,id;
set<pair<ll,ll> >s;
pair<ll,ll>d[100000],p;
bool b[1000000];
vector<vector<pair<ll,ll> > >v;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    v.resize(N);
    for(ll i=0; i<M; i++)
    {
        x=R[i][0],y=R[i][1];
        v[x].push_back({y,L[i]});
        v[y].push_back({x,L[i]});
    }
    for(ll i=0; i<N; i++)
        d[i]= {2e9,2e9};
    for(ll i=0; i<K; i++)
    {
        d[P[i]]= {0,0};
        s.insert({0,P[i]});
    }
    while(s.size())
    {
        p=*s.begin();
        s.erase(s.begin());
        x=p.second,y=p.first;
        for(auto z:v[x])
        {
            id=z.F;
            if(d[id].F > y + z.S)
            {
                s.erase({d[id].S,id});
                d[id].S = d[id].F;
                d[id].F = y + z.S;
                s.insert({d[id].S,id});
            }
            else if(d[id].S > y+z.S)
            {
                s.erase({d[id].S,id});
                d[id].S = y + z.S;
                s.insert({d[id].S,id});
            }
        }
    }
    return d[0].S;
}
/*int main()
{
    cin>>N1>>M1>>K1;
    for(ll i=0; i<M1; i++)
        cin>>R1[i][0]>>R1[i][1]>>L1[i];
    for(ll i=0; i<K1; i++)
        cin>>P1[i];
    cin>>solution;
    cout<<travel_plan(N1,M1,R1,L1,K1,P1);
}*/

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