Submission #1275852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275852		nanj0178	경주 (Race) (IOI11_race)	C++20	100 / 100	294 ms	54984 KiB

race

#include <bitset>
#include<iostream>
#include<vector>
#include<array>
#include<algorithm>
#include<set>
#include<cmath>
#include<unordered_map>
#include<iomanip>
#include <map>
#include <queue>
#include <stack>
#include <cstring>
#include <climits>
#include <chrono>
#include <random>
#include <cassert>
using namespace std;
#define PRINTARRAY(st, en, a) for(int _i = st; _i <= en; _i++) {cout << a[_i] << (_i != en ? " " : "\n");}
#define SZ(A) (int)A.size()
using LL = long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<vector<array<LL,2>>> E;
vector<int> dep;
vector<LL> path;
vector<int> tin;
vector<int> tout;
vector<int> dfsOrderV;
vector<int> heavyChild;
vector<int> groupSize;
vector<int> heavyParent;
int dfsOrder;
void dfs(int cur, int pre, int d, LL p) {
    dfsOrder++;
    tin[cur] = dfsOrder;
    dfsOrderV[dfsOrder] = cur;
    path[cur] = p;
    dep[cur] = d;
    int subGroupMax = 0;
    int heavyChildId = -1;
    for(auto [next, w] : E[cur]) {
        if (pre == next) continue;
        dfs(next, cur, d + 1, p + w);
        groupSize[cur] += groupSize[next];
        if (groupSize[next] > subGroupMax) {
            subGroupMax = groupSize[next];
            heavyChildId = next;
        }
    }
    if (heavyChildId != -1) {
        heavyChild[cur] = heavyChildId;
        heavyParent[heavyChildId] = cur;
    }
    tout[cur] = dfsOrder;
}
int best_path(int N, int K, int H[][2], int L[]) {
    E.assign(N + 1, {});
    dep.assign(N + 1, 0);
    path.assign(N + 1, 0);
    dfsOrderV.assign(N + 1, 0);
    tin.assign(N + 1, 0);
    tout.assign(N + 1, 0);
    heavyChild.assign(N + 1, -1);
    groupSize.assign(N + 1, 1);
    heavyParent.assign(N + 1, -1);

    for(int i = 0; i < N - 1; i++) {
        int x = H[i][0];
        int y = H[i][1];
        // cout << x << " " << y << endl;
        int w = L[i];
        E[x].push_back({y, w});
        E[y].push_back({x, w});
    }
    dfsOrder = 0;
    dfs(0, 0, 1, 0);
    // cout << "FIN" << endl;
    // PRINTARRAY(0, N - 1, path);
    // PRINTARRAY(0, N - 1, tin);
    // PRINTARRAY(0, N - 1, tout);
    // PRINTARRAY(0, N - 1, heavyChild);
    auto add = [&](int x, map<LL, int> &m) {
        if (m.count(path[x])) {
            m[path[x]] = min(m[path[x]], dep[x]);
        } else {
            m[path[x]] = dep[x];
        }
    };
    int ans = N;
    auto check = [&](int cur, int root, map<LL, int> &m) {
        if (cur == -1) return;
        LL need = K + 2 * path[root] - path[cur];
        if (m.count(need)) {
            // cout << cur << " " << root << " " << need << " " << m[need] + dep[cur] - 2 * dep[root] << endl;
            ans = min(ans, m[need] + dep[cur] - 2 * dep[root]);
        }
    };
    for(int i = 0; i < N; i++) {
        if (groupSize[i] != 1) continue;
        // cout << "----------" << endl;
        // cout << "st:" << i <<endl;
        // start on leaf
        map<LL, int> mPath;
        int leaf = i;
        add(leaf, mPath);
         for (int u = leaf; heavyParent[u] != -1; u = heavyParent[u]) {
            int p = heavyParent[u];
            // cout << p << " " << u << " check ";
            // for(auto [next, _] : E[p]) {
            //     cout << next << " ";
            // }
            // cout << endl;
            for(auto [next, _] : E[p]) {
                if (u == next) continue;
                if (dep[next] <= dep[p]) continue;
                for(int i = tin[next]; i <= tout[next]; i++) check(dfsOrderV[i], p, mPath);
                for(int i = tin[next]; i <= tout[next]; i++) add(dfsOrderV[i], mPath);      
                // cout << "|C:" <<next << "|"; 
                // for(int i = tin[next]; i <= tout[next]; i++) cout << dfsOrderV[i] << " ";
            }
            // cout << endl;
            // if (child != -1) {
            //     // cout << cur << " check ";
            //     // for(int i = tin[cur] + 1; i < tin[child]; i++) cout << dfsOrderV[i] << " ";
            //     // for(int i = tout[child] + 1; i <= tout[cur]; i++) cout << dfsOrderV[i] << " ";
            //     // cout << endl;
            // }
            // cout << cur << " check " << child << endl;; 
            check(p, p, mPath);
            add(p, mPath);
        }
    }
    if (ans == N) {
        return  -1;
    }
    return ans;
}

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