oj.uz

Submission #233142

# Submission time Handle Problem Language Result Execution time Memory
233142 2020-05-19T14:31:11 Z Coroian_David Crocodile's Underground City (IOI11_crocodile) C++11
100 / 100
 682 ms 52064 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(ex[i] == 1 || (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 << dp[0] << "\n";
            //cout << " SUNTEM " <<cr << " " << dp[cr] << " " << d << "\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:76: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 6 ms 2816 KB Output is correct
5 Correct 7 ms 2816 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2816 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct

Subtask #2
43.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 6 ms 2816 KB Output is correct
5 Correct 7 ms 2816 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2816 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct
9 Correct 9 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 3072 KB Output is correct
13 Correct 9 ms 3072 KB Output is correct
14 Correct 6 ms 2688 KB Output is correct
15 Correct 7 ms 2816 KB Output is correct

Subtask #3
11.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 6 ms 2816 KB Output is correct
5 Correct 7 ms 2816 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2816 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct
9 Correct 9 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 3072 KB Output is correct
13 Correct 9 ms 3072 KB Output is correct
14 Correct 6 ms 2688 KB Output is correct
15 Correct 7 ms 2816 KB Output is correct
16 Correct 548 ms 47192 KB Output is correct
17 Correct 116 ms 15224 KB Output is correct
18 Correct 146 ms 16756 KB Output is correct
19 Correct 682 ms 52064 KB Output is correct
20 Correct 347 ms 41336 KB Output is correct
21 Correct 55 ms 8184 KB Output is correct
22 Correct 380 ms 36988 KB Output is correct