oj.uz

Submission #1047125

# Submission time Handle Problem Language Result Execution time Memory
1047125 2024-08-07T09:09:09 Z Sharky Race (IOI11_race) C++17
100 / 100
 1231 ms 228008 KB 
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct thing {
    int dist, d, u;
    bool operator < (const thing &b) const {
        if (dist!=b.dist) return dist < b.dist;
        if (d!=b.d) return d < b.d;
        return u < b.u;
    }
};
struct node {
    pair<int,int> val;
    int lpt, rpt;
};
 
const int maxn = 2e5 + 5, maxN = 8e5 + 5, INF = 1e18;
int n, k;
vector<pair<int,int>> adj[maxn];
int sz[maxn], dist[maxn], d[maxn];
bool cmp(pair<int,int> x, pair<int,int> y) {
    return sz[x.first] > sz[y.first];
}
 
void dfs0(int u) {
    sz[u] = 1;
    for (auto [v, w]:adj[u]) {
        adj[v].erase(find(adj[v].begin(), adj[v].end(), make_pair(u, w)));
        dist[v] = dist[u] + w, d[v] = d[u] + 1;
        dfs0(v);
        sz[u] += sz[v];
    }
    sort(adj[u].begin(), adj[u].end(), cmp);
}
int newid[maxn], oldid[maxn], lim[maxn], cnt = -1;
void dfs1(int u) {
    cnt++;
    newid[u] = cnt, oldid[cnt] = u;
    for (auto [v, w]:adj[u]) dfs1(v);
    lim[u] = cnt;
}
 
vector<node> seg[maxN];
void build(int id, int l, int r) {
    seg[id] = {{{-INF, -INF}, 0, 0}};
    if (l==r) return;
    int mid = (l+r)/2;
    build(id*2, l, mid); build(id*2+1, mid+1, r);
}
void update(int id, int l, int r, int target, pair<int,int> val) {
    if (r<target || target<l) return;
    if (l==r) {
        seg[id].push_back({val, 0, 0});
        return;
    }
    int mid = (l+r)/2;
    update(id*2, l, mid, target, val); update(id*2+1, mid+1, r, target, val);
    pair<int,int> cur = max(seg[id*2].back().val, seg[id*2+1].back().val);
    seg[id].push_back({cur, (int)seg[id*2].size()-1, (int)seg[id*2+1].size()-1});
}
pair<int,int> qry(int id, int pt, int l, int r, int findl, int findr) {
    if (r<findl || findr<l) return {-INF, -INF};
    if (findl<=l && r<=findr) return seg[id][pt].val;
    int mid = (l+r)/2;
    pair<int,int> lhs = qry(id*2, seg[id][pt].lpt, l, mid, findl, findr);
    pair<int,int> rhs = qry(id*2+1, seg[id][pt].rpt, mid+1, r, findl, findr);
    return max(lhs, rhs);
}
 
int ans = INF, curD;
vector<thing> vec = {{-INF, -INF, -INF}};
void QRY(int l, int r, int val) {
    if (val<0) return;
    thing cur = {val, INF, INF};
    int pos = upper_bound(vec.begin(), vec.end(), cur) - vec.begin() - 1;
    // cout << l << " " << r << " " << val << " " << pos << endl;
    pair<int,int> temp = qry(1, pos, 0, n-1, l, r);
    // cout << temp.first << " " << temp.second << endl;
    if (temp.first!=val) return;
    ans = min(-temp.second + curD, ans);
}
 
int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[]) {
    n = N, k = K;
    for (int i=0;i<n-1;i++) {
        auto [u, v] = H[i];
        adj[u].push_back({v, L[i]});
        adj[v].push_back({u, L[i]});
    }
    dist[0] = 0, d[0] = 0;
    dfs0(0); dfs1(0);
    // for (int i=0;i<n;i++) cout << newid[i] << " "; cout << endl;
    for (int i=0;i<n;i++) vec.push_back({dist[i], -d[i], newid[i]});
    sort(vec.begin(), vec.end());
    build(1, 0, n-1);
    for (int i=1;i<=n;i++) {
        update(1, 0, n-1, vec[i].u, {vec[i].dist, vec[i].d});
        // cout << i << " " << vec[i].u << " " << vec[i].dist << " " << vec[i].d << endl;
    }
    for (int u=0;u<n;u++) {
        curD = -d[u];
        // if (u==6) cout << "TEST" << endl;
        QRY(newid[u]+1, lim[u], k + dist[u]);
        // if (u==6) cout << k+dist[u] << endl;
        for (int i=1;i<adj[u].size();i++) {
            int v = adj[u][i].first;
            for (int j=newid[v];j<=lim[v];j++) {
                curD = -2*d[u] + d[oldid[j]];
                QRY(newid[u]+1, newid[v]-1, k + 2*dist[u] - dist[oldid[j]]);
            }
        }
    }
    if (ans==INF) return -1;
    return ans;
}

Compilation message

race.cpp: In function 'int32_t best_path(int32_t, int32_t, int32_t (*)[2], int32_t*)':
race.cpp:106:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for (int i=1;i<adj[u].size();i++) {
      |                      ~^~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 36956 KB Output is correct
2 Correct 6 ms 37028 KB Output is correct
3 Correct 7 ms 36956 KB Output is correct
4 Correct 5 ms 36956 KB Output is correct
5 Correct 4 ms 36956 KB Output is correct
6 Correct 4 ms 36956 KB Output is correct
7 Correct 5 ms 36952 KB Output is correct
8 Correct 4 ms 36956 KB Output is correct
9 Correct 5 ms 36952 KB Output is correct
10 Correct 5 ms 36956 KB Output is correct
11 Correct 5 ms 36956 KB Output is correct
12 Correct 4 ms 36956 KB Output is correct
13 Correct 4 ms 36908 KB Output is correct
14 Correct 4 ms 36956 KB Output is correct
15 Correct 4 ms 36956 KB Output is correct
16 Correct 4 ms 36956 KB Output is correct
17 Correct 4 ms 36956 KB Output is correct
18 Correct 5 ms 36956 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 36956 KB Output is correct
2 Correct 6 ms 37028 KB Output is correct
3 Correct 7 ms 36956 KB Output is correct
4 Correct 5 ms 36956 KB Output is correct
5 Correct 4 ms 36956 KB Output is correct
6 Correct 4 ms 36956 KB Output is correct
7 Correct 5 ms 36952 KB Output is correct
8 Correct 4 ms 36956 KB Output is correct
9 Correct 5 ms 36952 KB Output is correct
10 Correct 5 ms 36956 KB Output is correct
11 Correct 5 ms 36956 KB Output is correct
12 Correct 4 ms 36956 KB Output is correct
13 Correct 4 ms 36908 KB Output is correct
14 Correct 4 ms 36956 KB Output is correct
15 Correct 4 ms 36956 KB Output is correct
16 Correct 4 ms 36956 KB Output is correct
17 Correct 4 ms 36956 KB Output is correct
18 Correct 5 ms 36956 KB Output is correct
19 Correct 6 ms 36956 KB Output is correct
20 Correct 5 ms 36956 KB Output is correct
21 Correct 6 ms 37600 KB Output is correct
22 Correct 6 ms 37464 KB Output is correct
23 Correct 6 ms 37468 KB Output is correct
24 Correct 6 ms 37468 KB Output is correct
25 Correct 6 ms 37600 KB Output is correct
26 Correct 6 ms 37468 KB Output is correct
27 Correct 5 ms 37468 KB Output is correct
28 Correct 6 ms 37468 KB Output is correct
29 Correct 6 ms 37468 KB Output is correct
30 Correct 6 ms 37468 KB Output is correct
31 Correct 5 ms 37468 KB Output is correct
32 Correct 6 ms 37468 KB Output is correct
33 Correct 6 ms 37468 KB Output is correct
34 Correct 5 ms 37468 KB Output is correct
35 Correct 6 ms 37468 KB Output is correct
36 Correct 5 ms 37468 KB Output is correct
37 Correct 5 ms 37468 KB Output is correct
38 Correct 6 ms 37512 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 36956 KB Output is correct
2 Correct 6 ms 37028 KB Output is correct
3 Correct 7 ms 36956 KB Output is correct
4 Correct 5 ms 36956 KB Output is correct
5 Correct 4 ms 36956 KB Output is correct
6 Correct 4 ms 36956 KB Output is correct
7 Correct 5 ms 36952 KB Output is correct
8 Correct 4 ms 36956 KB Output is correct
9 Correct 5 ms 36952 KB Output is correct
10 Correct 5 ms 36956 KB Output is correct
11 Correct 5 ms 36956 KB Output is correct
12 Correct 4 ms 36956 KB Output is correct
13 Correct 4 ms 36908 KB Output is correct
14 Correct 4 ms 36956 KB Output is correct
15 Correct 4 ms 36956 KB Output is correct
16 Correct 4 ms 36956 KB Output is correct
17 Correct 4 ms 36956 KB Output is correct
18 Correct 5 ms 36956 KB Output is correct
19 Correct 328 ms 122796 KB Output is correct
20 Correct 309 ms 123320 KB Output is correct
21 Correct 315 ms 123084 KB Output is correct
22 Correct 348 ms 123072 KB Output is correct
23 Correct 545 ms 123208 KB Output is correct
24 Correct 432 ms 123064 KB Output is correct
25 Correct 230 ms 126040 KB Output is correct
26 Correct 129 ms 129572 KB Output is correct
27 Correct 423 ms 213408 KB Output is correct
28 Correct 684 ms 228008 KB Output is correct
29 Correct 720 ms 227448 KB Output is correct
30 Correct 414 ms 212136 KB Output is correct
31 Correct 436 ms 216456 KB Output is correct
32 Correct 703 ms 212908 KB Output is correct
33 Correct 851 ms 211872 KB Output is correct
34 Correct 1030 ms 211624 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 36956 KB Output is correct
2 Correct 6 ms 37028 KB Output is correct
3 Correct 7 ms 36956 KB Output is correct
4 Correct 5 ms 36956 KB Output is correct
5 Correct 4 ms 36956 KB Output is correct
6 Correct 4 ms 36956 KB Output is correct
7 Correct 5 ms 36952 KB Output is correct
8 Correct 4 ms 36956 KB Output is correct
9 Correct 5 ms 36952 KB Output is correct
10 Correct 5 ms 36956 KB Output is correct
11 Correct 5 ms 36956 KB Output is correct
12 Correct 4 ms 36956 KB Output is correct
13 Correct 4 ms 36908 KB Output is correct
14 Correct 4 ms 36956 KB Output is correct
15 Correct 4 ms 36956 KB Output is correct
16 Correct 4 ms 36956 KB Output is correct
17 Correct 4 ms 36956 KB Output is correct
18 Correct 5 ms 36956 KB Output is correct
19 Correct 6 ms 36956 KB Output is correct
20 Correct 5 ms 36956 KB Output is correct
21 Correct 6 ms 37600 KB Output is correct
22 Correct 6 ms 37464 KB Output is correct
23 Correct 6 ms 37468 KB Output is correct
24 Correct 6 ms 37468 KB Output is correct
25 Correct 6 ms 37600 KB Output is correct
26 Correct 6 ms 37468 KB Output is correct
27 Correct 5 ms 37468 KB Output is correct
28 Correct 6 ms 37468 KB Output is correct
29 Correct 6 ms 37468 KB Output is correct
30 Correct 6 ms 37468 KB Output is correct
31 Correct 5 ms 37468 KB Output is correct
32 Correct 6 ms 37468 KB Output is correct
33 Correct 6 ms 37468 KB Output is correct
34 Correct 5 ms 37468 KB Output is correct
35 Correct 6 ms 37468 KB Output is correct
36 Correct 5 ms 37468 KB Output is correct
37 Correct 5 ms 37468 KB Output is correct
38 Correct 6 ms 37512 KB Output is correct
39 Correct 328 ms 122796 KB Output is correct
40 Correct 309 ms 123320 KB Output is correct
41 Correct 315 ms 123084 KB Output is correct
42 Correct 348 ms 123072 KB Output is correct
43 Correct 545 ms 123208 KB Output is correct
44 Correct 432 ms 123064 KB Output is correct
45 Correct 230 ms 126040 KB Output is correct
46 Correct 129 ms 129572 KB Output is correct
47 Correct 423 ms 213408 KB Output is correct
48 Correct 684 ms 228008 KB Output is correct
49 Correct 720 ms 227448 KB Output is correct
50 Correct 414 ms 212136 KB Output is correct
51 Correct 436 ms 216456 KB Output is correct
52 Correct 703 ms 212908 KB Output is correct
53 Correct 851 ms 211872 KB Output is correct
54 Correct 1030 ms 211624 KB Output is correct
55 Correct 25 ms 44812 KB Output is correct
56 Correct 21 ms 44880 KB Output is correct
57 Correct 274 ms 122888 KB Output is correct
58 Correct 246 ms 124084 KB Output is correct
59 Correct 121 ms 129272 KB Output is correct
60 Correct 394 ms 225920 KB Output is correct
61 Correct 456 ms 214696 KB Output is correct
62 Correct 400 ms 212912 KB Output is correct
63 Correct 522 ms 213956 KB Output is correct
64 Correct 688 ms 213400 KB Output is correct
65 Correct 1231 ms 215208 KB Output is correct
66 Correct 581 ms 228008 KB Output is correct
67 Correct 600 ms 216228 KB Output is correct
68 Correct 669 ms 215872 KB Output is correct
69 Correct 692 ms 216096 KB Output is correct
70 Correct 689 ms 208144 KB Output is correct