oj.uz

답안 #209488

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
209488 2020-03-14T11:17:18 Z Alexa2001 City Mapping (NOI18_citymapping) C++17
100 / 100
 28 ms 8312 KB 
#include "citymapping.h"
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1005;
typedef long long ll;

int nr = 0, root, n, sz[Nmax], up[Nmax], where[Nmax], last[Nmax], crt_chain;
ll dist[Nmax][Nmax];
vector<int> v[Nmax];

mt19937 mt(time(0));

int get_rand(int x, int y)
{
    return uniform_int_distribution<int> (x, y) (mt);
}

ll get_dist(int x, int y)
{
    if(x == y) return 0;
    if(dist[x][y]) return dist[x][y];
    return dist[x][y] = dist[y][x] = get_distance(x, y);
}

void add_edge(int V[], int U[], int cost[], int x, int y)
{
    if(dist[root][x] > dist[root][y]) swap(x, y);

    V[nr] = x;
    U[nr] = y;
    cost[nr] = dist[root][y] - dist[root][x];
    v[x].push_back(y);
    up[y] = x;

    ++nr;
}

int get_lca(int x, int y)
{
    ll D = (get_dist(root, x) + get_dist(root, y) - get_dist(x, y)) / 2;

    while(dist[root][x] != D)
        x = up[x];
    return x;
}

void dfs0(int node)
{
    sz[node] = 1;

    for(auto it : v[node])
    {
        dfs0(it);
        sz[node] += sz[it];
    }

    sort(v[node].begin(), v[node].end(), [](int x, int y) {return sz[x] > sz[y];});
}

void hp(int node)
{
    where[node] = crt_chain;

    if(v[node].empty())
    {
        last[crt_chain] = node;
        return;
    }

    hp(v[node][0]);

    for(int i=1; i<v[node].size(); ++i)
    {
        ++crt_chain;
        hp(v[node][i]);
    }
}

void process(int node, int V[], int U[], int cost[])
{
    dfs0(root);
    crt_chain = 1;
    hp(root);

    int x = last[1];

    while(1)
    {
        int lca = get_lca(x, node);

        if(lca == x)
        {
            add_edge(V, U, cost, x, node);
            return;
        }

        if(lca == root)
        {
            if(v[root].size() == 1)
            {
                add_edge(V, U, cost, root, node);
                return;
            }

            if(v[root].size() == 2)
            {
                if(where[x] == 1)
                {
                    x = last[where[v[root][1]]];
                    continue;
                }
                else
                {
                    add_edge(V, U, cost, root, node);
                    return;
                }
            }

            if(v[root].size() == 3)
            {
                if(where[x] == 1)
                {
                    x = last[where[v[root][1]]];
                    continue;
                }
                else
                {
                    x = last[where[v[root][2]]];
                    continue;
                }
            }
        }

        if(v[lca].size() == 1)
        {
            add_edge(V, U, cost, lca, node);
            return;
        }
        else if(v[lca].size() == 2)
            x = last[where[v[lca][1]]];
    }
}

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

    root = get_rand(1, n);
    int i;
    for(i=1; i<=n; ++i) get_dist(root, i);

    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 1);
    sort(ord.begin(), ord.end(), [](int x, int y) {return dist[root][x] < dist[root][y]; });

    for(auto it : ord)
        if(it != root)
            process(it, A, B, W);
}

Compilation message

citymapping.cpp: In function 'void hp(int)':
citymapping.cpp:74:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<v[node].size(); ++i)
                  ~^~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 7800 KB Correct: 2335 out of 500000 queries used.
2 Correct 21 ms 7676 KB Correct: 2490 out of 500000 queries used.
3 Correct 24 ms 8184 KB Correct: 4611 out of 500000 queries used.
4 Correct 22 ms 8312 KB Correct: 5574 out of 500000 queries used.
5 Correct 25 ms 7904 KB Correct: 2947 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 7800 KB Correct: 2335 out of 500000 queries used.
2 Correct 21 ms 7676 KB Correct: 2490 out of 500000 queries used.
3 Correct 24 ms 8184 KB Correct: 4611 out of 500000 queries used.
4 Correct 22 ms 8312 KB Correct: 5574 out of 500000 queries used.
5 Correct 25 ms 7904 KB Correct: 2947 out of 500000 queries used.
6 Correct 23 ms 7800 KB Correct: 2219 out of 500000 queries used.
7 Correct 24 ms 7928 KB Correct: 2363 out of 500000 queries used.
8 Correct 25 ms 8184 KB Correct: 4320 out of 500000 queries used.
9 Correct 23 ms 8184 KB Correct: 5141 out of 500000 queries used.
10 Correct 28 ms 8056 KB Correct: 3294 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 7672 KB Correct: 2342 out of 12000 queries used.
2 Correct 23 ms 7676 KB Correct: 2195 out of 12000 queries used.
3 Correct 24 ms 7800 KB Correct: 2538 out of 12000 queries used.
4 Correct 23 ms 7672 KB Correct: 2307 out of 12000 queries used.
5 Correct 22 ms 7548 KB Correct: 2069 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 7672 KB Correct: 2342 out of 12000 queries used.
2 Correct 23 ms 7676 KB Correct: 2195 out of 12000 queries used.
3 Correct 24 ms 7800 KB Correct: 2538 out of 12000 queries used.
4 Correct 23 ms 7672 KB Correct: 2307 out of 12000 queries used.
5 Correct 22 ms 7548 KB Correct: 2069 out of 12000 queries used.
6 Correct 27 ms 7544 KB Correct: 2111 out of 12000 queries used.
7 Correct 23 ms 7800 KB Correct: 2378 out of 12000 queries used.
8 Correct 22 ms 7672 KB Correct: 2211 out of 12000 queries used.
9 Correct 23 ms 7672 KB Correct: 2214 out of 12000 queries used.
10 Correct 25 ms 7800 KB Correct: 2447 out of 12000 queries used.

Subtask #5
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 7800 KB Correct: 2335 out of 500000 queries used.
2 Correct 21 ms 7676 KB Correct: 2490 out of 500000 queries used.
3 Correct 24 ms 8184 KB Correct: 4611 out of 500000 queries used.
4 Correct 22 ms 8312 KB Correct: 5574 out of 500000 queries used.
5 Correct 25 ms 7904 KB Correct: 2947 out of 500000 queries used.
6 Correct 23 ms 7800 KB Correct: 2219 out of 500000 queries used.
7 Correct 24 ms 7928 KB Correct: 2363 out of 500000 queries used.
8 Correct 25 ms 8184 KB Correct: 4320 out of 500000 queries used.
9 Correct 23 ms 8184 KB Correct: 5141 out of 500000 queries used.
10 Correct 28 ms 8056 KB Correct: 3294 out of 500000 queries used.
11 Correct 24 ms 7672 KB Correct: 2342 out of 12000 queries used.
12 Correct 23 ms 7676 KB Correct: 2195 out of 12000 queries used.
13 Correct 24 ms 7800 KB Correct: 2538 out of 12000 queries used.
14 Correct 23 ms 7672 KB Correct: 2307 out of 12000 queries used.
15 Correct 22 ms 7548 KB Correct: 2069 out of 12000 queries used.
16 Correct 27 ms 7544 KB Correct: 2111 out of 12000 queries used.
17 Correct 23 ms 7800 KB Correct: 2378 out of 12000 queries used.
18 Correct 22 ms 7672 KB Correct: 2211 out of 12000 queries used.
19 Correct 23 ms 7672 KB Correct: 2214 out of 12000 queries used.
20 Correct 25 ms 7800 KB Correct: 2447 out of 12000 queries used.
21 Correct 23 ms 7672 KB Correct: 2242 out of 25000 queries used.
22 Correct 24 ms 7288 KB Correct: 2294 out of 25000 queries used.
23 Correct 22 ms 6776 KB Correct: 2115 out of 25000 queries used.
24 Correct 24 ms 6776 KB Correct: 2207 out of 25000 queries used.
25 Correct 25 ms 8184 KB Correct: 4376 out of 25000 queries used.
26 Correct 25 ms 8184 KB Correct: 4440 out of 25000 queries used.
27 Correct 25 ms 8184 KB Correct: 4233 out of 25000 queries used.
28 Correct 24 ms 8056 KB Correct: 4592 out of 25000 queries used.
29 Correct 25 ms 8184 KB Correct: 4293 out of 25000 queries used.
30 Correct 25 ms 8056 KB Correct: 4375 out of 25000 queries used.
31 Correct 23 ms 8312 KB Correct: 5185 out of 25000 queries used.
32 Correct 24 ms 7544 KB Correct: 2178 out of 25000 queries used.
33 Correct 24 ms 8184 KB Correct: 5100 out of 25000 queries used.
34 Correct 27 ms 8056 KB Correct: 5157 out of 25000 queries used.
35 Correct 24 ms 8312 KB Correct: 5135 out of 25000 queries used.
36 Correct 24 ms 8184 KB Correct: 5139 out of 25000 queries used.
37 Correct 23 ms 8184 KB Correct: 5154 out of 25000 queries used.
38 Correct 22 ms 8184 KB Correct: 5153 out of 25000 queries used.
39 Correct 23 ms 8312 KB Correct: 5113 out of 25000 queries used.
40 Correct 24 ms 8312 KB Correct: 5195 out of 25000 queries used.
41 Correct 24 ms 8312 KB Correct: 5179 out of 25000 queries used.
42 Correct 23 ms 8312 KB Correct: 5136 out of 25000 queries used.
43 Correct 23 ms 7800 KB Correct: 2159 out of 25000 queries used.
44 Correct 22 ms 8184 KB Correct: 5079 out of 25000 queries used.
45 Correct 23 ms 8184 KB Correct: 5099 out of 25000 queries used.
46 Correct 23 ms 8184 KB Correct: 5081 out of 25000 queries used.
47 Correct 23 ms 8272 KB Correct: 5146 out of 25000 queries used.
48 Correct 24 ms 8312 KB Correct: 5132 out of 25000 queries used.
49 Correct 24 ms 8184 KB Correct: 5109 out of 25000 queries used.
50 Correct 23 ms 8184 KB Correct: 5129 out of 25000 queries used.
51 Correct 24 ms 8184 KB Correct: 5114 out of 25000 queries used.
52 Correct 24 ms 8312 KB Correct: 5127 out of 25000 queries used.
53 Correct 24 ms 8312 KB Correct: 5130 out of 25000 queries used.
54 Correct 24 ms 6776 KB Correct: 2005 out of 25000 queries used.
55 Correct 23 ms 8312 KB Correct: 5121 out of 25000 queries used.
56 Correct 23 ms 8188 KB Correct: 5132 out of 25000 queries used.
57 Correct 25 ms 8312 KB Correct: 5177 out of 25000 queries used.
58 Correct 23 ms 8184 KB Correct: 5123 out of 25000 queries used.
59 Correct 23 ms 8184 KB Correct: 5124 out of 25000 queries used.
60 Correct 26 ms 7800 KB Correct: 3056 out of 25000 queries used.
61 Correct 25 ms 7928 KB Correct: 2951 out of 25000 queries used.
62 Correct 26 ms 7928 KB Correct: 3074 out of 25000 queries used.
63 Correct 27 ms 8056 KB Correct: 3096 out of 25000 queries used.
64 Correct 26 ms 7928 KB Correct: 2931 out of 25000 queries used.
65 Correct 24 ms 7800 KB Correct: 2235 out of 25000 queries used.
66 Correct 25 ms 7800 KB Correct: 3102 out of 25000 queries used.
67 Correct 25 ms 6904 KB Correct: 2247 out of 25000 queries used.
68 Correct 24 ms 7544 KB Correct: 2327 out of 25000 queries used.
69 Correct 25 ms 7032 KB Correct: 2317 out of 25000 queries used.
70 Correct 23 ms 7288 KB Correct: 2062 out of 25000 queries used.