oj.uz

Submission #335275

# Submission time Handle Problem Language Result Execution time Memory
335275 2020-12-11T19:20:30 Z blue Crocodile's Underground City (IOI11_crocodile) C++11
100 / 100
 1873 ms 66660 KB 
#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

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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 1 ms 1132 KB Output is correct
3 Correct 1 ms 1132 KB Output is correct
4 Correct 2 ms 1260 KB Output is correct
5 Correct 2 ms 1260 KB Output is correct
6 Correct 0 ms 1260 KB Output is correct
7 Correct 2 ms 1260 KB Output is correct
8 Correct 2 ms 1260 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 1 ms 1132 KB Output is correct
3 Correct 1 ms 1132 KB Output is correct
4 Correct 2 ms 1260 KB Output is correct
5 Correct 2 ms 1260 KB Output is correct
6 Correct 0 ms 1260 KB Output is correct
7 Correct 2 ms 1260 KB Output is correct
8 Correct 2 ms 1260 KB Output is correct
9 Correct 4 ms 1260 KB Output is correct
10 Correct 1 ms 1156 KB Output is correct
11 Correct 3 ms 1260 KB Output is correct
12 Correct 7 ms 1644 KB Output is correct
13 Correct 4 ms 1644 KB Output is correct
14 Correct 2 ms 1132 KB Output is correct
15 Correct 3 ms 1260 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 1 ms 1132 KB Output is correct
3 Correct 1 ms 1132 KB Output is correct
4 Correct 2 ms 1260 KB Output is correct
5 Correct 2 ms 1260 KB Output is correct
6 Correct 0 ms 1260 KB Output is correct
7 Correct 2 ms 1260 KB Output is correct
8 Correct 2 ms 1260 KB Output is correct
9 Correct 4 ms 1260 KB Output is correct
10 Correct 1 ms 1156 KB Output is correct
11 Correct 3 ms 1260 KB Output is correct
12 Correct 7 ms 1644 KB Output is correct
13 Correct 4 ms 1644 KB Output is correct
14 Correct 2 ms 1132 KB Output is correct
15 Correct 3 ms 1260 KB Output is correct
16 Correct 1561 ms 56540 KB Output is correct
17 Correct 183 ms 23532 KB Output is correct
18 Correct 211 ms 25196 KB Output is correct
19 Correct 1873 ms 66660 KB Output is correct
20 Correct 329 ms 48876 KB Output is correct
21 Correct 82 ms 9580 KB Output is correct
22 Correct 630 ms 48004 KB Output is correct