Submission #335275

#	Time	Username	Problem	Language	Result	Execution time	Memory
335275		blue	Crocodile's Underground City (IOI11_crocodile)	C++11	100 / 100	1873 ms	66660 KiB

crocodile

#include "crocodile.h"
#include <iostream>
#include <vector>
#include <set>
using namespace std;

vector<int> min1(100001, 1e9), min2(100001, 1e9);

struct distcomp
{
    int i;
};

bool operator < (distcomp A, distcomp B)
{
    if(max(min1[A.i], min2[A.i]) == max(min1[B.i], min2[B.i])) return A.i < B.i;
    return max(min1[A.i], min2[A.i]) < max(min1[B.i], min2[B.i]);
}

int travel_plan(int N,      //number of chambers
                int M,      //number of corridors
                int R[][2], //endpoints of corridor i
                int L[],    //corridor lengths
                int K,      //number of exits
                int P[])    //list of exits
{
    vector<int> blocked(N, 0);
    vector<int> visit(N, 0);

    vector<int> edge[N], len[N];
    for(int i = 0; i < M; i++)
    {
        edge[R[i][0]].push_back(R[i][1]);
        len[R[i][0]].push_back(L[i]);

        edge[R[i][1]].push_back(R[i][0]);
        len[R[i][1]].push_back(L[i]);
    }

    vector<int> E(N);
    for(int i = 0; i < N; i++) E[i] = edge[i].size();

    for(int i = 0; i < N; i++)
    {
        if(E[i] == 2)
        {
            if(E[edge[i][0]] == 2) blocked[i] = blocked[edge[i][0]] = 1;
            if(E[edge[i][1]] == 2) blocked[i] = blocked[edge[i][1]] = 1;
        }
    }

    for(int i = 0; i < N; i++) for(int j: edge[i]) if(blocked[j]) E[i]--;

    set<distcomp> tbv;
    for(int p = 0; p < K; p++) min1[P[p]] = min2[P[p]] = 0;
    for(int i = 0; i < N; i++) tbv.insert(distcomp{i});

    while(!tbv.empty())
    {
        int u = tbv.begin()->i;
        tbv.erase(tbv.begin());
        visit[u] = 1;
        int temp = max(min1[u], min2[u]);
        if(u == 0) return temp;
        for(int i = 0; i < edge[u].size(); i++)
        {
            int v = edge[u][i];
            int l = len[u][i];

            if(visit[v]) continue;
            if(blocked[v]) continue;

            tbv.erase(tbv.find(distcomp{v}));
            if(temp + l <= min1[v])
            {
                min2[v] = min1[v];
                min1[v] = temp + l;
            }
            else if(temp + l < min2[v]) min2[v] = temp + l;
            tbv.insert(distcomp{v});
        }
    }
    return max(min1[0], min2[0]);
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:65:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int i = 0; i < edge[u].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~

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