oj.uz

Submission #237250

# Submission time Handle Problem Language Result Execution time Memory
237250 2020-06-05T12:58:31 Z nicolaalexandra Crocodile's Underground City (IOI11_crocodile) C++14
46 / 100
 12 ms 5248 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
#define DIMN 100010
#define DIMM 1000010
#define INF 2000000000
using namespace std;

priority_queue <pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > H;
vector <pair<int,int> > L[DIMN],edg[DIMN];
int f[DIMN],dp[DIMN],dist[DIMN],viz[DIMN];
pair <int,int> fth[DIMN];
void dfs (int nod, int tata){

    for (auto it : edg[nod]){
        int vecin = it.first;
        if (vecin != tata)
            dfs (vecin,nod);
    }

    if (f[nod]){ /// e nod special
        dp[nod] = 0;
    } else {

        int mini = INF, mini2 = INF;
        for (auto it : edg[nod]){
            int vecin = it.first, cost = it.second;
            if (vecin == tata)
                continue;
            if (dp[vecin] + cost < mini)
                mini2 = mini, mini = dp[vecin] + cost;
            else {
                if (dp[vecin] + cost < mini2)
                    mini2 = dp[vecin] + cost;
            }
        }

        if (mini2 != INF)
            dp[nod] = mini2;
        else dp[nod] = mini;

    }
}
int travel_plan (int n, int m, int r[][2], int l[], int k, int p[]){
    int i;

    for (i=0;i<m;i++){
        int x = r[i][0]+1, y = r[i][1]+1;
        L[x].push_back(make_pair(y,l[i]));
        L[y].push_back(make_pair(x,l[i]));
    }

    for (i=0;i<k;i++){
        int x = p[i] + 1;
        f[x] = 1;
    }

    for (i=1;i<=n;i++)
        dist[i] = INF;

    H.push(make_pair(0,1));
    dist[1] = 0;

    while (!H.empty()){
        int nod = H.top().second;
        int cost = H.top().first;
        H.pop();
        if (cost > dist[nod])
            continue;
        for (auto it : L[nod]){
            int vecin = it.first, new_cost = it.second;
            if (dist[nod] + new_cost < dist[vecin]){
                dist[vecin] = dist[nod] + new_cost;
                fth[vecin] = make_pair(nod,new_cost);
                H.push(make_pair(dist[vecin],vecin));
            }}}

    viz[1] = 1;
    for (i=1;i<=n;i++){
        if (!f[i])
            continue;

        int x = i;
        while (!viz[x]){
            viz[x] = 1;
            edg[fth[x].first].push_back(make_pair(x,fth[x].second));
            edg[x].push_back(make_pair(fth[x].first,fth[x].second));
            //cout<<x<<" "<<fth[x].first<<endl;
            x = fth[x].first;
        }

    }

    dfs (1,0);

    return dp[1];

}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 8 ms 4992 KB Output is correct
3 Correct 9 ms 4992 KB Output is correct
4 Correct 8 ms 5248 KB Output is correct
5 Correct 8 ms 5120 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 8 ms 5248 KB Output is correct
8 Correct 8 ms 5248 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 8 ms 4992 KB Output is correct
3 Correct 9 ms 4992 KB Output is correct
4 Correct 8 ms 5248 KB Output is correct
5 Correct 8 ms 5120 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 8 ms 5248 KB Output is correct
8 Correct 8 ms 5248 KB Output is correct
9 Correct 12 ms 5248 KB Output is correct
10 Incorrect 8 ms 5124 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 8 ms 4992 KB Output is correct
3 Correct 9 ms 4992 KB Output is correct
4 Correct 8 ms 5248 KB Output is correct
5 Correct 8 ms 5120 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 8 ms 5248 KB Output is correct
8 Correct 8 ms 5248 KB Output is correct
9 Correct 12 ms 5248 KB Output is correct
10 Incorrect 8 ms 5124 KB Output isn't correct
11 Halted 0 ms 0 KB -