oj.uz

Submission #964021

# Submission time Handle Problem Language Result Execution time Memory
964021 2024-04-16T07:58:56 Z 12345678 City Mapping (NOI18_citymapping) C++17
100 / 100
 12 ms 1116 KB 
#include "citymapping.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

mt19937 rng(time(0));

const ll nx=1e3+5;

ll ds[nx];
ll hv[nx], l[nx], sz[nx], rt, pa[nx], w[nx], t;
vector<pair<ll, ll>> k, rnd;
vector<ll> d[nx];
map<pair<ll, ll>, ll> mp;

ll dfssz(ll u)
{
    sz[u]=1;
    for (auto v:d[u]) sz[u]+=dfssz(v);
    if (d[u].size()==1) hv[u]=d[u][0], l[u]=-1;
    else if (d[u].size()==2)
    {
        if (sz[d[u][0]]<sz[d[u][1]]) swap(d[u][0], d[u][1]);
        hv[u]=d[u][0];
        l[u]=d[u][1];
    }  
    return sz[u];
}

ll query(ll u, ll v)
{
    if (u>v) swap(u, v);
    if (mp.find({u, v})!=mp.end()) return mp[{u, v}];
    return mp[{u, v}]=get_distance(u, v);
}

void find_roads(int N, int Q, int A[], int B[], int W[]) {
    pair<ll, ll> mx;
    for (ll i=2; i<=N; i++) rnd.push_back({rng(), i});
    sort(rnd.begin(), rnd.end());
    for (ll i=0; i<min(400, N); i++) mx=max(mx, {query(1, rnd[i].second), rnd[i].second});
    rt=mx.second;
    for (ll i=1; i<=N; i++) if (i!=rt) ds[i]=query(rt, i), k.push_back({ds[i], i});
    sort(k.begin(), k.end());
    for (auto [_, u]:k)
    {
        for (ll i=1; i<=N; i++) hv[i]=l[i]=-1;
        dfssz(rt);
        ll tmp=rt;
        while (1)
        {
            while (hv[tmp]!=-1) tmp=hv[tmp];
            ll ld=query(rt, tmp)-((query(rt, tmp)+query(rt, u))-query(u, tmp))/2;
            while (ld!=0) ld-=w[tmp], tmp=pa[tmp];
            if (d[tmp].size()<2)
            {
                d[tmp].push_back(u), pa[u]=tmp, w[u]=query(u, tmp), A[t]=u, B[t]=tmp, W[t++]=query(u, tmp);
                break;
            }
            else tmp=l[tmp];
        } 
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 856 KB Correct: 2395 out of 500000 queries used.
2 Correct 7 ms 860 KB Correct: 3139 out of 500000 queries used.
3 Correct 8 ms 872 KB Correct: 5306 out of 500000 queries used.
4 Correct 10 ms 1116 KB Correct: 6515 out of 500000 queries used.
5 Correct 8 ms 860 KB Correct: 3328 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 856 KB Correct: 2395 out of 500000 queries used.
2 Correct 7 ms 860 KB Correct: 3139 out of 500000 queries used.
3 Correct 8 ms 872 KB Correct: 5306 out of 500000 queries used.
4 Correct 10 ms 1116 KB Correct: 6515 out of 500000 queries used.
5 Correct 8 ms 860 KB Correct: 3328 out of 500000 queries used.
6 Correct 8 ms 860 KB Correct: 2389 out of 500000 queries used.
7 Correct 8 ms 856 KB Correct: 2892 out of 500000 queries used.
8 Correct 8 ms 860 KB Correct: 5164 out of 500000 queries used.
9 Correct 9 ms 1052 KB Correct: 5997 out of 500000 queries used.
10 Correct 8 ms 860 KB Correct: 3317 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 860 KB Correct: 2378 out of 12000 queries used.
2 Correct 8 ms 888 KB Correct: 2386 out of 12000 queries used.
3 Correct 8 ms 860 KB Correct: 2397 out of 12000 queries used.
4 Correct 9 ms 1116 KB Correct: 2385 out of 12000 queries used.
5 Correct 8 ms 1016 KB Correct: 2377 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 860 KB Correct: 2378 out of 12000 queries used.
2 Correct 8 ms 888 KB Correct: 2386 out of 12000 queries used.
3 Correct 8 ms 860 KB Correct: 2397 out of 12000 queries used.
4 Correct 9 ms 1116 KB Correct: 2385 out of 12000 queries used.
5 Correct 8 ms 1016 KB Correct: 2377 out of 12000 queries used.
6 Correct 8 ms 860 KB Correct: 2394 out of 12000 queries used.
7 Correct 10 ms 860 KB Correct: 2388 out of 12000 queries used.
8 Correct 9 ms 1020 KB Correct: 2400 out of 12000 queries used.
9 Correct 8 ms 856 KB Correct: 2390 out of 12000 queries used.
10 Correct 8 ms 860 KB Correct: 2384 out of 12000 queries used.

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 856 KB Correct: 2395 out of 500000 queries used.
2 Correct 7 ms 860 KB Correct: 3139 out of 500000 queries used.
3 Correct 8 ms 872 KB Correct: 5306 out of 500000 queries used.
4 Correct 10 ms 1116 KB Correct: 6515 out of 500000 queries used.
5 Correct 8 ms 860 KB Correct: 3328 out of 500000 queries used.
6 Correct 8 ms 860 KB Correct: 2389 out of 500000 queries used.
7 Correct 8 ms 856 KB Correct: 2892 out of 500000 queries used.
8 Correct 8 ms 860 KB Correct: 5164 out of 500000 queries used.
9 Correct 9 ms 1052 KB Correct: 5997 out of 500000 queries used.
10 Correct 8 ms 860 KB Correct: 3317 out of 500000 queries used.
11 Correct 8 ms 860 KB Correct: 2378 out of 12000 queries used.
12 Correct 8 ms 888 KB Correct: 2386 out of 12000 queries used.
13 Correct 8 ms 860 KB Correct: 2397 out of 12000 queries used.
14 Correct 9 ms 1116 KB Correct: 2385 out of 12000 queries used.
15 Correct 8 ms 1016 KB Correct: 2377 out of 12000 queries used.
16 Correct 8 ms 860 KB Correct: 2394 out of 12000 queries used.
17 Correct 10 ms 860 KB Correct: 2388 out of 12000 queries used.
18 Correct 9 ms 1020 KB Correct: 2400 out of 12000 queries used.
19 Correct 8 ms 856 KB Correct: 2390 out of 12000 queries used.
20 Correct 8 ms 860 KB Correct: 2384 out of 12000 queries used.
21 Correct 8 ms 860 KB Correct: 2388 out of 25000 queries used.
22 Correct 8 ms 860 KB Correct: 2891 out of 25000 queries used.
23 Correct 8 ms 856 KB Correct: 2876 out of 25000 queries used.
24 Correct 8 ms 856 KB Correct: 2879 out of 25000 queries used.
25 Correct 8 ms 860 KB Correct: 5088 out of 25000 queries used.
26 Correct 9 ms 860 KB Correct: 4981 out of 25000 queries used.
27 Correct 8 ms 856 KB Correct: 4916 out of 25000 queries used.
28 Correct 8 ms 860 KB Correct: 5199 out of 25000 queries used.
29 Correct 8 ms 860 KB Correct: 5166 out of 25000 queries used.
30 Correct 8 ms 856 KB Correct: 5170 out of 25000 queries used.
31 Correct 10 ms 1116 KB Correct: 6058 out of 25000 queries used.
32 Correct 9 ms 892 KB Correct: 2389 out of 25000 queries used.
33 Correct 11 ms 1024 KB Correct: 5981 out of 25000 queries used.
34 Correct 8 ms 1116 KB Correct: 6052 out of 25000 queries used.
35 Correct 12 ms 1112 KB Correct: 5989 out of 25000 queries used.
36 Correct 9 ms 956 KB Correct: 6057 out of 25000 queries used.
37 Correct 8 ms 1112 KB Correct: 6040 out of 25000 queries used.
38 Correct 8 ms 1112 KB Correct: 6059 out of 25000 queries used.
39 Correct 8 ms 1112 KB Correct: 6003 out of 25000 queries used.
40 Correct 8 ms 1112 KB Correct: 6115 out of 25000 queries used.
41 Correct 8 ms 1036 KB Correct: 6034 out of 25000 queries used.
42 Correct 8 ms 1096 KB Correct: 6042 out of 25000 queries used.
43 Correct 8 ms 860 KB Correct: 2392 out of 25000 queries used.
44 Correct 8 ms 1112 KB Correct: 5981 out of 25000 queries used.
45 Correct 8 ms 1116 KB Correct: 5998 out of 25000 queries used.
46 Correct 9 ms 924 KB Correct: 5955 out of 25000 queries used.
47 Correct 8 ms 1116 KB Correct: 6046 out of 25000 queries used.
48 Correct 9 ms 1112 KB Correct: 6025 out of 25000 queries used.
49 Correct 10 ms 1116 KB Correct: 6007 out of 25000 queries used.
50 Correct 8 ms 1116 KB Correct: 6022 out of 25000 queries used.
51 Correct 8 ms 1012 KB Correct: 6014 out of 25000 queries used.
52 Correct 8 ms 1080 KB Correct: 6033 out of 25000 queries used.
53 Correct 8 ms 1048 KB Correct: 6031 out of 25000 queries used.
54 Correct 8 ms 932 KB Correct: 2895 out of 25000 queries used.
55 Correct 10 ms 1116 KB Correct: 6004 out of 25000 queries used.
56 Correct 9 ms 1112 KB Correct: 6002 out of 25000 queries used.
57 Correct 9 ms 1112 KB Correct: 6051 out of 25000 queries used.
58 Correct 9 ms 1116 KB Correct: 6014 out of 25000 queries used.
59 Correct 11 ms 1012 KB Correct: 6023 out of 25000 queries used.
60 Correct 9 ms 856 KB Correct: 3361 out of 25000 queries used.
61 Correct 8 ms 860 KB Correct: 3407 out of 25000 queries used.
62 Correct 11 ms 860 KB Correct: 3343 out of 25000 queries used.
63 Correct 9 ms 776 KB Correct: 3318 out of 25000 queries used.
64 Correct 8 ms 860 KB Correct: 3355 out of 25000 queries used.
65 Correct 8 ms 860 KB Correct: 2875 out of 25000 queries used.
66 Correct 9 ms 860 KB Correct: 3363 out of 25000 queries used.
67 Correct 8 ms 860 KB Correct: 2869 out of 25000 queries used.
68 Correct 8 ms 860 KB Correct: 2883 out of 25000 queries used.
69 Correct 9 ms 856 KB Correct: 2890 out of 25000 queries used.
70 Correct 8 ms 860 KB Correct: 2883 out of 25000 queries used.