oj.uz

Submission #1077964

# Submission time Handle Problem Language Result Execution time Memory
1077964 2024-08-27T11:13:48 Z Sorting Factories (JOI14_factories) C++17
100 / 100
 6972 ms 223516 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];
vi anc[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, vector<int> &prevs){
    dfs_sz(u);
    int cen = find_centroid(u, sz[u]);

    prevs.push_back(cen);
    vis[cen] = true;
    anc[cen] = prevs;

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

    prevs.pop_back();
}

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);

    vi e{};
    decompose(0, e);

    // 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];
        // cout << v << " ";
        for(int a: anc[v]){
            if(!mn.count(a)) mn[a] = INF;
            chmin(mn[a], get_dist(a, v));
        }
    }
    // cout << "x" << endl;

    ll ans = INF;
    for(int i = 0; i < t; ++i){
        int v = y[i];
        // cout << v << " ";
        for(int a: anc[v]){
            if(!mn.count(a)) continue;
            chmin(ans, mn[a] + get_dist(a, v));
        }
    }
    // cout << "y" << endl;

    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 26712 KB Output is correct
2 Correct 626 ms 35412 KB Output is correct
3 Correct 843 ms 35476 KB Output is correct
4 Correct 627 ms 35524 KB Output is correct
5 Correct 879 ms 35860 KB Output is correct
6 Correct 285 ms 35412 KB Output is correct
7 Correct 838 ms 35412 KB Output is correct
8 Correct 867 ms 35412 KB Output is correct
9 Correct 868 ms 35668 KB Output is correct
10 Correct 271 ms 35412 KB Output is correct
11 Correct 835 ms 35524 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26460 KB Output is correct
2 Correct 2135 ms 157452 KB Output is correct
3 Correct 2776 ms 170760 KB Output is correct
4 Correct 816 ms 148020 KB Output is correct
5 Correct 4444 ms 202656 KB Output is correct
6 Correct 3168 ms 170980 KB Output is correct
7 Correct 2119 ms 61124 KB Output is correct
8 Correct 423 ms 57628 KB Output is correct
9 Correct 2367 ms 64964 KB Output is correct
10 Correct 1776 ms 61384 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 26712 KB Output is correct
2 Correct 626 ms 35412 KB Output is correct
3 Correct 843 ms 35476 KB Output is correct
4 Correct 627 ms 35524 KB Output is correct
5 Correct 879 ms 35860 KB Output is correct
6 Correct 285 ms 35412 KB Output is correct
7 Correct 838 ms 35412 KB Output is correct
8 Correct 867 ms 35412 KB Output is correct
9 Correct 868 ms 35668 KB Output is correct
10 Correct 271 ms 35412 KB Output is correct
11 Correct 835 ms 35524 KB Output is correct
12 Correct 12 ms 26460 KB Output is correct
13 Correct 2135 ms 157452 KB Output is correct
14 Correct 2776 ms 170760 KB Output is correct
15 Correct 816 ms 148020 KB Output is correct
16 Correct 4444 ms 202656 KB Output is correct
17 Correct 3168 ms 170980 KB Output is correct
18 Correct 2119 ms 61124 KB Output is correct
19 Correct 423 ms 57628 KB Output is correct
20 Correct 2367 ms 64964 KB Output is correct
21 Correct 1776 ms 61384 KB Output is correct
22 Correct 4132 ms 159848 KB Output is correct
23 Correct 3656 ms 185800 KB Output is correct
24 Correct 5770 ms 197480 KB Output is correct
25 Correct 6408 ms 199376 KB Output is correct
26 Correct 6205 ms 197988 KB Output is correct
27 Correct 6972 ms 223516 KB Output is correct
28 Correct 1484 ms 176316 KB Output is correct
29 Correct 6385 ms 197480 KB Output is correct
30 Correct 6190 ms 196760 KB Output is correct
31 Correct 6055 ms 197724 KB Output is correct
32 Correct 2402 ms 79844 KB Output is correct
33 Correct 522 ms 71624 KB Output is correct
34 Correct 1650 ms 71648 KB Output is correct
35 Correct 1669 ms 72132 KB Output is correct
36 Correct 2131 ms 74100 KB Output is correct
37 Correct 2232 ms 74100 KB Output is correct