oj.uz

Submission #1078003

# Submission time Handle Problem Language Result Execution time Memory
1078003 2024-08-27T11:32:29 Z Sorting Factories (JOI14_factories) C++17
100 / 100
 3979 ms 157720 KB 
#pragma GCC optimize("O3")
#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[]){
    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 12 ms 12636 KB Output is correct
2 Correct 271 ms 30736 KB Output is correct
3 Correct 391 ms 30548 KB Output is correct
4 Correct 333 ms 30548 KB Output is correct
5 Correct 450 ms 30516 KB Output is correct
6 Correct 162 ms 30636 KB Output is correct
7 Correct 338 ms 30592 KB Output is correct
8 Correct 345 ms 30548 KB Output is correct
9 Correct 436 ms 30544 KB Output is correct
10 Correct 190 ms 30612 KB Output is correct
11 Correct 379 ms 30532 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 1398 ms 141760 KB Output is correct
3 Correct 1940 ms 140724 KB Output is correct
4 Correct 587 ms 143952 KB Output is correct
5 Correct 3068 ms 152212 KB Output is correct
6 Correct 2036 ms 142268 KB Output is correct
7 Correct 876 ms 54724 KB Output is correct
8 Correct 298 ms 55496 KB Output is correct
9 Correct 1045 ms 56008 KB Output is correct
10 Correct 927 ms 55184 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12636 KB Output is correct
2 Correct 271 ms 30736 KB Output is correct
3 Correct 391 ms 30548 KB Output is correct
4 Correct 333 ms 30548 KB Output is correct
5 Correct 450 ms 30516 KB Output is correct
6 Correct 162 ms 30636 KB Output is correct
7 Correct 338 ms 30592 KB Output is correct
8 Correct 345 ms 30548 KB Output is correct
9 Correct 436 ms 30544 KB Output is correct
10 Correct 190 ms 30612 KB Output is correct
11 Correct 379 ms 30532 KB Output is correct
12 Correct 7 ms 12380 KB Output is correct
13 Correct 1398 ms 141760 KB Output is correct
14 Correct 1940 ms 140724 KB Output is correct
15 Correct 587 ms 143952 KB Output is correct
16 Correct 3068 ms 152212 KB Output is correct
17 Correct 2036 ms 142268 KB Output is correct
18 Correct 876 ms 54724 KB Output is correct
19 Correct 298 ms 55496 KB Output is correct
20 Correct 1045 ms 56008 KB Output is correct
21 Correct 927 ms 55184 KB Output is correct
22 Correct 1840 ms 150016 KB Output is correct
23 Correct 1877 ms 151080 KB Output is correct
24 Correct 2722 ms 150132 KB Output is correct
25 Correct 2541 ms 151656 KB Output is correct
26 Correct 3051 ms 149932 KB Output is correct
27 Correct 3979 ms 157720 KB Output is correct
28 Correct 703 ms 153148 KB Output is correct
29 Correct 2922 ms 149520 KB Output is correct
30 Correct 2613 ms 149256 KB Output is correct
31 Correct 2583 ms 149184 KB Output is correct
32 Correct 1025 ms 56472 KB Output is correct
33 Correct 242 ms 55576 KB Output is correct
34 Correct 616 ms 53960 KB Output is correct
35 Correct 603 ms 53940 KB Output is correct
36 Correct 802 ms 53884 KB Output is correct
37 Correct 808 ms 53876 KB Output is correct