oj.uz

Submission #237234

# Submission time Handle Problem Language Result Execution time Memory
237234 2020-06-05T11:22:24 Z nicolaalexandra Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 6 ms 2816 KB 
#include <bits/stdc++.h>
#include "crocodile.h"
#define DIMN 100010
#define DIMM 1000010
#define INF 2000000000
using namespace std;

struct idk{
    int mini,mini2,fiu,fiu2;
};
idk dp[DIMN];
vector <pair<int,int> > L[DIMN];
map <pair<int,int>, int> cost;
int f[DIMN];

void dfs (int nod, int tata){

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

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

        int mini = INF, mini2 = INF, fiu = 0, fiu2 = 0;
        for (auto it : L[nod]){
            int vecin = it.first, cost = it.second;
            if (vecin == tata)
                continue;

            if (dp[vecin].mini2 + cost < mini){
                mini2 = mini, fiu2 = fiu;
                mini = dp[vecin].mini2 + cost, fiu = vecin;
            } else {
                if (dp[vecin].mini2 + cost < mini2)
                    mini2 = dp[vecin].mini2 + cost, fiu2 = vecin;
            }

        }



        //dp[nod].mini = mini, dp[nod].mini2 = mini2;
        dp[nod].mini = dp[fiu].mini + cost[make_pair(nod,fiu)];
        dp[nod].mini2 = dp[fiu2].mini + cost[make_pair(nod,fiu2)];
        dp[nod].fiu = fiu, dp[nod].fiu2 = fiu2;

    }

}

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]));
        cost[make_pair(x,y)] = l[i];
        cost[make_pair(y,x)] = l[i];
    }

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

    dfs (1,0);

    int x = 1, sol = 0;
    while (!f[x]){
        if (dp[x].fiu2){
            sol += cost[make_pair(x,dp[x].fiu2)];
            x = dp[x].fiu2;
        } else {
            sol += cost[make_pair(x,dp[x].fiu)];
            x = dp[x].fiu;
        }
    }

    return sol;

}

Subtask #1
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 Incorrect 6 ms 2816 KB Output isn't correct
4 Halted 0 ms 0 KB -

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 Incorrect 6 ms 2816 KB Output isn't correct
4 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 Incorrect 6 ms 2816 KB Output isn't correct
4 Halted 0 ms 0 KB -