oj.uz

Submission #1078008

# Submission time Handle Problem Language Result Execution time Memory
1078008 2024-08-27T11:33:45 Z Sorting Factories (JOI14_factories) C++17
100 / 100
 3423 ms 168476 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);
    }
}

const ll INF = 1e18;
ll mn[N];

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

    for(int i = 0; i < n; ++i)
        mn[i] = INF;
}

ll Query(int s, int *x, int t, int *y){
    if(s > t){
        swap(s, t);
        swap(x, y);
    }

    for(int i = 0; i < s; ++i){
        int v = x[i];
        int a = v;

        while(a != -1){
            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){
            chmin(ans, mn[a] + get_dist(a, v));
            a = cen_par[a];
        }
    }

    for(int i = 0; i < s; ++i){
        int v = x[i];
        int a = v;

        while(a != -1){
            mn[a] = INF;
            a = cen_par[a];
        }
    }

    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12636 KB Output is correct
2 Correct 277 ms 28404 KB Output is correct
3 Correct 350 ms 28500 KB Output is correct
4 Correct 369 ms 28496 KB Output is correct
5 Correct 409 ms 28756 KB Output is correct
6 Correct 158 ms 28500 KB Output is correct
7 Correct 341 ms 28436 KB Output is correct
8 Correct 324 ms 28756 KB Output is correct
9 Correct 405 ms 28752 KB Output is correct
10 Correct 153 ms 28616 KB Output is correct
11 Correct 338 ms 28492 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12376 KB Output is correct
2 Correct 1431 ms 137248 KB Output is correct
3 Correct 1910 ms 139364 KB Output is correct
4 Correct 560 ms 139704 KB Output is correct
5 Correct 2725 ms 167260 KB Output is correct
6 Correct 1976 ms 140056 KB Output is correct
7 Correct 869 ms 52184 KB Output is correct
8 Correct 254 ms 52424 KB Output is correct
9 Correct 1079 ms 55256 KB Output is correct
10 Correct 864 ms 52424 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12636 KB Output is correct
2 Correct 277 ms 28404 KB Output is correct
3 Correct 350 ms 28500 KB Output is correct
4 Correct 369 ms 28496 KB Output is correct
5 Correct 409 ms 28756 KB Output is correct
6 Correct 158 ms 28500 KB Output is correct
7 Correct 341 ms 28436 KB Output is correct
8 Correct 324 ms 28756 KB Output is correct
9 Correct 405 ms 28752 KB Output is correct
10 Correct 153 ms 28616 KB Output is correct
11 Correct 338 ms 28492 KB Output is correct
12 Correct 7 ms 12376 KB Output is correct
13 Correct 1431 ms 137248 KB Output is correct
14 Correct 1910 ms 139364 KB Output is correct
15 Correct 560 ms 139704 KB Output is correct
16 Correct 2725 ms 167260 KB Output is correct
17 Correct 1976 ms 140056 KB Output is correct
18 Correct 869 ms 52184 KB Output is correct
19 Correct 254 ms 52424 KB Output is correct
20 Correct 1079 ms 55256 KB Output is correct
21 Correct 864 ms 52424 KB Output is correct
22 Correct 2008 ms 144224 KB Output is correct
23 Correct 1936 ms 145400 KB Output is correct
24 Correct 2508 ms 146284 KB Output is correct
25 Correct 2496 ms 148348 KB Output is correct
26 Correct 2593 ms 147176 KB Output is correct
27 Correct 3423 ms 168476 KB Output is correct
28 Correct 637 ms 148312 KB Output is correct
29 Correct 2487 ms 146740 KB Output is correct
30 Correct 2588 ms 145972 KB Output is correct
31 Correct 2575 ms 140884 KB Output is correct
32 Correct 1016 ms 52372 KB Output is correct
33 Correct 243 ms 48840 KB Output is correct
34 Correct 611 ms 47200 KB Output is correct
35 Correct 623 ms 47192 KB Output is correct
36 Correct 860 ms 47632 KB Output is correct
37 Correct 822 ms 47780 KB Output is correct