Submission #706938

#	Time	Username	Problem	Language	Result	Execution time	Memory
706938		Nhoksocqt1	Race (IOI11_race)	C++17	100 / 100	580 ms	53740 KiB

race

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

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 200005;

set<ii> G[MAXN];
int sz[MAXN], dp[5 * MAXN], numNode, pathLen;

int dfsSize(int u, int p) {
    sz[u] = 1;
    for (auto it : G[u]) {
        int v(it.fi);
        if(v != p)
            sz[u] += dfsSize(v, u);
    }

    return sz[u];
}

int centroid(int u, int p, int nSize) {
    for (auto it : G[u]) {
        int v(it.fi);
        if(v != p && sz[v] > nSize / 2)
            return centroid(v, u, nSize);
    }

    return u;
}

int dfs(int u, int p, int len, int cntNode, vector<ii> &dis) {
    if(len > pathLen)
        return 1e9+7;

    dis.push_back({len, cntNode + 1});
    int res = min(int(1e9)+7, cntNode + dp[pathLen - len]);
    for (auto it : G[u]) {
        int v(it.fi), w(it.se);
        if(v != p)
            res = min(res, dfs(v, u, len + w, cntNode + 1, dis));
    }

    return res;
}

int build(int u, int p) {
    int nSize = dfsSize(u, p);
    int c = centroid(u, p, nSize);

    dp[0] = 1;
    int res(1e9+7);
    vector<int> tmp;
    for (auto it : G[c]) {
        vector<ii> tmpn;
        int v(it.fi), w(it.se);
        res = min(res, dfs(v, c, w, 1, tmpn));
        while(tmpn.size()) {
            tmp.push_back(tmpn.back().fi);
            minimize(dp[tmp.back()], tmpn.back().se);
            tmpn.pop_back();
        }
    }

    for (int it = 0; it < int(tmp.size()); ++it) {
        int x(tmp[it]);
        dp[x] = 1e9+7;
    }

    vector<ii> tmpg(G[c].begin(), G[c].end());
    for (int it = 0; it < int(tmpg.size()); ++it) {
        int v(tmpg[it].fi), w(tmpg[it].se);
        G[c].erase({v, w});
        G[v].erase({c, w});
        res = min(res, build(v, c));
    }

    return res;
}

int best_path(int N, int K, int H[][2], int L[]) {
    numNode = N, pathLen = K;
    for (int i = 0; i + 1 < numNode; ++i) {
        int u(H[i][0]), v(H[i][1]), w(L[i]);
        G[u].insert({v, w});
        G[v].insert({u, w});
    }

    for (int i = 0; i <= pathLen; ++i)
        dp[i] = 1e9+7;

    int res = build(0, -1);
    return (res >= 1e9 ? -1 : res - 1);
}

Compilation message (stderr)

race.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
race.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      |

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