oj.uz

Submission #335269

# Submission time Handle Problem Language Result Execution time Memory
335269 2020-12-11T19:04:45 Z blue Crocodile's Underground City (IOI11_crocodile) C++11
46 / 100
 14 ms 2540 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;
        tbv.insert(distcomp{P[p]});
    }

    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;

            if(temp + l <= min1[v])
            {
                min2[v] = min1[v];
                min1[v] = temp + l;
            }
            else if(temp + l < min2[v]) min2[v] = temp + l;
            E[v]--;
            if(E[v] == 1) tbv.insert(distcomp{v});
        }
    }
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:68:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for(int i = 0; i < edge[u].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~
crocodile.cpp:27:29: warning: control reaches end of non-void function [-Wreturn-type]
   27 |     vector<int> blocked(N, 0);
      |                             ^

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 2 ms 1132 KB Output is correct
4 Correct 2 ms 1260 KB Output is correct
5 Correct 3 ms 1260 KB Output is correct
6 Correct 2 ms 1280 KB Output is correct
7 Correct 2 ms 1260 KB Output is correct
8 Correct 2 ms 1260 KB Output is correct

Subtask #2
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 2 ms 1132 KB Output is correct
4 Correct 2 ms 1260 KB Output is correct
5 Correct 3 ms 1260 KB Output is correct
6 Correct 2 ms 1280 KB Output is correct
7 Correct 2 ms 1260 KB Output is correct
8 Correct 2 ms 1260 KB Output is correct
9 Runtime error 14 ms 2540 KB Execution killed with signal 6 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #3
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 2 ms 1132 KB Output is correct
4 Correct 2 ms 1260 KB Output is correct
5 Correct 3 ms 1260 KB Output is correct
6 Correct 2 ms 1280 KB Output is correct
7 Correct 2 ms 1260 KB Output is correct
8 Correct 2 ms 1260 KB Output is correct
9 Runtime error 14 ms 2540 KB Execution killed with signal 6 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -