oj.uz

Submission #296717

# Submission time Handle Problem Language Result Execution time Memory
296717 2020-09-10T20:21:51 Z b00n0rp Factories (JOI14_factories) C++17
33 / 100
 8000 ms 224844 KB 
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define pii pair<int,int>
#define F first
#define S second
#define vi vector<int>
#define pb push_back
#define runtime() ((double)(clock())/CLOCKS_PER_SEC)

int n,centroid;
const int MAXN = 500005;
const ll INF = 1e16;

int par[MAXN][21],cenpar[MAXN];
int dep[MAXN],sz[MAXN];
vector<pii> adj[MAXN];
bitset<MAXN> vis;

vi g[MAXN];

ll mnd[MAXN],dist[MAXN];
ll cendist[MAXN][21];

void dfs0(int u){
	for(auto v:adj[u]){
		if(v.F != par[u][0]){
			par[v.F][0] = u;
			dep[v.F] = dep[u]+1;
			dist[v.F] = dist[u]+v.S;
			dfs0(v.F);
		}
	}
}

void dfs_sz(int u,int p){
	sz[u] = 1;
	for(auto v:adj[u]){
		if(v.F != p and vis[v.F] == 0){
			dfs_sz(v.F,u);
			sz[u] += sz[v.F];
		}
	}
}

int find_centroid(int u,int p,int tot){
	for(auto v:adj[u]){
		if(v.F == p or vis[v.F]) continue;
		if(sz[v.F] > tot/2) return find_centroid(v.F,u,tot); 
	}
	return u;
}

void centroid_decomposition(int u,int p){
	dfs_sz(u,u);
	int cen = find_centroid(u,p,sz[u]);
	if(p == -1) centroid = cen;
	else g[p].pb(cen);
	cenpar[cen] = p;
	vis[cen] = 1;
	for(auto v:adj[cen]){
		if(!vis[v.F]) centroid_decomposition(v.F,cen);
	}
}

int lca(int u,int v){
	if(dep[u] < dep[v]) swap(u,v);
	for(int i = 20; i >= 0; i --){
		if(dep[u]-(1<<i) >= dep[v]) u = par[u][i];
	}
	if(u == v) return u;
	for(int i = 20; i >= 0; i --){
		if(par[u][i] != par[v][i]){
			u = par[u][i];
			v = par[v][i];
		}
	}
	return par[u][0];
}

ll calc_dist(int u,int v){
	return dist[u]+dist[v]-2*dist[lca(u,v)];
}

void Init(int N, int A[], int B[], int D[]){
	n = N;
	REP(i,n-1){
		adj[A[i]].pb({B[i],D[i]});
		adj[B[i]].pb({A[i],D[i]});
	}
	par[0][0] = 0;
	dep[0] = 0;
	dfs0(0);
	FOR(j,1,21){
		REP(i,n){
			par[i][j] = par[par[i][j-1]][j-1];
		}
	}
	centroid_decomposition(0,-1);
	REP(i,n+1) mnd[i] = INF;
	REP(i,n){
		int cur = i,cnt = 0;
		while(cur != -1){
			cendist[i][cnt] = calc_dist(i,cur);
			cnt++;
			cur = cenpar[cur];
		}
	}
	// REP(i,n) cout << i << " " << cenpar[i] << endl;
}

void upd(int u,int type){
	int cur = u;
	int cnt = 0;
	while(cur != -1){
		if(type == 0){
			mnd[cur] = min(mnd[cur],cendist[u][cnt]);
		}
		else mnd[cur] = INF;
		cur = cenpar[cur];
		cnt++;
	}
	
	assert(cnt <= 20);
}

ll quer(int u){
	ll res = INF;
	int cur = u;
	int cnt = 0;
	while(cur != -1){
		res = min(res,cendist[u][cnt]+mnd[cur]);
		cur = cenpar[cur];
		cnt ++;
	}
	assert(cnt <= 20);
	return res;
}

ll Query(int S, int X[], int T, int Y[]) {
	REP(i,S) upd(X[i],0);
	ll ans = INF;
	// REP(i,S) REP(j,T) ans = min(ans,calc_dist(X[i],Y[j]));
	REP(i,T) ans = min(ans,quer(Y[i]));
	REP(i,S) upd(X[i],1);
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24440 KB Output is correct
2 Correct 367 ms 33912 KB Output is correct
3 Correct 397 ms 33912 KB Output is correct
4 Correct 397 ms 33912 KB Output is correct
5 Correct 419 ms 34168 KB Output is correct
6 Correct 295 ms 33912 KB Output is correct
7 Correct 399 ms 33912 KB Output is correct
8 Correct 397 ms 33912 KB Output is correct
9 Correct 413 ms 34168 KB Output is correct
10 Correct 288 ms 33916 KB Output is correct
11 Correct 395 ms 33912 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24192 KB Output is correct
2 Correct 2781 ms 199512 KB Output is correct
3 Correct 5673 ms 201332 KB Output is correct
4 Correct 974 ms 197084 KB Output is correct
5 Correct 7801 ms 224712 KB Output is correct
6 Correct 5911 ms 202588 KB Output is correct
7 Correct 1243 ms 68216 KB Output is correct
8 Correct 529 ms 68428 KB Output is correct
9 Correct 1486 ms 72268 KB Output is correct
10 Correct 1263 ms 69496 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24440 KB Output is correct
2 Correct 367 ms 33912 KB Output is correct
3 Correct 397 ms 33912 KB Output is correct
4 Correct 397 ms 33912 KB Output is correct
5 Correct 419 ms 34168 KB Output is correct
6 Correct 295 ms 33912 KB Output is correct
7 Correct 399 ms 33912 KB Output is correct
8 Correct 397 ms 33912 KB Output is correct
9 Correct 413 ms 34168 KB Output is correct
10 Correct 288 ms 33916 KB Output is correct
11 Correct 395 ms 33912 KB Output is correct
12 Correct 19 ms 24192 KB Output is correct
13 Correct 2781 ms 199512 KB Output is correct
14 Correct 5673 ms 201332 KB Output is correct
15 Correct 974 ms 197084 KB Output is correct
16 Correct 7801 ms 224712 KB Output is correct
17 Correct 5911 ms 202588 KB Output is correct
18 Correct 1243 ms 68216 KB Output is correct
19 Correct 529 ms 68428 KB Output is correct
20 Correct 1486 ms 72268 KB Output is correct
21 Correct 1263 ms 69496 KB Output is correct
22 Correct 3153 ms 205552 KB Output is correct
23 Correct 3319 ms 207736 KB Output is correct
24 Correct 6584 ms 207328 KB Output is correct
25 Correct 6628 ms 210656 KB Output is correct
26 Correct 6401 ms 207592 KB Output is correct
27 Execution timed out 8099 ms 224844 KB Time limit exceeded
28 Halted 0 ms 0 KB -