Submission #543200

#	Time	Username	Problem	Language	Result	Execution time	Memory
543200		ogibogi2004	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	510 ms	87892 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=1e5+6;
const int INF=2e9;
vector<pair<int,ll> >g[MAXN];
bool winning[MAXN];
int wn_cnt[MAXN];
ll smol1[MAXN],smol2[MAXN];
bool used[MAXN];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{

    for(int i=1;i<=N;i++)
    {
        winning[i]=0;
        wn_cnt[i]=0;
        smol1[i]=INF;
        smol2[i]=INF;
        used[i]=0;
    }
    for(int i=0;i<K;i++)
    {
        winning[P[i]+1]=1;
        smol1[P[i]+1]=0;
        smol2[P[i]+1]=0;
    }
    for(int i=0;i<M;i++)
    {
        g[R[i][0]+1].push_back({R[i][1]+1,L[i]});
        g[R[i][1]+1].push_back({R[i][0]+1,L[i]});
    }
    priority_queue<pair<int,int> >pq;
    for(int i=0;i<K;i++)
    {
        pq.push({-smol2[P[i]+1],P[i]+1});
    }
    while(!pq.empty())
    {
        int u=pq.top().second;
        pq.pop();
        if(used[u])continue;
        used[u]=1;
        if(u==0)break;
        for(auto xd:g[u])
        {
            wn_cnt[xd.first]++;
            if(smol2[u]+xd.second<=smol1[xd.first])
            {
                smol2[xd.first]=smol1[xd.first];
                smol1[xd.first]=smol2[u]+xd.second;
                if(smol2[xd.first]!=INF)pq.push({-smol2[xd.first],xd.first});
            }
            else if(smol2[u]+xd.second<smol2[xd.first])
            {
                smol2[xd.first]=smol2[u]+xd.second;
                pq.push({-smol2[xd.first],xd.first});
            }
        }
    }
    return smol2[1];
}

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