Submission #233141

#	Time	Username	Problem	Language	Result	Execution time	Memory
233141		Coroian_David	Crocodile's Underground City (IOI11_crocodile)	C++11	46 / 100	10 ms	3200 KiB

crocodile

#include <bits/stdc++.h>

#define MAX_N 100000
#define MAX_M 1000000

#include "crocodile.h"

#define xx first
#define yy second

using namespace std;

const int sqrInf = (int)(1e9) - 1;

vector <pair<int, int>> g[MAX_N + 1];

void add(int a, int b, int c)
{
    g[a].push_back({b, c});
}

int best[MAX_N + 1];
int dp[MAX_N + 1];
int ex[MAX_N + 1];
int viz[MAX_N + 1];

priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

void getNodes(int N)
{
    for(int i = 0; i < N; i ++)
    {
        if(g[i].size() == 2 && ex[i] == 0 && i != 0)
        {
            viz[i] = 1;
        }

        else
        {
            int s = 0;
            int m1 = sqrInf, m2 = sqrInf;
            for(auto u : g[i])
            {
                if(ex[u.xx])
                {

                    s ++;
                    if(u.yy < m1)
                    {
                        m2 = m1;
                        m1 = u.yy;
                    }

                    else if(u.yy < m2)
                        m2 = u.yy;
                }
            }

            best[i] = m1;
            dp[i] = m2;

            if(s >= 2)
            {
                q.push({m2, i});
            }
        }
    }
}

void getRez(int N)
{
    //cout << best[0] << " " << dp[0] << "\n";

    for(int x = 1; x <= 1000000 && q.size(); x ++)
    {
        int cr = q.top().second;
        int d = q.top().first;
        q.pop();

        if(viz[cr] == 0)
        {
            //cout << " SUNTEM " <<cr << " " << dp[cr] << "\n";

            viz[cr] = 1;
            for(auto u : g[cr])
            {
                int ok = 0;
                if(dp[cr] + u.yy < best[u.xx])
                {
                    ok = 1;
                    dp[u.xx] = best[u.xx];
                    best[u.xx] = dp[cr] + u.yy;
                }

                else
                    if(dp[cr] + u.yy < dp[u.xx])
                        dp[u.xx] = dp[cr] + u.yy, ok = 1;

                if(ok)
                    q.push({dp[u.xx], u.xx});
            }
        }
    }
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    for(int i = 0; i < M; i ++)
    {
        int a = R[i][0];
        int b = R[i][1];
        int c = L[i];
        add(a, b, c);
        add(b, a, c);
    }

    for(int i = 0; i < K; i ++)
        ex[P[i]] = 1;

    getNodes(N);

    getRez(N);

    return dp[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'void getRez(int)':
crocodile.cpp:77:13: warning: unused variable 'd' [-Wunused-variable]
         int d = q.top().first;
             ^

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