Submission #1248897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248897		12baater	Crocodile's Underground City (IOI11_crocodile)	C++20	46 / 100	201 ms	327680 KiB

crocodile

#include "crocodile.h"
#include <functional>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>


using namespace std;
typedef long long ll;

const ll INF = 1E15;
const int MAXN = 100010;

vector<pair<int,int>> adj[MAXN];
int depths[MAXN];
int maxDepth = 0;
bool done[MAXN];
bool isExit[MAXN];

priority_queue<int, vector<int>, greater<>> values[MAXN];

void dfs(int node, int parent, int depth) {
    depths[node] = depth;
    maxDepth = max(depth, maxDepth);
    for (auto [child, cost] : adj[node]) {
        if (child == parent) continue;
        dfs(child, node, depth+1);
    }
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    for (int i = 0; i < K; i++) {
        isExit[P[i]] = true;
        values[P[i]].push(0);
        values[P[i]].push(0);
    }
    for (int i = 0; i < M; i++) {
        int a = R[i][0], b = R[i][1], c = L[i];
        adj[a].emplace_back(b,c);
        adj[b].emplace_back(a,c);
    }

    dfs(0, 0, 0);

    vector<vector<int>> v(maxDepth+1, vector<int>());
    for (int i = 0; i < N; i++) {
        v[depths[i]].push_back(i);
    }

    for (int i = maxDepth; i > 0; i--) {
        for (int node : v[i]) {
            if (values[node].size() < 2) continue;
            values[node].pop();
            int a = values[node].top();
            for (auto [child, cost] : adj[node]) {
                values[child].push(a+cost);
            }
        }
    }

    values[0].pop();
    return values[0].top();
}

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