oj.uz

답안 #1077990

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1077990 2024-08-27T11:27:12 Z Sorting 공장들 (JOI14_factories) C++17
100 / 100
 3771 ms 171192 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[]){
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 12632 KB Output is correct
2 Correct 279 ms 30216 KB Output is correct
3 Correct 347 ms 30548 KB Output is correct
4 Correct 349 ms 30180 KB Output is correct
5 Correct 425 ms 30548 KB Output is correct
6 Correct 199 ms 30400 KB Output is correct
7 Correct 345 ms 30276 KB Output is correct
8 Correct 339 ms 30288 KB Output is correct
9 Correct 407 ms 30544 KB Output is correct
10 Correct 146 ms 30292 KB Output is correct
11 Correct 328 ms 30292 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12380 KB Output is correct
2 Correct 1402 ms 140864 KB Output is correct
3 Correct 1810 ms 142800 KB Output is correct
4 Correct 568 ms 143292 KB Output is correct
5 Correct 2600 ms 170980 KB Output is correct
6 Correct 1805 ms 143852 KB Output is correct
7 Correct 814 ms 54668 KB Output is correct
8 Correct 242 ms 55224 KB Output is correct
9 Correct 1008 ms 58112 KB Output is correct
10 Correct 858 ms 55248 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 12632 KB Output is correct
2 Correct 279 ms 30216 KB Output is correct
3 Correct 347 ms 30548 KB Output is correct
4 Correct 349 ms 30180 KB Output is correct
5 Correct 425 ms 30548 KB Output is correct
6 Correct 199 ms 30400 KB Output is correct
7 Correct 345 ms 30276 KB Output is correct
8 Correct 339 ms 30288 KB Output is correct
9 Correct 407 ms 30544 KB Output is correct
10 Correct 146 ms 30292 KB Output is correct
11 Correct 328 ms 30292 KB Output is correct
12 Correct 6 ms 12380 KB Output is correct
13 Correct 1402 ms 140864 KB Output is correct
14 Correct 1810 ms 142800 KB Output is correct
15 Correct 568 ms 143292 KB Output is correct
16 Correct 2600 ms 170980 KB Output is correct
17 Correct 1805 ms 143852 KB Output is correct
18 Correct 814 ms 54668 KB Output is correct
19 Correct 242 ms 55224 KB Output is correct
20 Correct 1008 ms 58112 KB Output is correct
21 Correct 858 ms 55248 KB Output is correct
22 Correct 2117 ms 148828 KB Output is correct
23 Correct 1963 ms 150144 KB Output is correct
24 Correct 2590 ms 150912 KB Output is correct
25 Correct 2554 ms 152948 KB Output is correct
26 Correct 2469 ms 151352 KB Output is correct
27 Correct 3771 ms 171192 KB Output is correct
28 Correct 700 ms 151200 KB Output is correct
29 Correct 2994 ms 146724 KB Output is correct
30 Correct 3087 ms 145720 KB Output is correct
31 Correct 3452 ms 146440 KB Output is correct
32 Correct 1081 ms 56028 KB Output is correct
33 Correct 283 ms 52368 KB Output is correct
34 Correct 694 ms 50812 KB Output is correct
35 Correct 724 ms 50888 KB Output is correct
36 Correct 910 ms 51144 KB Output is correct
37 Correct 896 ms 51320 KB Output is correct