oj.uz

Submission #79089

# Submission time Handle Problem Language Result Execution time Memory
79089 2018-10-11T04:36:18 Z gs14004 Factories (JOI14_factories) C++17
100 / 100
 5863 ms 295116 KB 
#include "factories.h"
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
typedef long long lint;
typedef pair<lint,int> pi;

vector<pi> graph[500005];

int piv, dfn[500005];
int dep[500005], sz[500005];
lint dist[500005];
int pa[500005][19];

int dfs(int x, int par){
	dfn[x] = ++piv;
	sz[x] = 1;
	for (auto &i : graph[x]){
		if(par == i.second) continue;
		dep[i.second] = dep[x] + 1;
		dist[i.second] = dist[x] + i.first;
		pa[i.second][0] = x;
		sz[x] += dfs(i.second, x);
	}
	return sz[x];
}

void Init(int N, int A[], int B[], int D[]){
	for (int i=0; i<N-1; i++) {
		graph[A[i]+1].push_back(pi(D[i],B[i]+1));
		graph[B[i]+1].push_back(pi(D[i],A[i]+1));
	}
	dfs(1, 0);
	for(int i=1; i<=18; i++){
		for(int j=1; j<=N; j++){
			pa[j][i] = pa[pa[j][i-1]][i-1];
		}
	}
}

int lca(int x, int y){
	if(dep[x] < dep[y]) swap(x,y);
	int dx = dep[x] - dep[y];
	for (int i=0; (1<<i) <= dx; i++) {
		if(dx & (1<<i)) {
			x = pa[x][i];
		}
	}
	for (int i=18; i>=0; i--) {
		if(pa[x][i] != pa[y][i]){
			x = pa[x][i];
			y = pa[y][i];
		}
	}
	if(x != y) x = pa[x][0];
	return x;
}

bool cmp(int a, int b){
	return dfn[a] < dfn[b];
}

bool sub(int a, int b){
	return dfn[a] + sz[a] >= dfn[b] + sz[b];
}

vector<pi> g2[500005];
vector<int> pos;
int c;
int vis_stamp[500005];
int object[500005];
void const_g(){
	vector<int> stk;
	for(auto &i : pos){
		if(stk.empty()) stk.push_back(i);
		else{
			while(!stk.empty() && !sub(stk.back(), i)) stk.pop_back();
			int par = stk.back();
			int cur = i;
			g2[par].emplace_back(dist[cur] - dist[par], cur);
			g2[cur].emplace_back(dist[cur] - dist[par], par);
			stk.push_back(cur);
		}
	}
}

lint dijkstra(int n, int* s){
	priority_queue<pi,vector<pi>,greater<pi> > pq;
	for (int i=0; i<n; i++) {
		pq.push(pi(0ll,s[i] + 1));
	}
	while (!pq.empty()) {
		pi t = pq.top();
		pq.pop();
		if(vis_stamp[t.second] == c) continue;
		vis_stamp[t.second] = c;
		if(object[t.second] == c){
			return t.first;
		}
		for (pi &i : g2[t.second]){
			if(vis_stamp[i.second] == c) continue;
			pq.push(pi(t.first + i.first, i.second));
		}
	}
	return -1;
}

lint Query(int S, int X[], int T, int Y[]){
	c++;
	for (int i=0; i<S; i++) {
		pos.push_back(X[i]+1);
	}
	for (int i=0; i<T; i++) {
		object[Y[i]+1] = c;
		pos.push_back(Y[i]+1);
	}
	sort(pos.begin(),pos.end(),cmp);
	int p = (int)pos.size() - 1;
	for (int i=0; i<p; i++) {
		pos.push_back(lca(pos[i],pos[i+1]));
	}
	sort(pos.begin(),pos.end(),cmp);
	pos.resize(unique(pos.begin(),pos.end()) - pos.begin());
	const_g();
	lint ret = dijkstra(S,X);
	for (int &i : pos){
		g2[i].clear();
	}
	pos.clear();
	return ret;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 24572 KB Output is correct
2 Correct 1610 ms 42924 KB Output is correct
3 Correct 1486 ms 52268 KB Output is correct
4 Correct 1673 ms 62040 KB Output is correct
5 Correct 1629 ms 71680 KB Output is correct
6 Correct 1180 ms 80920 KB Output is correct
7 Correct 1445 ms 90228 KB Output is correct
8 Correct 1549 ms 99772 KB Output is correct
9 Correct 1554 ms 109424 KB Output is correct
10 Correct 1193 ms 118756 KB Output is correct
11 Correct 1507 ms 122256 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 122256 KB Output is correct
2 Correct 2484 ms 216724 KB Output is correct
3 Correct 3245 ms 219380 KB Output is correct
4 Correct 1940 ms 219380 KB Output is correct
5 Correct 3255 ms 242684 KB Output is correct
6 Correct 3487 ms 242684 KB Output is correct
7 Correct 2975 ms 242684 KB Output is correct
8 Correct 1966 ms 242684 KB Output is correct
9 Correct 3012 ms 242684 KB Output is correct
10 Correct 3119 ms 242684 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 24572 KB Output is correct
2 Correct 1610 ms 42924 KB Output is correct
3 Correct 1486 ms 52268 KB Output is correct
4 Correct 1673 ms 62040 KB Output is correct
5 Correct 1629 ms 71680 KB Output is correct
6 Correct 1180 ms 80920 KB Output is correct
7 Correct 1445 ms 90228 KB Output is correct
8 Correct 1549 ms 99772 KB Output is correct
9 Correct 1554 ms 109424 KB Output is correct
10 Correct 1193 ms 118756 KB Output is correct
11 Correct 1507 ms 122256 KB Output is correct
12 Correct 27 ms 122256 KB Output is correct
13 Correct 2484 ms 216724 KB Output is correct
14 Correct 3245 ms 219380 KB Output is correct
15 Correct 1940 ms 219380 KB Output is correct
16 Correct 3255 ms 242684 KB Output is correct
17 Correct 3487 ms 242684 KB Output is correct
18 Correct 2975 ms 242684 KB Output is correct
19 Correct 1966 ms 242684 KB Output is correct
20 Correct 3012 ms 242684 KB Output is correct
21 Correct 3119 ms 242684 KB Output is correct
22 Correct 4753 ms 242684 KB Output is correct
23 Correct 4303 ms 242684 KB Output is correct
24 Correct 4636 ms 242684 KB Output is correct
25 Correct 4776 ms 242684 KB Output is correct
26 Correct 4937 ms 242684 KB Output is correct
27 Correct 5146 ms 246828 KB Output is correct
28 Correct 3472 ms 249504 KB Output is correct
29 Correct 5518 ms 272740 KB Output is correct
30 Correct 5578 ms 294792 KB Output is correct
31 Correct 5863 ms 295116 KB Output is correct
32 Correct 3138 ms 295116 KB Output is correct
33 Correct 2234 ms 295116 KB Output is correct
34 Correct 2932 ms 295116 KB Output is correct
35 Correct 2851 ms 295116 KB Output is correct
36 Correct 3027 ms 295116 KB Output is correct
37 Correct 2929 ms 295116 KB Output is correct