oj.uz

Submission #1097003

# Submission time Handle Problem Language Result Execution time Memory
1097003 2024-10-05T17:11:31 Z thangdz2k7 City Mapping (NOI18_citymapping) C++17
100 / 100
 14 ms 6144 KB 
// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#include "citymapping.h"
#define pb push_back
#define fi first
#define se second
#define endl '\n'

using namespace std;
using ll = long long;
using ii = pair <int, int>;
using vi = vector <int>;

const int N = 1e3 + 5;
const int mod = 1e9 + 7;

void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}

ll d[N][N];

ll dist(int x, int y){
    if (x > y) swap(x, y);
    if (x == y) return 0;
    if (!d[x][y]) d[x][y] = get_distance(x, y);
    return d[x][y];

}

bool del[N];
int sz[N], heavy[N];
vi adj[N];

void dfs(int u){
    sz[u] = 1, heavy[u] = 0;
    for (int v : adj[u]) if (!del[v]){
        dfs(v); sz[u] += sz[v];
        if (sz[v] > sz[heavy[u]]) heavy[u] = v;
    }
}

void find_roads(int n, int q, int a[], int b[], int w[]){
    vector <int> sr;
    for (int i = 2; i < n + 1; ++ i) sr.pb(i);
    sort(sr.begin(), sr.end(), [&](int u, int v){
        return dist(1, u) < dist(1, v);
    });

    int nE = 0;
    for (int u : sr){
        int r = 1;
        for (int i = 1; i <= n; ++ i) del[i] = 0;
        while (true){
            dfs(r); vi path = {r};
            while (heavy[r]) r = heavy[r], path.pb(r);
            if (path.size() == 1) break;
            ll x = dist(1, path.back()) + dist(1, u) - dist(u, path.back()); x /= 2;
            for (int u : path) if (dist(1, u) == x) {
                r = u; //break;
            } else del[u] = 1;
        }
        adj[r].pb(u); a[nE] = r, b[nE] = u, w[nE] = d[1][u] - d[1][r],  ++ nE;
    }
}

//void solve(){
//
//}
//
//int main(){
//    if (fopen("pqh.inp", "r")){
//        freopen("pqh.inp", "r", stdin);
//        freopen("pqh.out", "w", stdout);
//    }
//    ios_base::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//
//    int t = 1; // cin >> t;
//    while (t --) solve();
//    return 0;
//}

Compilation message

citymapping.cpp:19:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void maxl(auto &a, auto b) {a = max(a, b);}
      |           ^~~~
citymapping.cpp:19:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void maxl(auto &a, auto b) {a = max(a, b);}
      |                    ^~~~
citymapping.cpp:20:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void minl(auto &a, auto b) {a = min(a, b);}
      |           ^~~~
citymapping.cpp:20:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void minl(auto &a, auto b) {a = min(a, b);}
      |                    ^~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4700 KB Correct: 2695 out of 500000 queries used.
2 Correct 9 ms 4188 KB Correct: 2428 out of 500000 queries used.
3 Correct 9 ms 5468 KB Correct: 4527 out of 500000 queries used.
4 Correct 8 ms 5628 KB Correct: 5523 out of 500000 queries used.
5 Correct 10 ms 4956 KB Correct: 3397 out of 500000 queries used.

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4700 KB Correct: 2695 out of 500000 queries used.
2 Correct 9 ms 4188 KB Correct: 2428 out of 500000 queries used.
3 Correct 9 ms 5468 KB Correct: 4527 out of 500000 queries used.
4 Correct 8 ms 5628 KB Correct: 5523 out of 500000 queries used.
5 Correct 10 ms 4956 KB Correct: 3397 out of 500000 queries used.
6 Correct 11 ms 3928 KB Correct: 2009 out of 500000 queries used.
7 Correct 9 ms 3676 KB Correct: 2063 out of 500000 queries used.
8 Correct 9 ms 5380 KB Correct: 4244 out of 500000 queries used.
9 Correct 9 ms 5884 KB Correct: 5089 out of 500000 queries used.
10 Correct 10 ms 4952 KB Correct: 3054 out of 500000 queries used.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3928 KB Correct: 2082 out of 12000 queries used.
2 Correct 12 ms 4184 KB Correct: 2321 out of 12000 queries used.
3 Correct 12 ms 4444 KB Correct: 2459 out of 12000 queries used.
4 Correct 11 ms 4352 KB Correct: 2466 out of 12000 queries used.
5 Correct 10 ms 4096 KB Correct: 2232 out of 12000 queries used.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3928 KB Correct: 2082 out of 12000 queries used.
2 Correct 12 ms 4184 KB Correct: 2321 out of 12000 queries used.
3 Correct 12 ms 4444 KB Correct: 2459 out of 12000 queries used.
4 Correct 11 ms 4352 KB Correct: 2466 out of 12000 queries used.
5 Correct 10 ms 4096 KB Correct: 2232 out of 12000 queries used.
6 Correct 12 ms 4552 KB Correct: 2473 out of 12000 queries used.
7 Correct 12 ms 4188 KB Correct: 2382 out of 12000 queries used.
8 Correct 11 ms 4140 KB Correct: 2207 out of 12000 queries used.
9 Correct 11 ms 4264 KB Correct: 2235 out of 12000 queries used.
10 Correct 11 ms 4188 KB Correct: 2302 out of 12000 queries used.

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4700 KB Correct: 2695 out of 500000 queries used.
2 Correct 9 ms 4188 KB Correct: 2428 out of 500000 queries used.
3 Correct 9 ms 5468 KB Correct: 4527 out of 500000 queries used.
4 Correct 8 ms 5628 KB Correct: 5523 out of 500000 queries used.
5 Correct 10 ms 4956 KB Correct: 3397 out of 500000 queries used.
6 Correct 11 ms 3928 KB Correct: 2009 out of 500000 queries used.
7 Correct 9 ms 3676 KB Correct: 2063 out of 500000 queries used.
8 Correct 9 ms 5380 KB Correct: 4244 out of 500000 queries used.
9 Correct 9 ms 5884 KB Correct: 5089 out of 500000 queries used.
10 Correct 10 ms 4952 KB Correct: 3054 out of 500000 queries used.
11 Correct 10 ms 3928 KB Correct: 2082 out of 12000 queries used.
12 Correct 12 ms 4184 KB Correct: 2321 out of 12000 queries used.
13 Correct 12 ms 4444 KB Correct: 2459 out of 12000 queries used.
14 Correct 11 ms 4352 KB Correct: 2466 out of 12000 queries used.
15 Correct 10 ms 4096 KB Correct: 2232 out of 12000 queries used.
16 Correct 12 ms 4552 KB Correct: 2473 out of 12000 queries used.
17 Correct 12 ms 4188 KB Correct: 2382 out of 12000 queries used.
18 Correct 11 ms 4140 KB Correct: 2207 out of 12000 queries used.
19 Correct 11 ms 4264 KB Correct: 2235 out of 12000 queries used.
20 Correct 11 ms 4188 KB Correct: 2302 out of 12000 queries used.
21 Correct 11 ms 4516 KB Correct: 2502 out of 25000 queries used.
22 Correct 9 ms 3324 KB Correct: 2071 out of 25000 queries used.
23 Correct 9 ms 3676 KB Correct: 2284 out of 25000 queries used.
24 Correct 9 ms 3420 KB Correct: 2036 out of 25000 queries used.
25 Correct 8 ms 5720 KB Correct: 4436 out of 25000 queries used.
26 Correct 8 ms 5468 KB Correct: 4358 out of 25000 queries used.
27 Correct 8 ms 5468 KB Correct: 4307 out of 25000 queries used.
28 Correct 8 ms 5732 KB Correct: 4417 out of 25000 queries used.
29 Correct 8 ms 5432 KB Correct: 4502 out of 25000 queries used.
30 Correct 8 ms 5468 KB Correct: 4442 out of 25000 queries used.
31 Correct 9 ms 5724 KB Correct: 5151 out of 25000 queries used.
32 Correct 10 ms 4188 KB Correct: 2223 out of 25000 queries used.
33 Correct 8 ms 6144 KB Correct: 5083 out of 25000 queries used.
34 Correct 9 ms 5468 KB Correct: 5158 out of 25000 queries used.
35 Correct 8 ms 5724 KB Correct: 5100 out of 25000 queries used.
36 Correct 8 ms 5664 KB Correct: 5118 out of 25000 queries used.
37 Correct 8 ms 5632 KB Correct: 5144 out of 25000 queries used.
38 Correct 8 ms 5724 KB Correct: 5102 out of 25000 queries used.
39 Correct 9 ms 5980 KB Correct: 5135 out of 25000 queries used.
40 Correct 12 ms 5588 KB Correct: 5168 out of 25000 queries used.
41 Correct 8 ms 5724 KB Correct: 5124 out of 25000 queries used.
42 Correct 8 ms 5212 KB Correct: 5203 out of 25000 queries used.
43 Correct 10 ms 3932 KB Correct: 2087 out of 25000 queries used.
44 Correct 8 ms 5556 KB Correct: 5116 out of 25000 queries used.
45 Correct 8 ms 5212 KB Correct: 5090 out of 25000 queries used.
46 Correct 9 ms 5724 KB Correct: 5068 out of 25000 queries used.
47 Correct 9 ms 5468 KB Correct: 5179 out of 25000 queries used.
48 Correct 9 ms 5544 KB Correct: 5135 out of 25000 queries used.
49 Correct 9 ms 5468 KB Correct: 5091 out of 25000 queries used.
50 Correct 8 ms 5632 KB Correct: 5105 out of 25000 queries used.
51 Correct 8 ms 5208 KB Correct: 5099 out of 25000 queries used.
52 Correct 8 ms 5464 KB Correct: 5128 out of 25000 queries used.
53 Correct 9 ms 5464 KB Correct: 5144 out of 25000 queries used.
54 Correct 9 ms 3164 KB Correct: 2333 out of 25000 queries used.
55 Correct 9 ms 5728 KB Correct: 5196 out of 25000 queries used.
56 Correct 14 ms 5632 KB Correct: 5141 out of 25000 queries used.
57 Correct 8 ms 5788 KB Correct: 5125 out of 25000 queries used.
58 Correct 8 ms 5428 KB Correct: 5115 out of 25000 queries used.
59 Correct 9 ms 5508 KB Correct: 5104 out of 25000 queries used.
60 Correct 10 ms 4420 KB Correct: 3041 out of 25000 queries used.
61 Correct 10 ms 4868 KB Correct: 3317 out of 25000 queries used.
62 Correct 9 ms 4444 KB Correct: 2917 out of 25000 queries used.
63 Correct 10 ms 4700 KB Correct: 3317 out of 25000 queries used.
64 Correct 10 ms 5124 KB Correct: 3103 out of 25000 queries used.
65 Correct 9 ms 2652 KB Correct: 2067 out of 25000 queries used.
66 Correct 9 ms 4800 KB Correct: 3228 out of 25000 queries used.
67 Correct 9 ms 3800 KB Correct: 2018 out of 25000 queries used.
68 Correct 10 ms 3420 KB Correct: 2394 out of 25000 queries used.
69 Correct 10 ms 4352 KB Correct: 2451 out of 25000 queries used.
70 Correct 11 ms 3420 KB Correct: 2414 out of 25000 queries used.