oj.uz

Submission #235366

# Submission time Handle Problem Language Result Execution time Memory
235366 2020-05-28T07:12:56 Z Atalasion Factories (JOI14_factories) C++14
100 / 100
 6163 ms 133964 KB 
//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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 24448 KB Output is correct
2 Correct 2156 ms 42828 KB Output is correct
3 Correct 2158 ms 42408 KB Output is correct
4 Correct 2109 ms 42928 KB Output is correct
5 Correct 1806 ms 42932 KB Output is correct
6 Correct 1347 ms 42732 KB Output is correct
7 Correct 2152 ms 42568 KB Output is correct
8 Correct 2023 ms 43164 KB Output is correct
9 Correct 1800 ms 42748 KB Output is correct
10 Correct 1348 ms 42776 KB Output is correct
11 Correct 2137 ms 42360 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24192 KB Output is correct
2 Correct 2383 ms 113588 KB Output is correct
3 Correct 3213 ms 113132 KB Output is correct
4 Correct 1765 ms 113936 KB Output is correct
5 Correct 2515 ms 123976 KB Output is correct
6 Correct 3310 ms 114544 KB Output is correct
7 Correct 3588 ms 63368 KB Output is correct
8 Correct 1928 ms 64628 KB Output is correct
9 Correct 2517 ms 65848 KB Output is correct
10 Correct 3438 ms 64924 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 24448 KB Output is correct
2 Correct 2156 ms 42828 KB Output is correct
3 Correct 2158 ms 42408 KB Output is correct
4 Correct 2109 ms 42928 KB Output is correct
5 Correct 1806 ms 42932 KB Output is correct
6 Correct 1347 ms 42732 KB Output is correct
7 Correct 2152 ms 42568 KB Output is correct
8 Correct 2023 ms 43164 KB Output is correct
9 Correct 1800 ms 42748 KB Output is correct
10 Correct 1348 ms 42776 KB Output is correct
11 Correct 2137 ms 42360 KB Output is correct
12 Correct 23 ms 24192 KB Output is correct
13 Correct 2383 ms 113588 KB Output is correct
14 Correct 3213 ms 113132 KB Output is correct
15 Correct 1765 ms 113936 KB Output is correct
16 Correct 2515 ms 123976 KB Output is correct
17 Correct 3310 ms 114544 KB Output is correct
18 Correct 3588 ms 63368 KB Output is correct
19 Correct 1928 ms 64628 KB Output is correct
20 Correct 2517 ms 65848 KB Output is correct
21 Correct 3438 ms 64924 KB Output is correct
22 Correct 6039 ms 126544 KB Output is correct
23 Correct 4772 ms 127356 KB Output is correct
24 Correct 6163 ms 128076 KB Output is correct
25 Correct 5873 ms 129480 KB Output is correct
26 Correct 5657 ms 116188 KB Output is correct
27 Correct 4647 ms 133964 KB Output is correct
28 Correct 3129 ms 130500 KB Output is correct
29 Correct 5412 ms 115324 KB Output is correct
30 Correct 5464 ms 115080 KB Output is correct
31 Correct 5445 ms 115468 KB Output is correct
32 Correct 3129 ms 75680 KB Output is correct
33 Correct 2166 ms 77816 KB Output is correct
34 Correct 3421 ms 62260 KB Output is correct
35 Correct 3311 ms 62188 KB Output is correct
36 Correct 3827 ms 62264 KB Output is correct
37 Correct 3757 ms 62260 KB Output is correct