Submission #880601

#	Time	Username	Problem	Language	Result	Execution time	Memory
880601		_KuroNeko_	Race (IOI11_race)	C++17	100 / 100	307 ms	40016 KiB

race

#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<double> vdb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
typedef set<int> si;
typedef set<long long> sl;
typedef set<double> sdb;
typedef set<string> ss;
typedef set<char> sc;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ftb(i, a, b) for (int i = a, _b = b; i <= _b; ++i)
#define ft(i, a, b) for (int i = a, _b = b; i < _b; ++i)
#define fgb(i, a, b) for (int i = a, _b = b; i >= _b; --i)
#define fg(i, a, b) for (int i = a, _b = b; i > _b; --i)
#define endl "\n"
const int N = 2*1e5;
const int K = 1e6;
int subtree[N + 1];
int dis[K + 1];
bool check[N + 1];
vector<pii> adj[N + 1];
int sz = 0;
void find_subtree(int node, int parent) {
    subtree[node] = 1;
    for (pii it : adj[node]) {
        if (it.first != parent && !check[it.first]) {
            find_subtree(it.first, node);
            subtree[node] += subtree[it.first];
        }
    }
}
int centroid(int node, int parent) {
    for (pii it : adj[node]) {
        if (it.first != parent && !check[it.first]) {
            if (subtree[it.first] > sz / 2) {
                return centroid(it.first, node);
            }
        }
    }
    return node;
}
void dfs(int node, int type, int parent, int depth, int length, int k, int& ans) {
    if (length > k) return;
    if (type == 3) {
        dis[length] = 1e9;
        for (pii it : adj[node]) {
            if (it.first != parent && !check[it.first]) {
                dfs(it.first, type, node, depth + 1, length + it.second, k, ans);
            }
        }
    }
    else if (type == 2) {
        dis[length] = min(dis[length], depth);
        for (pii it : adj[node]) {
            if (it.first != parent && !check[it.first]) {
                dfs(it.first, type, node, depth + 1, length + it.second, k, ans);
            }
        }
    }
    else {
        ans = min(ans, depth + dis[k - length]);
        for (pii it : adj[node]) {
            if (it.first != parent && !check[it.first]) {
                dfs(it.first, type, node, depth + 1, length + it.second, k, ans);
            }
        }
    }
}
void solve(int i, int& ans, int k) {
    find_subtree(i, -1);
    sz = subtree[i];
    int node = centroid(i, -1);
    check[node] = true;
    dis[0] = 0;
    for (pii it : adj[node]) {
        if (check[it.first]) continue;
        dfs(it.first, 1, -1, 1, it.second, k, ans);
        dfs(it.first, 2, -1, 1, it.second, k, ans);
    }
    dfs(node, 3, -1, 0, 0, k, ans);
    for (pii it : adj[node]) {
        if (!check[it.first]) solve(it.first, ans, k);
    }
}
int best_path(int n, int k, int h[][2], int l[]) {
    ftb(i, 0, k) {
        dis[i] = 1e9;
    }
    ft(i, 0, n - 1) {
        adj[h[i][0]].push_back({ h[i][1],l[i] });
        adj[h[i][1]].push_back({ h[i][0],l[i] });
    }
    int ans = 1e9;
    solve(0, ans, k);
    if (ans == 1e9) ans = -1;
    return ans;
}
// int main() {
//     int n, k;
//     cin >> n >> k;
//     int h[n - 1][2];
//     int l[n - 1];
//     ft(i, 0, n - 1) {
//         int x, y, z;
//         cin >> x >> y >> z;
//         h[i][0] = x;
//         h[i][1] = y;
//         l[i] = z;
//     }
//     cout << best_path(n, k, h, l);
// }

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