Submission #374244

#	Time	Username	Problem	Language	Result	Execution time	Memory
374244		ijxjdjd	Race (IOI11_race)	C++14	21 / 100	200 ms	42604 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = (int)(2e5 + 5);
ll K;
vector<pair<int, int>> adj[MAXN];
struct paths {
    ll addL = 0;
    int addV = 0;
    unordered_map<ll, int> mn;
    paths() {
        mn[0] = 0;
    }
    bool contains(int a) {
        return mn.count(a-addL);
    }
    int get(int a) {
        return mn[a-addL] + addV;
    }
    void insert(ll v, int cnt) {
        if (contains(v) && get(v) > cnt) {
            mn[v-addL] = cnt-addV;
        }
        else {
            mn[v-addL] = cnt-addV;
        }
    }
    int size() {
        return mn.size();
    }
};
paths keep[MAXN];
int res = MAXN;
void dfs(int n, int p) {
    for (auto& e : adj[n]) {
        if (e.first != p) {
            dfs(e.first, n);
            keep[e.first].addL += e.second;
            keep[e.first].addV++;
            if (keep[n].size() < keep[e.first].size()) {
                swap(keep[e.first], keep[n]);
            }
            for (auto& keypair : keep[e.first].mn) {
                ll od = keypair.first + keep[e.first].addL;
                if (keep[n].contains(K-od)) {
                    res = min(keypair.second + keep[e.first].addV + keep[n].get(K-od), res);
                }
            }
            for (auto& keypair : keep[e.first].mn) {
                keep[n].insert(keypair.first + keep[e.first].addL, keypair.second + keep[e.first].addV);
            }
        }
    }
}
int best_path(int N, int k, int H[][2], int L[])
{
    for (int i = 0; i < N-1; i++) {
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }
    K = k;
    dfs(0, 0);
    return (res == MAXN ? -1 : res);
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57