oj.uz

Submission #384675

# Submission time Handle Problem Language Result Execution time Memory
384675 2021-04-02T04:33:49 Z thecodingwizard City Mapping (NOI18_citymapping) C++11
0 / 100
 15 ms 620 KB 
#include <bits/stdc++.h>
#include "citymapping.h"
using namespace std;

#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];
int sz[1010];
ii pa[1010];
vector<pair<int, ii>> edges;

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

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

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

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

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

    for (ii x : nodes) {
        //cout << "sovling for " << x.s << endl;
        solve(root, -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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 620 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 620 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 620 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 620 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 620 KB Reported list of edges differ from actual.
2 Halted 0 ms 0 KB -