Submission #915337

#	Time	Username	Problem	Language	Result	Execution time	Memory
915337		StefanL2005	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	840 ms	92528 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;
#define inf 1000*1000*1000 + 6

struct nod{
    int nr;
    vector<nod*> Ch;
    vector<int> Cost;
};

struct muchie{
    int start, end, cost;
};

bool rule (muchie A, muchie B)
{
    if (A.cost == B.cost)
    {
        if (A.start == B.start)
            return A.end > B.end;
        return A.start > B.start;
    }
    return A.cost > B.cost;
}

void bloom (nod *node, vector<pair<int,int>> &Choice, vector<int> &Check, priority_queue<muchie, vector<muchie>, decltype(&rule)> &Q)
{
    for (int i = 0; i < node->Ch.size(); i++)
    {
        auto vecin = node->Ch[i];

        if (Check[vecin->nr] >= 2)
            continue;

        muchie A; A.start = node->nr; A.end = vecin->nr; A.cost = node->Cost[i] + Choice[node->nr].second;
        Q.push(A);
    }
}

int travel_plan(int n, int m, int R[][2], int L[], int k, int exit[])
{
    vector<int> Check(n, 0);
    vector<nod*> Tree(n);
    vector<pair<int,int>> Choice(n);
    priority_queue<muchie, vector<muchie>, decltype(&rule)> Q(rule);
    
    for (int i = 0; i < n; i++)
    { Tree[i] = new nod; Tree[i]->nr = i; }

    for (int i = 0; i < m; i++)
    {
        int a = R[i][0], b = R[i][1];

        Tree[a]->Ch.push_back(Tree[b]);
        Tree[a]->Cost.push_back(L[i]);
        Tree[b]->Ch.push_back(Tree[a]);
        Tree[b]->Cost.push_back(L[i]);
    }

    for (int i = 0; i < k; i++)
    {
        Choice[exit[i]] = make_pair(0, 0);
        Check[exit[i]] = 2;
    }
    for (int i = 0; i < k; i++)
    {
        auto node = Tree[exit[i]];
        bloom(node, Choice, Check, Q);
    }    

    while (!Q.empty())
    {
        auto A = Q.top();
        Q.pop();
     
        switch(Check[A.end])
        {
            case 0:{ Choice[A.end].first = A.cost; break; }
            case 1:{ 
                Choice[A.end].second = A.cost; 
                bloom(Tree[A.end], Choice, Check, Q);                
            break; }
        }
        Check[A.end]++;
    }

    return Choice[0].second;
}

Compilation message (stderr)

crocodile.cpp: In function 'void bloom(nod*, std::vector<std::pair<int, int> >&, std::vector<int>&, std::priority_queue<muchie, std::vector<muchie>, bool (*)(muchie, muchie)>&)':
crocodile.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<nod*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i = 0; i < node->Ch.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~

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