제출 #212578

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
212578		ChrisT	공장들 (JOI14_factories)	C++17	100 / 100	5098 ms	509532 KiB

factories

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pil = pair<int,ll>;
using ld = long double;
#define all(x) (x).begin(),(x).end()
const int MN = 5e5+3, LOG = 20, MOD = 1e9+7;
mt19937_64 rnd = mt19937_64(chrono::steady_clock::now().time_since_epoch().count());
int sz[MN], p[MN], st[MN], tt=0; bool done[MN]; ll push[MN], down[MN], up[MN], sp[MN<<1][LOG];
vector<pii> adj[MN];vector<pil> go[MN];
void prep (int cur, int par = -1) {
	sp[st[cur] = ++tt][0] = push[cur];
    for (pii i : adj[cur]) if (i.first != par) {
        push[i.first] = push[cur] + i.second;
        prep(i.first,cur);
		sp[++tt][0] = push[cur];
    }
}
void initlca () {
	for (int j = 1; j < LOG; j++)
		for (int i = 1; i <= tt-(1<<j)+1; i++)
			sp[i][j] = min(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
}
ll dist (int a, int b) {
	if (a == b) return 0;
	if (st[a] > st[b]) swap(a,b);
	int lg = 31 - __builtin_clz(st[b]-st[a]+1);
	return push[a] + push[b] - min(sp[st[a]][lg],sp[st[b]-(1<<lg)+1][lg])*2;
}
int dfs (int cur, int par = -1) {
    sz[cur] = 1;
    for (pii i : adj[cur]) if (!done[i.first] && i.first != par) {
        sz[cur] += dfs(i.first,cur);
    }
    return sz[cur];
}
int findcent (int cur, int tot, int par = -1) {
    for (pii i : adj[cur]) {
        if (i.first != par && !done[i.first] && sz[i.first] > (tot>>1))
            return findcent(i.first,tot,cur);
    }
    return cur;
}
void maketree (int cur, int lst = 0) {
    dfs(cur);
    int cent = findcent(cur,sz[cur]);
    done[cent] = 1;
    p[cent] = lst;
    for (pii i : adj[cent]) if (!done[i.first]) maketree(i.first,cent);
}
void Init (int n, int *a, int *b, int *d) {
    for (int i = 0; i < n-1; i++) {
        adj[++a[i]].emplace_back(++b[i],d[i]);
        adj[b[i]].emplace_back(a[i],d[i]);
    }
    prep(1);
    maketree(1);
	initlca();
	for (int i = 1; i <= n; i++) {
		int cur = i;
		while (cur) {
			go[i].emplace_back(cur,dist(i,cur));
			cur = p[cur];
		}
	}
    memset(down,0x3f,sizeof down);
}
ll Query (int s, int *x, int t, int *y) {
    ll ret = LLONG_MAX;
    for (int i = 0; i < s; i++) {
		for (auto &pp : go[++x[i]])
			if (pp.second < down[pp.first])
				down[pp.first] = pp.second;
    }
    for (int i = 0; i < t; i++) {
		for (auto &pp : go[++y[i]])
			ret = min(ret,pp.second + down[pp.first]);
    }
    for (int i = 0; i < s; i++) {
        for (auto &pp : go[x[i]])
			down[pp.first] = 1e18;
    }
    return ret;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67