oj.uz

Submission #1077983

# Submission time Handle Problem Language Result Execution time Memory
1077983 2024-08-27T11:24:26 Z Sorting Factories (JOI14_factories) C++17
100 / 100
 7983 ms 170052 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <iomanip>
#include <queue>
#include <stack>
#include <numeric>
#include <cassert>
#include <cmath>
#include <random>
#include <ctime>
#include <chrono>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)x.size())
#define rep(i, a, b) for(int i = a; i < b; ++i)

template <typename T>
void remove_duplicates(vector<T> &v){
    sort(all(v));
    v.resize(unique(all(v)) - v.begin());
}

template <typename T> void chmin(T &a, T b){ a = (b < a) ? b : a; }
template <typename T> void chmax(T &a, T b){ a = (b > a) ? b : a; }

template<class T>
struct RMQ {
	vector<vector<T>> jmp;
    RMQ(){}
	RMQ(const vector<T>& V) : jmp(1, V) {
		for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
			jmp.emplace_back(sz(V) - pw * 2 + 1);
			rep(j,0,sz(jmp[k]))
				jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
		}
	}
	T query(int a, int b) {
		// assert(a < b); // or return inf if a == b
		int dep = 31 - __builtin_clz(b - a);
		return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
	}
};

struct LCA {
	int T = 0;
	vi time, path, ret;
	RMQ<int> rmq;

    LCA(){}
	LCA(vector<vi>& C) : time(sz(C)), rmq((dfs(C,0,-1), ret)) {}
	void dfs(vector<vi>& C, int v, int par) {
		time[v] = T++;
		for (int y : C[v]) if (y != par) {
			path.push_back(v), ret.push_back(time[v]);
			dfs(C, y, v);
		}
	}

	int lca(int a, int b) {
		if (a == b) return a;
		tie(a, b) = minmax(time[a], time[b]);
		return path[rmq.query(a, b)];
	}
	//dist(a,b){return depth[a] + depth[b] - 2*depth[lca(a,b)];}
} lca;

const int N = 5e5 + 3;

int n, sz[N];
vector<pii> adj[N];
bool vis[N];

int cen_par[N];

ll depth[N];

ll get_dist(int a, int b){
    int l = lca.lca(a, b);
    return depth[a] + depth[b] - 2 * depth[l];
}

void dfs_depth(int u, int par = -1){
    for(auto [to, w]: adj[u]){
        if(to == par) continue;
        depth[to] = depth[u] + w;
        dfs_depth(to, u);
    }
}

void dfs_sz(int u, int par = -1){
    sz[u] = 1;
    for(auto [to, w]: adj[u]){
        if(vis[to] || to == par) continue;
        dfs_sz(to, u);
        sz[u] += sz[to];
    }
}

int find_centroid(int u, int sz_root, int par = -1){
    for(auto [to, w]: adj[u]){
        if(to == par || vis[to]) continue;
        if(sz[to] >= sz_root / 2) return find_centroid(to, sz_root, u);
    }
    return u;
}

void decompose(int u, int par = -1){
    dfs_sz(u);
    int cen = find_centroid(u, sz[u]);

    cen_par[cen] = par;
    vis[cen] = true;

    for(auto [to, w]: adj[cen]){
        if(vis[to]) continue;
        decompose(to, cen);
    }
}

void Init(int _n, int *a, int *b, int *d){
    n = _n;

    vector<vi> adj2(n + 1);
    for(int i = 0; i < n - 1; ++i){
        adj[a[i]].push_back({b[i], d[i]});
        adj[b[i]].push_back({a[i], d[i]});
        adj2[a[i]].push_back(b[i]);
        adj2[b[i]].push_back(a[i]);
    }

    lca = LCA(adj2);

    decompose(0);

    // for(int i = 0; i < n; ++i){
        // cout << "anc of " << i << ": ";
        // for(int x: anc[i])
            // cout << x << " ";
        // cout << endl;
    // }

    dfs_depth(0);
}

const ll INF = 1e18;
ll Query(int s, int x[], int t, int y[]){
    unordered_map<int, ll> mn;
    for(int i = 0; i < s; ++i){
        int v = x[i];
        int a = v;

        while(a != -1){
            if(!mn.count(a)) mn[a] = INF;
            chmin(mn[a], get_dist(a, v));
            a = cen_par[a];
        }
    }
    // cout << "x" << endl;

    ll ans = INF;
    for(int i = 0; i < t; ++i){
        int v = y[i];
        int a = v;

        while(a != -1){
            if(!mn.count(a)){
                a = cen_par[a];
                continue;
            }
            chmin(ans, mn[a] + get_dist(a, v));
            a = cen_par[a];
        }
    }
    // cout << "y" << endl;

    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12636 KB Output is correct
2 Correct 637 ms 30708 KB Output is correct
3 Correct 833 ms 30388 KB Output is correct
4 Correct 621 ms 30544 KB Output is correct
5 Correct 897 ms 30732 KB Output is correct
6 Correct 240 ms 30556 KB Output is correct
7 Correct 842 ms 30464 KB Output is correct
8 Correct 823 ms 30576 KB Output is correct
9 Correct 886 ms 30700 KB Output is correct
10 Correct 262 ms 30544 KB Output is correct
11 Correct 902 ms 30548 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12380 KB Output is correct
2 Correct 1895 ms 137748 KB Output is correct
3 Correct 3321 ms 139620 KB Output is correct
4 Correct 600 ms 139964 KB Output is correct
5 Correct 4161 ms 167820 KB Output is correct
6 Correct 2839 ms 140616 KB Output is correct
7 Correct 1996 ms 54456 KB Output is correct
8 Correct 343 ms 54644 KB Output is correct
9 Correct 2237 ms 57800 KB Output is correct
10 Correct 1907 ms 54724 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12636 KB Output is correct
2 Correct 637 ms 30708 KB Output is correct
3 Correct 833 ms 30388 KB Output is correct
4 Correct 621 ms 30544 KB Output is correct
5 Correct 897 ms 30732 KB Output is correct
6 Correct 240 ms 30556 KB Output is correct
7 Correct 842 ms 30464 KB Output is correct
8 Correct 823 ms 30576 KB Output is correct
9 Correct 886 ms 30700 KB Output is correct
10 Correct 262 ms 30544 KB Output is correct
11 Correct 902 ms 30548 KB Output is correct
12 Correct 7 ms 12380 KB Output is correct
13 Correct 1895 ms 137748 KB Output is correct
14 Correct 3321 ms 139620 KB Output is correct
15 Correct 600 ms 139964 KB Output is correct
16 Correct 4161 ms 167820 KB Output is correct
17 Correct 2839 ms 140616 KB Output is correct
18 Correct 1996 ms 54456 KB Output is correct
19 Correct 343 ms 54644 KB Output is correct
20 Correct 2237 ms 57800 KB Output is correct
21 Correct 1907 ms 54724 KB Output is correct
22 Correct 3624 ms 146016 KB Output is correct
23 Correct 2972 ms 147080 KB Output is correct
24 Correct 5777 ms 148188 KB Output is correct
25 Correct 5255 ms 150096 KB Output is correct
26 Correct 6147 ms 148828 KB Output is correct
27 Correct 7983 ms 170052 KB Output is correct
28 Correct 1165 ms 150052 KB Output is correct
29 Correct 5577 ms 148324 KB Output is correct
30 Correct 5575 ms 147524 KB Output is correct
31 Correct 5386 ms 148320 KB Output is correct
32 Correct 2134 ms 59548 KB Output is correct
33 Correct 424 ms 55448 KB Output is correct
34 Correct 1530 ms 53196 KB Output is correct
35 Correct 1464 ms 53192 KB Output is correct
36 Correct 2052 ms 53620 KB Output is correct
37 Correct 2157 ms 53368 KB Output is correct