oj.uz

Submission #706938

# Submission time Handle Problem Language Result Execution time Memory
706938 2023-03-08T06:55:21 Z Nhoksocqt1 Race (IOI11_race) C++17
100 / 100
 580 ms 53740 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9624 KB Output is correct
2 Correct 5 ms 9700 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9700 KB Output is correct
5 Correct 5 ms 9680 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 5 ms 9700 KB Output is correct
9 Correct 5 ms 9700 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9704 KB Output is correct
12 Correct 5 ms 9704 KB Output is correct
13 Correct 5 ms 9696 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9716 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 5 ms 9700 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9624 KB Output is correct
2 Correct 5 ms 9700 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9700 KB Output is correct
5 Correct 5 ms 9680 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 5 ms 9700 KB Output is correct
9 Correct 5 ms 9700 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9704 KB Output is correct
12 Correct 5 ms 9704 KB Output is correct
13 Correct 5 ms 9696 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9716 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 5 ms 9700 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 5 ms 9684 KB Output is correct
21 Correct 6 ms 9840 KB Output is correct
22 Correct 8 ms 13424 KB Output is correct
23 Correct 8 ms 12756 KB Output is correct
24 Correct 8 ms 13140 KB Output is correct
25 Correct 8 ms 13140 KB Output is correct
26 Correct 7 ms 11124 KB Output is correct
27 Correct 9 ms 12920 KB Output is correct
28 Correct 6 ms 10608 KB Output is correct
29 Correct 7 ms 11092 KB Output is correct
30 Correct 7 ms 11252 KB Output is correct
31 Correct 8 ms 12372 KB Output is correct
32 Correct 7 ms 12628 KB Output is correct
33 Correct 8 ms 13012 KB Output is correct
34 Correct 7 ms 12116 KB Output is correct
35 Correct 7 ms 12972 KB Output is correct
36 Correct 8 ms 13396 KB Output is correct
37 Correct 8 ms 12912 KB Output is correct
38 Correct 7 ms 11760 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9624 KB Output is correct
2 Correct 5 ms 9700 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9700 KB Output is correct
5 Correct 5 ms 9680 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 5 ms 9700 KB Output is correct
9 Correct 5 ms 9700 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9704 KB Output is correct
12 Correct 5 ms 9704 KB Output is correct
13 Correct 5 ms 9696 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9716 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 5 ms 9700 KB Output is correct
19 Correct 196 ms 22240 KB Output is correct
20 Correct 180 ms 22216 KB Output is correct
21 Correct 200 ms 22580 KB Output is correct
22 Correct 203 ms 22844 KB Output is correct
23 Correct 118 ms 22104 KB Output is correct
24 Correct 106 ms 22020 KB Output is correct
25 Correct 201 ms 25500 KB Output is correct
26 Correct 135 ms 29808 KB Output is correct
27 Correct 277 ms 34496 KB Output is correct
28 Correct 440 ms 47172 KB Output is correct
29 Correct 366 ms 46180 KB Output is correct
30 Correct 297 ms 34500 KB Output is correct
31 Correct 297 ms 34380 KB Output is correct
32 Correct 334 ms 34516 KB Output is correct
33 Correct 343 ms 34684 KB Output is correct
34 Correct 278 ms 35436 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9624 KB Output is correct
2 Correct 5 ms 9700 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9700 KB Output is correct
5 Correct 5 ms 9680 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 5 ms 9700 KB Output is correct
9 Correct 5 ms 9700 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 5 ms 9704 KB Output is correct
12 Correct 5 ms 9704 KB Output is correct
13 Correct 5 ms 9696 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9716 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 5 ms 9700 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 5 ms 9684 KB Output is correct
21 Correct 6 ms 9840 KB Output is correct
22 Correct 8 ms 13424 KB Output is correct
23 Correct 8 ms 12756 KB Output is correct
24 Correct 8 ms 13140 KB Output is correct
25 Correct 8 ms 13140 KB Output is correct
26 Correct 7 ms 11124 KB Output is correct
27 Correct 9 ms 12920 KB Output is correct
28 Correct 6 ms 10608 KB Output is correct
29 Correct 7 ms 11092 KB Output is correct
30 Correct 7 ms 11252 KB Output is correct
31 Correct 8 ms 12372 KB Output is correct
32 Correct 7 ms 12628 KB Output is correct
33 Correct 8 ms 13012 KB Output is correct
34 Correct 7 ms 12116 KB Output is correct
35 Correct 7 ms 12972 KB Output is correct
36 Correct 8 ms 13396 KB Output is correct
37 Correct 8 ms 12912 KB Output is correct
38 Correct 7 ms 11760 KB Output is correct
39 Correct 196 ms 22240 KB Output is correct
40 Correct 180 ms 22216 KB Output is correct
41 Correct 200 ms 22580 KB Output is correct
42 Correct 203 ms 22844 KB Output is correct
43 Correct 118 ms 22104 KB Output is correct
44 Correct 106 ms 22020 KB Output is correct
45 Correct 201 ms 25500 KB Output is correct
46 Correct 135 ms 29808 KB Output is correct
47 Correct 277 ms 34496 KB Output is correct
48 Correct 440 ms 47172 KB Output is correct
49 Correct 366 ms 46180 KB Output is correct
50 Correct 297 ms 34500 KB Output is correct
51 Correct 297 ms 34380 KB Output is correct
52 Correct 334 ms 34516 KB Output is correct
53 Correct 343 ms 34684 KB Output is correct
54 Correct 278 ms 35436 KB Output is correct
55 Correct 19 ms 11036 KB Output is correct
56 Correct 17 ms 11072 KB Output is correct
57 Correct 114 ms 23212 KB Output is correct
58 Correct 83 ms 22920 KB Output is correct
59 Correct 129 ms 30584 KB Output is correct
60 Correct 580 ms 53740 KB Output is correct
61 Correct 289 ms 35016 KB Output is correct
62 Correct 313 ms 39608 KB Output is correct
63 Correct 377 ms 39584 KB Output is correct
64 Correct 544 ms 39584 KB Output is correct
65 Correct 309 ms 35388 KB Output is correct
66 Correct 464 ms 48428 KB Output is correct
67 Correct 379 ms 41324 KB Output is correct
68 Correct 388 ms 39820 KB Output is correct
69 Correct 440 ms 40060 KB Output is correct
70 Correct 373 ms 38688 KB Output is correct