Submission #1292087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292087		shidou26	공장들 (JOI14_factories)	C++20	100 / 100	6402 ms	133704 KiB

factories

#ifndef KURUMI
	#include "factories.h"
#endif

#include <bits/stdc++.h>
using namespace std;

#ifdef KURUMI
    #include "algo/debug.h"
#endif

#define endl '\n'
#define fi first
#define se second
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define filter(v) v.resize(unique(all(v)) - v.begin())
#define dbg(x) "[" #x << " = " << x << "]" 

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T1, typename T2> T2 rand(T1 l, T2 r) {
    return uniform_int_distribution<T2>(l, r)(rng);
}
template<typename T1, typename T2> T2 wrand(T1 l, T2 r, int seed) {
    if(seed == 0) return rand(l, r);
    else return (seed > 0 ? max(rand(l, r), wrand(l, r, seed - 1)) : min(rand(l, r), wrand(l, r, seed + 1)));
}

template<typename T> bool maximize(T &a, T b) {
    if(a < b) {
        a = b;
        return true; 
    }else return false;
}
template<typename T> bool minimize(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }else return false;
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tp3;

const int N = 5e5 + 3;

int n;
vector<pii> adj[N];

namespace Graph {
	const int LOG = 21;

	int timer;
	int tin[N], tout[N], dep[N], par[N][LOG];
	ll pre[N];

	void dfs_lca(int u, int p) {
		tin[u] = ++timer;
		for(int j = 1; j < LOG; j++) {
			par[u][j] = par[par[u][j - 1]][j - 1];
		}

		for(pii e : adj[u]) {
			int v, w; tie(v, w) = e;
			if(v == p) continue;

			dep[v] = dep[u] + 1;
			pre[v] = pre[u] + w;
			par[v][0] = u;

			dfs_lca(v, u);
		}

		tout[u] = timer;
	}

	bool ancestor(int u, int v) {
		return tin[u] <= tin[v] && tout[v] <= tout[u];
	}

	int lca(int u, int v) {
		if(ancestor(u, v)) return u;
		if(ancestor(v, u)) return v;

		for(int i = LOG - 1; i >= 0; i--) {
			if(par[u][i] && !ancestor(par[u][i], v)) {
				u = par[u][i];
			}
		}

		return par[u][0];
	}

	ll distance(int u, int v) {
		return pre[u] + pre[v] - 2 * pre[lca(u, v)];
	}
}
using namespace Graph;

namespace Centroid {
	int siz[N], lift[N];
	bool passed[N];

	void dfs_size(int u, int p) {
		siz[u] = 1;
		for(pii e : adj[u]) {
			int v, w; tie(v, w) = e;
			if(v == p || passed[v]) continue;
			dfs_size(v, u);
			siz[u] += siz[v];
		}
	}

	int find_centroid(int u, int p, int tar) {
		for(pii e : adj[u]) {
			int v, w; tie(v, w) = e;
			if(v == p || passed[v]) continue;
			if(siz[v] * 2 > tar) return find_centroid(v, u, tar);
		}
		return u;
	}

	void decompose(int u, int p) {
		dfs_size(u, -1);
		u = find_centroid(u, -1, siz[u]);

		lift[u] = p;

		passed[u] = true;
		for(pii e : adj[u]) {
			int v = e.fi;
			if(!passed[v]) decompose(v, u);
		}
	}
}
using namespace Centroid;

const ll INF = 1e18 + 3;

ll best[N];

void Init(int _N, int _A[], int _B[], int _D[]) {
	n = _N;

	for(int i = 0; i < n - 1; i++) {
		int u = _A[i], v = _B[i], w = _D[i];
		u++; 
		v++;
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);

		// cout << u << " " << v << " " << w << endl;
	}

	dfs_lca(1, -1);
	decompose(1, -1);

	fill(best + 1, best + 1 + n, INF);
}

void paint(int u) {
	int x = u;
	while(x != -1) {
		minimize(best[x], distance(x, u));
		x = lift[x];
	}
}

void unpaint(int u) {
	int x = u;
	while(x != -1) {
		best[x] = INF;
		x = lift[x];
	}
}

ll get_near(int u) {
	int x = u;
	ll res = INF;

	while(x != -1) {
		minimize(res, best[x] + distance(x, u));
		x = lift[x];
	}

	return res;
}

long long Query(int s, int x[], int t, int y[]) {
	ll answer = INF;
  	for(int i = 0; i < s; i++) paint(x[i] + 1); //, cout << x[i] + 1 << " \n"[i == s - 1];
  	for(int i = 0; i < t; i++) minimize(answer, get_near(y[i] + 1)); //, cout << y[i] + 1 << " \n"[i == t - 1];
  	for(int i = 0; i < s; i++) unpaint(x[i] + 1);
  	return answer;
}

#ifdef KURUMI
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    #define task "Deeto"
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    
    int n, q; cin >> n >> q;
    
    static int a[1000], b[1000], d[1000];
    for(int i = 0; i < n - 1; i++) {
    	cin >> a[i] >> b[i] >> d[i];
    }

    Init(n, a, b, d);

    for(int i = 0; i < q; i++) {
    	int s, t; cin >> s >> t;
    	static int x[1000], y[1000];

    	for(int j = 0; j < s; j++) cin >> x[j];
    	for(int j = 0; j < t; j++) cin >> y[j];

    	cout << Query(s, x, t, y) << endl;
    }	

    cerr << "Saa, watashtachi no deeto hajimemashou" << endl;
    cerr << "Atarashii kiseki wo koko kara hajimeru shining place nee mou ichido kimi to..." << endl;
    
    return 0;
}
#endif

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