oj.uz

Submission #233141

# Submission time Handle Problem Language Result Execution time Memory
233141 2020-05-19T14:25:42 Z Coroian_David Crocodile's Underground City (IOI11_crocodile) C++11
46 / 100
 10 ms 3200 KB 
#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

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

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

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 7 ms 2688 KB Output is correct
5 Correct 7 ms 2816 KB Output is correct
6 Correct 6 ms 2816 KB Output is correct
7 Correct 7 ms 2816 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct
9 Correct 8 ms 2944 KB Output is correct
10 Correct 6 ms 2688 KB Output is correct
11 Correct 7 ms 2816 KB Output is correct
12 Correct 10 ms 3200 KB Output is correct
13 Correct 9 ms 3200 KB Output is correct
14 Incorrect 6 ms 2688 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 7 ms 2688 KB Output is correct
5 Correct 7 ms 2816 KB Output is correct
6 Correct 6 ms 2816 KB Output is correct
7 Correct 7 ms 2816 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct
9 Correct 8 ms 2944 KB Output is correct
10 Correct 6 ms 2688 KB Output is correct
11 Correct 7 ms 2816 KB Output is correct
12 Correct 10 ms 3200 KB Output is correct
13 Correct 9 ms 3200 KB Output is correct
14 Incorrect 6 ms 2688 KB Output isn't correct
15 Halted 0 ms 0 KB -