Submission #1132743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132743		WeIlIaN	City Mapping (NOI18_citymapping)	C++20	100 / 100	15 ms	5960 KiB

citymapping

#include <bits/stdc++.h>
#include "citymapping.h"
using namespace std;

#define MOD 1000000007
#define fir first
#define sec second
#define pushf push_front
#define pushb push_back
#define popf pop_front
#define popb pop_back
#define mp make_pair
#define all(a) a.begin(), a.end()

#define FOR(i, s, e) for(int i = s; i < e; i++)
#define RFOR(i, s, e) for(int i = e-1; i >= s; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
typedef vector<vc> vvc;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
typedef queue<int> qi;
typedef queue<ll> qll;
typedef queue<pii> qpii;
typedef queue<pll> qpll;
typedef deque<int> dqi;
typedef deque<ll> dqll;
typedef deque<pii> dqpii;
typedef deque<pll> dqpll;
typedef priority_queue<int> pqi;
typedef priority_queue<ll> pqll;
typedef priority_queue<pii> pqpii;
typedef priority_queue<pll> pqpll;
typedef priority_queue<int, vi, greater<int> > r_pqi;
typedef priority_queue<ll, vll, greater<ll> > r_pqll;
typedef priority_queue<pii, vpii, greater<pii> > r_pqpii;
typedef priority_queue<pll, vpll, greater<pll> > r_pqpll;

const int N = 1e3 + 5;

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

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

}

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[]){
    vi sr;
    for (int i = 2; i < n + 1; ++ i) sr.pushb(i);
    sort(all(sr), [&](int u, int v){
        return dist(1, u) < dist(1, v);
    });

    int cnt = 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.pushb(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].pushb(u);
        a[cnt] = r, b[cnt] = u, w[cnt] = d[1][u] - d[1][r];
        ++cnt;
    }
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 43 / 43