Submission #235366

#	Time	Username	Problem	Language	Result	Execution time	Memory
235366		Atalasion	Factories (JOI14_factories)	C++14	100 / 100	6163 ms	133964 KiB

factories

//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize ("Ofast")
#pragma GCC optimize("unroll-loops")


using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 500000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000000000000010;
const ll LOG = 20;

int n, q, mark[N], mark2[N], st[N], ft[N], Time, par[N][LOG], hh[N];
ll h[N], dis[N];
vector<pii> G[N];
vector<pair<int, ll>> g[N];

void DFS(int v = 1, int p = 0){
	par[v][0] = p;
	st[v] = ++Time;
	for (int lg = 1; lg < LOG; lg++) par[v][lg] = par[par[v][lg - 1]][lg - 1];
	for (auto u:G[v]){
		if (u.F == p) continue;
		h[u.F] = h[v] + u.S;
		hh[u.F] = hh[v] + 1;
		DFS(u.F, v);
	}
	ft[v] = Time;
}

int LCA(int v, int u){
	if (hh[v] < hh[u]) swap(v, u);
	int res = hh[v] - hh[u];
	for (int i = 0; i < LOG; i++){
		if (res & (1 << i)) v = par[v][i];
	}
	if (v == u) return v;
	for (int i = LOG - 1; i >= 0; i--){
		if (par[v][i] != par[u][i]) v = par[v][i], u = par[u][i];
	}
	return par[v][0];
} 

void Init(int nn, int A[], int B[], int D[]){
	n = nn;
	for (int i = 0; i < n - 1; i++){
		B[i] ++, A[i] ++;
		G[A[i]].pb({B[i], D[i]});
		G[B[i]].pb({A[i], D[i]});
	}
	DFS();
}

bool cmp(int x, int y){
	return st[x] < st[y];
}

void DJ(int T, int Y[], vi node){
	for (auto u:node) dis[u] = INF;
	set<pair<ll, int>> st;
	for (int i = 0; i < T; i++) dis[Y[i]] = 0, st.insert({0, Y[i]});
	while (st.size()){
		pair<ll, int> fr = *st.begin();
//		cout << fr.F << ' ' << fr.S << '\n';
		st.erase(st.begin());
		for (auto u:g[fr.S]){
//			cout << "YES " << u.F << ' ' << dis[u.F] << ' ' << fr.F << ' ' << fr.S << '\n';
			if (dis[u.F] > fr.F + u.S){
				st.erase({dis[u.F], u.F});
				dis[u.F] = fr.F + u.S;
				st.insert({dis[u.F], u.F});
			}
		}
	}
}

ll Query(int S, int X[], int T, int Y[]){
	vector<int> node;
	for (int i = 0; i < S; i++) X[i]++;
	for (int i = 0; i < T; i++) Y[i] ++;
	for (int i = 0; i < S; i++) node.pb(X[i]), mark[X[i]] = 1;
	for (int i = 0; i < T; i++) node.pb(Y[i]), mark2[Y[i]] = 1;
	sort(all(node), cmp);
	int SZ = node.size();
	for(int i = 1; i < SZ; i++){
		node.pb(LCA(node[i - 1], node[i]));
//		cout << node[i - 1] << ' ' << node[i] << ' ' << LCA(node[i - 1], node[i]) << '\n';
	}
	sort(all(node), cmp);
	stack<int> SS;
	SS.push(node[0]);
	SZ = node.size();
	for (int i = 1; i < SZ; i++){
		while (ft[SS.top()] < ft[node[i]]) SS.pop();
//		cout << node[i] << ' ' << SS.top() << '\n';
		g[SS.top()].pb({node[i], h[node[i]] - h[SS.top()]});
		g[node[i]].pb({SS.top(), h[node[i]] - h[SS.top()]});
		SS.push(node[i]);
	}
	ll ans = INF;
	DJ(T, Y, node);
	for (auto u:node){
		if (mark[u] == 1) ans = min(ans, dis[u]);
		if (mark[u] == 1 && mark2[u] == 1) ans = 0;
		mark[u] = mark2[u] = 0;
		g[u].clear();
		g[u].shrink_to_fit();
	}
	return ans;
}

//int32_t main(){
//	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	cin >> n >> q;
//	vi A, B, D;
//	for (int i = 0; i < n - 1; i++){
//		int x, y, z;
//		cin >> x >> y >> z;
//		A.pb(x), B.pb(y), D.pb(z);
//	}
//	Init(n, A, B, D);
//	for (int i = 1; i <= q; i++){
//		int S, T;
//		cin >> S >> T;
//		vi X, Y;
//		for (int j = 0; j < S; j++){
//			int x;
//			cin >> x;
//			X.pb(x);
//		}
//		for (int j = 0; j < T; j++){
//			int x;
//			cin >> x;
//			Y.pb(x);
//		}
//		cout << Query(S, X, T, Y) << '\n';
//	}
//
//
//
//
//
//
//
//
//
//
//	return 0;
//}
/*
7 1
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4
*/

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