Submission #990366

#	Time	Username	Problem	Language	Result	Execution time	Memory
990366		stdfloat	Race (IOI11_race)	C++17	43 / 100	3053 ms	33620 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;

using ll = long long;

#define ff  first
#define ss  second
#define pii pair<int, int>

int k, mn = INT_MAX;

vector<int> sz;

map<int, int> m;

vector<bool> vis;

vector<vector<pii>> v, E;

int dfs_sz(int x, int p = -1) {
    sz[x] = 1;
    for (auto [i, w] : E[x]) {
        if (i != p && !vis[i]) sz[x] += dfs_sz(i, x);
    }

    return sz[x];
}

int ctrd(int x, int p, int n) {
    for (auto [i, w] : E[x]) {
        if (i != p && !vis[i] && sz[i] > (n >> 1)) return ctrd(i, x, n);
    }

    return x;
}

void dfs(int x, int p, int d1, int d2) {
    for (auto [i, w] : E[x]) {
        // cout << "xi " << i << ' ' << vis[i] << ' ' << w << ' ' << d2 << endl;
        if (i != p && !vis[i] && w <= k - d2) {
        // cout << "xi " << i << ' ' << vis[i] << ' ' << w << ' ' << d2 << endl;
            // if (m.find(d2 + w) == m.end()) m[d2 + w] = d1 + 1;
            // else m2[d2 + w] = min(m2[d2 + w], d1 + 1);

            m[d2 + w] = min((m[d2 + w] ? m[d2 + w] : INT_MAX), d1 + 1);
            dfs(i, x, d1 + 1, d2 + w);
        }
    }
}

void f(int x, int p = -1) {
    int n = dfs_sz(x), c = ctrd(x, p, n);

    vis[c] = true;

    // cout << "\nn " << n << ' ' << c << endl;

    map<int, int> M; M[0] = 0;
    for (auto [i, w] : E[c]) {
        // m.clear();
        // m[w] = 1;
        m = {{w, 1}};
        dfs(i, c, 1, w);

        // cout << "ci " << i << ' ' << w << endl;
    
        for (auto i : m) {
            if (M.find(k - i.ff) != M.end()) mn = min(mn, M[k - i.ff] + i.ss);
            // cout << "i.ff " << i.ff << ' ' << i.ss << endl;
        }
        for (auto i : m)
            M[i.ff] = min((M[i.ff] ? M[i.ff] : INT_MAX), i.ss);
    }

    for (auto [i, w] : E[c])
        if (!vis[i]) f(i, c);
}

int best_path(int N, int K, int H[][2], int L[]) {
    k = K;
    E.assign(N, {});
    for (int i = 0; i < N - 1; i++) {
        E[H[i][0]].push_back({H[i][1], L[i]});
        E[H[i][1]].push_back({H[i][0], L[i]});
    }

    sz.assign(N, 0);
    vis.assign(N, false);
    f(0);

    return (mn == INT_MAX ? -1 : mn);
}

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