Submission #1275830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275830		nanj0178	Race (IOI11_race)	C++20	0 / 100	2 ms	332 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; i++) {
        int x = H[i][0];
        int y = H[i][1];
        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]);
        }
    };
    auto dfs1 = [&](auto &&self, int cur, int pre, int root, map<LL, int> &m) -> void {
        LL need = K + 2 * path[root] - path[cur];
        if (m.count(need)) {
            ans = min(ans, m[need] + dep[cur] - 2 * dep[root]);
        }        
        for(auto [next, _] : E[cur]) {
            if (next == pre) continue;
            self(self, next, cur, root, m);
        }
    };
    auto dfs2 = [&](auto &&self, int cur, int pre, int root, map<LL, int> &m)-> void {
        add(cur, m);
        for(auto [next, _] : E[cur]) {
            if (next == pre) continue;
            self(self, next, cur, root, m);
        }
    };    
    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 cur = i;
        while(cur != -1) {
            
            int child = heavyChild[cur];
            for(auto [next, _]: E[cur]) {
                if (next == child) continue;
                dfs1(dfs1, next, cur, cur, mPath);
                dfs2(dfs2, next, cur, cur, mPath);
            }
            // 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;
            //     for(int i = tin[cur]; i < tin[child]; i++) check(dfsOrderV[i], cur, mPath);
            //     for(int i = tout[child] + 1; i <= tout[cur]; i++) check(dfsOrderV[i], cur, mPath);
            //     for(int i = tin[cur]; i < tin[child]; i++) add(dfsOrderV[i], mPath);
            //     for(int i = tout[child] + 1; i <= tout[cur]; i++) add(dfsOrderV[i], mPath);                
            // }
            // cout << cur << " check " << child << endl;; 
            check(cur, cur, mPath);
            add(cur, mPath);
            cur = heavyParent[cur];
        }
    }
    if (ans == N) {
        return  -1;
    }
    return ans;
}

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