Submission #62165

#	Time	Username	Problem	Language	Result	Execution time	Memory
62165		reality	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	1303 ms	69352 KiB

crocodile

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()

#include "crocodile.h"

const int Nmax = (int)(1e6) + 5;

int D[Nmax];
int was[Nmax];

vector < pii > g[Nmax];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    int n = N;
    int m = M;
    for (int i = 0;i < m;++i)
        g[R[i][0]].pb(mp(R[i][1],L[i])),g[R[i][1]].pb(mp(R[i][0],L[i]));
    priority_queue < pii , vector < pii > , greater < pii > > Q;
    for (int i = 0;i < n + n;++i)
        D[i] = 1e9 + 55;
    for (int i = 0;i < K;++i)
    {
        D[P[i] * 2] = D[P[i] * 2 + 1] = 0;
        Q.push(mp(0,P[i] * 2));
        Q.push(mp(0,P[i] * 2 + 1));
    }
    while (!Q.empty())
    {
        int node = Q.top().se;
        Q.pop();
        ++was[node];
        if (was[node] > 1) continue;
        if ((node & 1) && was[node ^ 1])
        {
            for (auto it : g[node / 2])
            {
                int v = it.fi;
                if (D[v * 2] >= D[node] + it.se)
                    D[v * 2 + 1] = D[v * 2],D[v * 2] = D[node] + it.se,Q.push(mp(D[v * 2],v * 2)),Q.push(mp(D[v * 2 + 1],v * 2 + 1));
                else
                if (D[v * 2 + 1] > D[node] + it.se)
                    D[v * 2 + 1] = D[node] + it.se,Q.push(mp(D[v * 2 + 1],v * 2 + 1));
            }
        }
    }
    return D[1];
}

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