oj.uz

Submission #384690

# Submission time Handle Problem Language Result Execution time Memory
384690 2021-04-02T05:07:43 Z thecodingwizard City Mapping (NOI18_citymapping) C++11
100 / 100
 14 ms 768 KB 
#include <bits/stdc++.h>
#include "citymapping.h"
using namespace std;

using ll = long long;
#define ii pair<int, int>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

vector<ii> adj[1010];
ll sz[1010];
ii pa[1010];
vector<pair<int, ii>> edges;

ll dfsSize(int u, int a1, int a2) {
    sz[u] = 1;
    for (ii v : adj[u]) {
        if (v.f == a1 || v.f == a2) continue;
        sz[u] += dfsSize(v.f, a1, a2);
    }
    return sz[u];
}

pair<int, ll> getEndpoint(int u, int a1, int a2) {
    int best = -1;
    ll bestDist = 0;
    for (ii v : adj[u]) {
        if (v.f == a1 || v.f == a2) continue;
        if (best == -1 || sz[best] < sz[v.f]) {
            best = v.f;
            bestDist = v.s;
        }
    }
    if (best == -1) return mp(u, 0);
    pair<int, ll> ret = getEndpoint(best, a1, a2);
    ret.s += bestDist;
    return ret;
}

void solve(int root, int avoid, int avoid2, int target, ll rootToTarget) {
    dfsSize(root, avoid, avoid2);
    pair<int, ll> endpoint = getEndpoint(root, avoid, avoid2);
    //cout << root << " " << endpoint.f << endl;
    if (endpoint.f == root) {
        edges.pb(mp(rootToTarget, mp(root, target)));
        adj[root].pb(mp(target, rootToTarget));
        pa[target] = mp(root, rootToTarget);
        //cout << "attaching " << target << " to " << root << " with weight " << rootToTarget << endl;
    } else {
        ll d = (rootToTarget + get_distance(endpoint.f, target) - endpoint.s) / 2;
        int prevNode = -1;
        int node = endpoint.f;
        ll nodeDist = endpoint.s;
        while (nodeDist > rootToTarget - d) {
            assert(pa[node].f != -1);
            nodeDist -= pa[node].s;
            prevNode = node;
            node = pa[node].f;
        }
        assert(nodeDist == rootToTarget - d);
        solve(node, prevNode, avoid, target, d);
    }
}

void find_roads(int N, int Q, int A[], int B[], int W[]) {
    int root = 1;
    pa[1] = mp(-1, -1);

    vector<pair<ll, int>> nodes;
    for (int i = 2; i <= N; i++) {
        nodes.pb(mp(get_distance(root, i), i));
    }
    sort(all(nodes));

    for (pair<ll, int> x : nodes) {
        //cout << "sovling for " << x.s << endl;
        solve(root, -1, -1, x.s, x.f);
    }

    for (int i = 0; i < N-1; i++) {
        A[i] = edges[i].s.f;
        B[i] = edges[i].s.s;
        W[i] = edges[i].f;
    }

	return;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 620 KB Correct: 2691 out of 500000 queries used.
2 Correct 13 ms 620 KB Correct: 2421 out of 500000 queries used.
3 Correct 10 ms 492 KB Correct: 4517 out of 500000 queries used.
4 Correct 10 ms 492 KB Correct: 5567 out of 500000 queries used.
5 Correct 14 ms 620 KB Correct: 3387 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 620 KB Correct: 2691 out of 500000 queries used.
2 Correct 13 ms 620 KB Correct: 2421 out of 500000 queries used.
3 Correct 10 ms 492 KB Correct: 4517 out of 500000 queries used.
4 Correct 10 ms 492 KB Correct: 5567 out of 500000 queries used.
5 Correct 14 ms 620 KB Correct: 3387 out of 500000 queries used.
6 Correct 14 ms 748 KB Correct: 2009 out of 500000 queries used.
7 Correct 11 ms 620 KB Correct: 2063 out of 500000 queries used.
8 Correct 10 ms 620 KB Correct: 4244 out of 500000 queries used.
9 Correct 10 ms 620 KB Correct: 5089 out of 500000 queries used.
10 Correct 12 ms 620 KB Correct: 3054 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 620 KB Correct: 2086 out of 12000 queries used.
2 Correct 12 ms 620 KB Correct: 2304 out of 12000 queries used.
3 Correct 14 ms 620 KB Correct: 2457 out of 12000 queries used.
4 Correct 14 ms 620 KB Correct: 2470 out of 12000 queries used.
5 Correct 12 ms 620 KB Correct: 2240 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 620 KB Correct: 2086 out of 12000 queries used.
2 Correct 12 ms 620 KB Correct: 2304 out of 12000 queries used.
3 Correct 14 ms 620 KB Correct: 2457 out of 12000 queries used.
4 Correct 14 ms 620 KB Correct: 2470 out of 12000 queries used.
5 Correct 12 ms 620 KB Correct: 2240 out of 12000 queries used.
6 Correct 13 ms 748 KB Correct: 2473 out of 12000 queries used.
7 Correct 13 ms 620 KB Correct: 2382 out of 12000 queries used.
8 Correct 12 ms 620 KB Correct: 2207 out of 12000 queries used.
9 Correct 12 ms 620 KB Correct: 2235 out of 12000 queries used.
10 Correct 12 ms 620 KB Correct: 2302 out of 12000 queries used.

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 620 KB Correct: 2691 out of 500000 queries used.
2 Correct 13 ms 620 KB Correct: 2421 out of 500000 queries used.
3 Correct 10 ms 492 KB Correct: 4517 out of 500000 queries used.
4 Correct 10 ms 492 KB Correct: 5567 out of 500000 queries used.
5 Correct 14 ms 620 KB Correct: 3387 out of 500000 queries used.
6 Correct 14 ms 748 KB Correct: 2009 out of 500000 queries used.
7 Correct 11 ms 620 KB Correct: 2063 out of 500000 queries used.
8 Correct 10 ms 620 KB Correct: 4244 out of 500000 queries used.
9 Correct 10 ms 620 KB Correct: 5089 out of 500000 queries used.
10 Correct 12 ms 620 KB Correct: 3054 out of 500000 queries used.
11 Correct 12 ms 620 KB Correct: 2086 out of 12000 queries used.
12 Correct 12 ms 620 KB Correct: 2304 out of 12000 queries used.
13 Correct 14 ms 620 KB Correct: 2457 out of 12000 queries used.
14 Correct 14 ms 620 KB Correct: 2470 out of 12000 queries used.
15 Correct 12 ms 620 KB Correct: 2240 out of 12000 queries used.
16 Correct 13 ms 748 KB Correct: 2473 out of 12000 queries used.
17 Correct 13 ms 620 KB Correct: 2382 out of 12000 queries used.
18 Correct 12 ms 620 KB Correct: 2207 out of 12000 queries used.
19 Correct 12 ms 620 KB Correct: 2235 out of 12000 queries used.
20 Correct 12 ms 620 KB Correct: 2302 out of 12000 queries used.
21 Correct 14 ms 620 KB Correct: 2502 out of 25000 queries used.
22 Correct 13 ms 640 KB Correct: 2071 out of 25000 queries used.
23 Correct 12 ms 620 KB Correct: 2284 out of 25000 queries used.
24 Correct 13 ms 620 KB Correct: 2036 out of 25000 queries used.
25 Correct 11 ms 620 KB Correct: 4436 out of 25000 queries used.
26 Correct 11 ms 620 KB Correct: 4358 out of 25000 queries used.
27 Correct 13 ms 748 KB Correct: 4307 out of 25000 queries used.
28 Correct 10 ms 620 KB Correct: 4417 out of 25000 queries used.
29 Correct 11 ms 620 KB Correct: 4502 out of 25000 queries used.
30 Correct 11 ms 620 KB Correct: 4442 out of 25000 queries used.
31 Correct 11 ms 620 KB Correct: 5151 out of 25000 queries used.
32 Correct 12 ms 620 KB Correct: 2223 out of 25000 queries used.
33 Correct 11 ms 620 KB Correct: 5083 out of 25000 queries used.
34 Correct 11 ms 620 KB Correct: 5158 out of 25000 queries used.
35 Correct 10 ms 620 KB Correct: 5100 out of 25000 queries used.
36 Correct 10 ms 620 KB Correct: 5118 out of 25000 queries used.
37 Correct 11 ms 620 KB Correct: 5144 out of 25000 queries used.
38 Correct 12 ms 620 KB Correct: 5102 out of 25000 queries used.
39 Correct 11 ms 620 KB Correct: 5135 out of 25000 queries used.
40 Correct 12 ms 620 KB Correct: 5168 out of 25000 queries used.
41 Correct 11 ms 768 KB Correct: 5124 out of 25000 queries used.
42 Correct 10 ms 620 KB Correct: 5203 out of 25000 queries used.
43 Correct 12 ms 620 KB Correct: 2087 out of 25000 queries used.
44 Correct 10 ms 620 KB Correct: 5116 out of 25000 queries used.
45 Correct 10 ms 620 KB Correct: 5090 out of 25000 queries used.
46 Correct 10 ms 620 KB Correct: 5068 out of 25000 queries used.
47 Correct 11 ms 620 KB Correct: 5179 out of 25000 queries used.
48 Correct 11 ms 620 KB Correct: 5135 out of 25000 queries used.
49 Correct 10 ms 620 KB Correct: 5091 out of 25000 queries used.
50 Correct 11 ms 620 KB Correct: 5105 out of 25000 queries used.
51 Correct 11 ms 620 KB Correct: 5099 out of 25000 queries used.
52 Correct 10 ms 620 KB Correct: 5128 out of 25000 queries used.
53 Correct 10 ms 620 KB Correct: 5144 out of 25000 queries used.
54 Correct 12 ms 620 KB Correct: 2333 out of 25000 queries used.
55 Correct 11 ms 620 KB Correct: 5196 out of 25000 queries used.
56 Correct 11 ms 620 KB Correct: 5141 out of 25000 queries used.
57 Correct 10 ms 620 KB Correct: 5125 out of 25000 queries used.
58 Correct 11 ms 620 KB Correct: 5115 out of 25000 queries used.
59 Correct 10 ms 620 KB Correct: 5104 out of 25000 queries used.
60 Correct 11 ms 620 KB Correct: 3041 out of 25000 queries used.
61 Correct 12 ms 620 KB Correct: 3317 out of 25000 queries used.
62 Correct 11 ms 620 KB Correct: 2917 out of 25000 queries used.
63 Correct 12 ms 620 KB Correct: 3317 out of 25000 queries used.
64 Correct 11 ms 620 KB Correct: 3103 out of 25000 queries used.
65 Correct 13 ms 620 KB Correct: 2067 out of 25000 queries used.
66 Correct 12 ms 620 KB Correct: 3228 out of 25000 queries used.
67 Correct 12 ms 620 KB Correct: 2018 out of 25000 queries used.
68 Correct 13 ms 620 KB Correct: 2394 out of 25000 queries used.
69 Correct 13 ms 620 KB Correct: 2451 out of 25000 queries used.
70 Correct 14 ms 620 KB Correct: 2414 out of 25000 queries used.