답안 #335268

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
335268	2020-12-11T19:03:41 Z	blue	악어의 지하 도시 (IOI11_crocodile)	C++11	컴파일 오류	0 ms	0 KB

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;
        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;
        q(111*u);
        for(int i = 0; i < edge[u].size(); i++)
        {
            int v = edge[u][i];
            int l = len[u][i];
            q(v);

            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:9: error: 'q' was not declared in this scope
   68 |         q(111*u);
      |         ^
crocodile.cpp:69:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         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);
      |                             ^