oj.uz

Submission #978912

# Submission time Handle Problem Language Result Execution time Memory
978912 2024-05-10T01:42:28 Z lucas Race (IOI11_race) C++17
100 / 100
 866 ms 86704 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define F0R(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i <= b; i++)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define FORd(i,a,b) for (int i = (b); i >= (a); i--)
#define trav(a, x) for (auto& a : x)
#define rep(i, a, b) for(int i = a; i < (b); ++i)

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

const char nl = '\n';
const int MAX_N = 100011;
const ll INF = (1<<29) + 123;
const ll MOD = 1000000007; // 998244353
const ld PI = 4*atan((ld)1);

template <typename T> bool ckmin(T& a, const T& b) { return a > b ? a=b, 1 : 0; }
template <typename T> bool ckmax(T& a, const T& b) { return b > a ? a=b, 1 : 0; }

/**** Credit to chatgpt 4.0 ****/

// Stream operator for std::pair
template<typename T1, typename T2>
ostream& operator<<(ostream &out, const pair<T1, T2> &v) {
    out << "(" << v.first << ", " << v.second << ")"; 
    return out;
}

// Trait to check if a type is iterable
template<typename T, typename = void>
struct is_iterable : false_type {};

template<typename T>
struct is_iterable<T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>> : true_type {};

// Stream operator for iterable types excluding std::string
template<typename TT>
typename enable_if<is_iterable<TT>::value && !is_same<TT, string>::value, ostream&>::type
operator<<(ostream& out, const TT& c) {
    out << "{ ";
    for (const auto& x : c) out << x << " ";
    out << "}"; 
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, std::stack<T> container) {
    std::vector<T> elements;
    while (!container.empty()) {
        elements.push_back(container.top());
        container.pop();
    }
    std::reverse(elements.begin(), elements.end()); // Reverse to maintain order
    return out << elements;
}

template<typename T>
ostream& operator<<(ostream& out, std::queue<T> container) {
    std::vector<T> elements;
    while (!container.empty()) {
        elements.push_back(container.front());
        container.pop();
    }
    return out << elements;
}

// Helper function to print std::priority_queue
template<typename T, typename Container, typename Compare>
ostream& operator<<(ostream& out, std::priority_queue<T, Container, Compare> pq) {
    out << "{";
    while (!pq.empty()) {
        out << " " << pq.top();
        pq.pop();
    }
    out << " }";
    return out;
}

#ifdef DBG
void dbg_out() { cerr << endl; }

template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
    cerr << ' ' << H;
    dbg_out(T...);
}

#define dbg(...) cerr << #__VA_ARGS__ << ":", dbg_out(__VA_ARGS__);
#define dbg_array(a, n) cerr << #a << ": { "; for(int i = 0; i < n; i++) cerr << a[i] << " "; cerr << "}\n";
#else
#define dbg(...)
#define dbg_array(a, n)
#endif

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MX = 2e5+5;

int n, k;
vpi adj[MX];
vector<bool> dead(MX, 0);
int subtree_size[MX];

int get_subtree_size(int node, int parent = -1) {
    if (dead[node]) {
        subtree_size[node] = 0;
        return 0;
    }
	int &res = subtree_size[node];
	res = 1;
	for (pi i : adj[node]) {
		if (i.f == parent) { continue; }
		res += get_subtree_size(i.f, node);
	}
	return res;
}

int get_centroid(int node, int start, int parent = -1) {
    // if (dead[node]) assert(0);
	for (pi i : adj[node]) {
		if (i.f == parent) { continue; }

		if (subtree_size[i.f] * 2 > subtree_size[start]) { return get_centroid(i.f, start, node); }
	}
	return node;
}

array<int, 3> dist[MX]; // dist, length, child root
vi comp;
const int maxK = 1e6+5;
void calc_dist(int node, int depth, int par, int d, int root = -1) {
    dbg("calc_dist", node, depth, par, d, root, dead[node]);
    if (dead[node]) return;
    if (d > k) return;
    comp.pb(node);
    dist[node] = {d, depth, root};
    trav(u, adj[node]) {
        if (u.f == par) continue;
        int newRoot = root;
        if (root == -1) newRoot = u.f;
        calc_dist(u.f, depth+1, node, d+u.s, newRoot);
    }
}

int ans = MX;
vpi cnt[maxK];  // map from dist to pair of depth, childNode
void solve(int node) {
    if (dead[node]) return;
    get_subtree_size(node);
    int cent = get_centroid(node, node);
    dbg(node, cent);
    // dfs on cent and store all the lengths
    comp.clear();
    calc_dist(cent, 0, -1, 0);
    dbg(comp);
    // now two sum the component
    trav(v, comp) {
        int d = dist[v][0];
        cnt[d].clear();
        cnt[k-d].clear();
    }
    set<int> dists;
    trav(v, comp) {
        if (v == cent) continue;
        dbg(dist[v][0], dist[v][1], dist[v][2]);
        cnt[dist[v][0]].pb({dist[v][1], dist[v][2]});
        dists.insert(dist[v][0]);
    }
    trav(d, dists) {
        vpi tmp = {{MX, -1}, {MX, -1}}; // best and second best options
        // find the first two not from the same childNode
        trav(x, cnt[d]) {
            bool match = 0;
            F0R(i, 2) {
                if (tmp[i].s == x.s) {
                    ckmin(tmp[i].f, x.f);
                    match = 1;
                    break;
                }
            }
            if (!match) {
                // see if its better than best
                if (x.f < tmp[0].f) {
                    tmp[1] = tmp[0];
                    tmp[0] = x;
                } else if (x.f < tmp[1].f) {
                    tmp[1] = x;
                }
            }
            if (tmp[0].f > tmp[1].f) swap(tmp[0], tmp[1]);
        }
        if (tmp[1].s == -1) tmp.pop_back();
        cnt[d] = tmp;
        dbg(d, cnt[d]);
    }
    // now two sum on this
    trav(d, dists) {
        if (d == k) {
            // assert(sz(cnt[d]) > 0);
            ckmin(ans, cnt[d][0].f);
        }
        int rem = k-d;
        if (rem < 0) continue;
        if (!sz(cnt[rem])) continue;
        trav(x, cnt[d]) {
            trav(y, cnt[rem]) {
                if (x.s != y.s) {
                    ckmin(ans, x.f+y.f);
                }
            }
        }
    }
    dbg("marking dead", cent);
    dead[cent] = 1;
    trav(u, adj[cent]) {
        solve(u.f);
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N;
    k = K;
    F0R(i, N-1) {
        adj[H[i][0]].pb({H[i][1], L[i]});
        adj[H[i][1]].pb({H[i][0], L[i]});
    }
    solve(0);
    if (ans == MX) return -1;
    return ans;
}

// int main() {
//     ios_base::sync_with_stdio(false);
//     cin.tie(0); cout.tie(0);
//     int n, k; cin >> n >> k;
//     int H[n-1][2]; F0R(i, n-1) cin >> H[i][0] >> H[i][1];
//     int L[n-1]; F0R(i, n-1) cin >> L[i];
//     cout << best_path(n, k, H, L) << nl;
//     return 0;
// }

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 35420 KB Output is correct
2 Correct 7 ms 35420 KB Output is correct
3 Correct 7 ms 35420 KB Output is correct
4 Correct 7 ms 35420 KB Output is correct
5 Correct 7 ms 35400 KB Output is correct
6 Correct 7 ms 35420 KB Output is correct
7 Correct 7 ms 35432 KB Output is correct
8 Correct 7 ms 35416 KB Output is correct
9 Correct 8 ms 35444 KB Output is correct
10 Correct 7 ms 35396 KB Output is correct
11 Correct 9 ms 35420 KB Output is correct
12 Correct 7 ms 35416 KB Output is correct
13 Correct 7 ms 35420 KB Output is correct
14 Correct 7 ms 35692 KB Output is correct
15 Correct 7 ms 35420 KB Output is correct
16 Correct 7 ms 35420 KB Output is correct
17 Correct 7 ms 35672 KB Output is correct
18 Correct 7 ms 35420 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 35420 KB Output is correct
2 Correct 7 ms 35420 KB Output is correct
3 Correct 7 ms 35420 KB Output is correct
4 Correct 7 ms 35420 KB Output is correct
5 Correct 7 ms 35400 KB Output is correct
6 Correct 7 ms 35420 KB Output is correct
7 Correct 7 ms 35432 KB Output is correct
8 Correct 7 ms 35416 KB Output is correct
9 Correct 8 ms 35444 KB Output is correct
10 Correct 7 ms 35396 KB Output is correct
11 Correct 9 ms 35420 KB Output is correct
12 Correct 7 ms 35416 KB Output is correct
13 Correct 7 ms 35420 KB Output is correct
14 Correct 7 ms 35692 KB Output is correct
15 Correct 7 ms 35420 KB Output is correct
16 Correct 7 ms 35420 KB Output is correct
17 Correct 7 ms 35672 KB Output is correct
18 Correct 7 ms 35420 KB Output is correct
19 Correct 7 ms 35416 KB Output is correct
20 Correct 7 ms 35420 KB Output is correct
21 Correct 8 ms 35420 KB Output is correct
22 Correct 8 ms 35420 KB Output is correct
23 Correct 8 ms 35420 KB Output is correct
24 Correct 8 ms 35532 KB Output is correct
25 Correct 9 ms 35480 KB Output is correct
26 Correct 8 ms 35420 KB Output is correct
27 Correct 8 ms 35420 KB Output is correct
28 Correct 9 ms 35420 KB Output is correct
29 Correct 9 ms 35420 KB Output is correct
30 Correct 9 ms 35648 KB Output is correct
31 Correct 10 ms 35872 KB Output is correct
32 Correct 10 ms 35572 KB Output is correct
33 Correct 9 ms 35676 KB Output is correct
34 Correct 9 ms 35400 KB Output is correct
35 Correct 8 ms 35420 KB Output is correct
36 Correct 10 ms 35388 KB Output is correct
37 Correct 9 ms 35676 KB Output is correct
38 Correct 9 ms 35728 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 35420 KB Output is correct
2 Correct 7 ms 35420 KB Output is correct
3 Correct 7 ms 35420 KB Output is correct
4 Correct 7 ms 35420 KB Output is correct
5 Correct 7 ms 35400 KB Output is correct
6 Correct 7 ms 35420 KB Output is correct
7 Correct 7 ms 35432 KB Output is correct
8 Correct 7 ms 35416 KB Output is correct
9 Correct 8 ms 35444 KB Output is correct
10 Correct 7 ms 35396 KB Output is correct
11 Correct 9 ms 35420 KB Output is correct
12 Correct 7 ms 35416 KB Output is correct
13 Correct 7 ms 35420 KB Output is correct
14 Correct 7 ms 35692 KB Output is correct
15 Correct 7 ms 35420 KB Output is correct
16 Correct 7 ms 35420 KB Output is correct
17 Correct 7 ms 35672 KB Output is correct
18 Correct 7 ms 35420 KB Output is correct
19 Correct 134 ms 41516 KB Output is correct
20 Correct 134 ms 41476 KB Output is correct
21 Correct 135 ms 41968 KB Output is correct
22 Correct 146 ms 42524 KB Output is correct
23 Correct 79 ms 41548 KB Output is correct
24 Correct 63 ms 41460 KB Output is correct
25 Correct 113 ms 44044 KB Output is correct
26 Correct 89 ms 49620 KB Output is correct
27 Correct 159 ms 46716 KB Output is correct
28 Correct 198 ms 58068 KB Output is correct
29 Correct 196 ms 57468 KB Output is correct
30 Correct 150 ms 47452 KB Output is correct
31 Correct 150 ms 47504 KB Output is correct
32 Correct 165 ms 47328 KB Output is correct
33 Correct 202 ms 46372 KB Output is correct
34 Correct 135 ms 46492 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 35420 KB Output is correct
2 Correct 7 ms 35420 KB Output is correct
3 Correct 7 ms 35420 KB Output is correct
4 Correct 7 ms 35420 KB Output is correct
5 Correct 7 ms 35400 KB Output is correct
6 Correct 7 ms 35420 KB Output is correct
7 Correct 7 ms 35432 KB Output is correct
8 Correct 7 ms 35416 KB Output is correct
9 Correct 8 ms 35444 KB Output is correct
10 Correct 7 ms 35396 KB Output is correct
11 Correct 9 ms 35420 KB Output is correct
12 Correct 7 ms 35416 KB Output is correct
13 Correct 7 ms 35420 KB Output is correct
14 Correct 7 ms 35692 KB Output is correct
15 Correct 7 ms 35420 KB Output is correct
16 Correct 7 ms 35420 KB Output is correct
17 Correct 7 ms 35672 KB Output is correct
18 Correct 7 ms 35420 KB Output is correct
19 Correct 7 ms 35416 KB Output is correct
20 Correct 7 ms 35420 KB Output is correct
21 Correct 8 ms 35420 KB Output is correct
22 Correct 8 ms 35420 KB Output is correct
23 Correct 8 ms 35420 KB Output is correct
24 Correct 8 ms 35532 KB Output is correct
25 Correct 9 ms 35480 KB Output is correct
26 Correct 8 ms 35420 KB Output is correct
27 Correct 8 ms 35420 KB Output is correct
28 Correct 9 ms 35420 KB Output is correct
29 Correct 9 ms 35420 KB Output is correct
30 Correct 9 ms 35648 KB Output is correct
31 Correct 10 ms 35872 KB Output is correct
32 Correct 10 ms 35572 KB Output is correct
33 Correct 9 ms 35676 KB Output is correct
34 Correct 9 ms 35400 KB Output is correct
35 Correct 8 ms 35420 KB Output is correct
36 Correct 10 ms 35388 KB Output is correct
37 Correct 9 ms 35676 KB Output is correct
38 Correct 9 ms 35728 KB Output is correct
39 Correct 134 ms 41516 KB Output is correct
40 Correct 134 ms 41476 KB Output is correct
41 Correct 135 ms 41968 KB Output is correct
42 Correct 146 ms 42524 KB Output is correct
43 Correct 79 ms 41548 KB Output is correct
44 Correct 63 ms 41460 KB Output is correct
45 Correct 113 ms 44044 KB Output is correct
46 Correct 89 ms 49620 KB Output is correct
47 Correct 159 ms 46716 KB Output is correct
48 Correct 198 ms 58068 KB Output is correct
49 Correct 196 ms 57468 KB Output is correct
50 Correct 150 ms 47452 KB Output is correct
51 Correct 150 ms 47504 KB Output is correct
52 Correct 165 ms 47328 KB Output is correct
53 Correct 202 ms 46372 KB Output is correct
54 Correct 135 ms 46492 KB Output is correct
55 Correct 21 ms 36696 KB Output is correct
56 Correct 21 ms 35932 KB Output is correct
57 Correct 108 ms 43420 KB Output is correct
58 Correct 39 ms 44240 KB Output is correct
59 Correct 220 ms 58044 KB Output is correct
60 Correct 764 ms 86704 KB Output is correct
61 Correct 224 ms 47716 KB Output is correct
62 Correct 221 ms 50688 KB Output is correct
63 Correct 261 ms 50540 KB Output is correct
64 Correct 866 ms 63996 KB Output is correct
65 Correct 160 ms 48232 KB Output is correct
66 Correct 605 ms 59668 KB Output is correct
67 Correct 118 ms 52116 KB Output is correct
68 Correct 380 ms 60872 KB Output is correct
69 Correct 404 ms 58792 KB Output is correct
70 Correct 377 ms 60680 KB Output is correct