oj.uz

Submission #170852

# Submission time Handle Problem Language Result Execution time Memory
170852 2019-12-26T14:45:39 Z ZwariowanyMarcin Factories (JOI14_factories) C++14
100 / 100
 4838 ms 162940 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)

using namespace std;

const int nax = 5e5 + 111;

int n;
vector <pair<int,int>> v[nax];
int par[nax];
int kil[nax];
int nn;
int siz[nax];
int LVL[nax];
ll odl[nax][20];

void dfs(int u, int p) {
	nn++;
	siz[u] = 1;
	for(auto it : v[u])
		if(it.fi != p && !kil[it.fi]) {
			dfs(it.fi, u);
			siz[u] += siz[it.fi];
		}
}

int daj(int u, int p) {
	for(auto it : v[u])
		if(it.fi != p && !kil[it.fi] && nn <= 2 * siz[it.fi])
			return daj(it.fi, u);
	return u;
}

void getodl(int u, int p, int lvl) {
	for(auto it : v[u]) 
		if(it.fi != p && !kil[it.fi]) {
			odl[it.fi][lvl] = odl[u][lvl] + it.se;
			getodl(it.fi, u, lvl);
		}
}

void decomp(int u, int p, int lvl = 0) {
	nn = 0;
	dfs(u, 0);
	int C = daj(u, 0);
	par[C] = p;
	LVL[C] = lvl;
	kil[C] = 1;
	getodl(C, 0, lvl);
	for(auto it : v[C])
		if(!kil[it.fi])
			decomp(it.fi, C, lvl + 1);
}

ll naj[nax];

void Init(int N, int a[], int b[], int c[]) {
	n = N;
	for(int i = 0; i < n; ++i)
		a[i]++;
	for(int i = 0; i < n; ++i)
		b[i]++;
	for(int i = 0; i < n - 1; ++i) {
		v[a[i]].pb(mp(b[i], c[i]));
		v[b[i]].pb(mp(a[i], c[i]));
	}
	decomp(1, 0);
	for(int i = 1; i <= n; ++i)
		naj[i] = 1e18;
}

ll Query(int s, int x[], int t, int y[]) {
	for(int i = 0; i < s; ++i)
		x[i]++;
	for(int i = 0; i < t; ++i)
		y[i]++;
	ll res = 1e18;
	for(int i = 0; i < s; ++i) {
		int node = x[i];
		while(node != 0) {
			naj[node] = min(naj[node], odl[x[i]][LVL[node]]);
			node = par[node];
		}
	}
	for(int i = 0; i < t; ++i) {
		int node = y[i];
		while(node != 0) {
			res = min(res, naj[node] + odl[y[i]][LVL[node]]);
			node = par[node];
		}
	}
	for(int i = 0; i < s; ++i) {
		int node = x[i];
		while(node != 0) {
			naj[node] = 1e18;
			node = par[node];
		}
	}
	return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12664 KB Output is correct
2 Correct 380 ms 24668 KB Output is correct
3 Correct 404 ms 30612 KB Output is correct
4 Correct 404 ms 30672 KB Output is correct
5 Correct 424 ms 27000 KB Output is correct
6 Correct 301 ms 27608 KB Output is correct
7 Correct 406 ms 28644 KB Output is correct
8 Correct 403 ms 29944 KB Output is correct
9 Correct 425 ms 30200 KB Output is correct
10 Correct 297 ms 29948 KB Output is correct
11 Correct 405 ms 30756 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12412 KB Output is correct
2 Correct 2103 ms 142360 KB Output is correct
3 Correct 3579 ms 136592 KB Output is correct
4 Correct 991 ms 140124 KB Output is correct
5 Correct 4295 ms 162916 KB Output is correct
6 Correct 3425 ms 141680 KB Output is correct
7 Correct 1123 ms 50040 KB Output is correct
8 Correct 487 ms 50832 KB Output is correct
9 Correct 1270 ms 54280 KB Output is correct
10 Correct 1279 ms 51448 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12664 KB Output is correct
2 Correct 380 ms 24668 KB Output is correct
3 Correct 404 ms 30612 KB Output is correct
4 Correct 404 ms 30672 KB Output is correct
5 Correct 424 ms 27000 KB Output is correct
6 Correct 301 ms 27608 KB Output is correct
7 Correct 406 ms 28644 KB Output is correct
8 Correct 403 ms 29944 KB Output is correct
9 Correct 425 ms 30200 KB Output is correct
10 Correct 297 ms 29948 KB Output is correct
11 Correct 405 ms 30756 KB Output is correct
12 Correct 14 ms 12412 KB Output is correct
13 Correct 2103 ms 142360 KB Output is correct
14 Correct 3579 ms 136592 KB Output is correct
15 Correct 991 ms 140124 KB Output is correct
16 Correct 4295 ms 162916 KB Output is correct
17 Correct 3425 ms 141680 KB Output is correct
18 Correct 1123 ms 50040 KB Output is correct
19 Correct 487 ms 50832 KB Output is correct
20 Correct 1270 ms 54280 KB Output is correct
21 Correct 1279 ms 51448 KB Output is correct
22 Correct 2422 ms 135800 KB Output is correct
23 Correct 2559 ms 138064 KB Output is correct
24 Correct 3912 ms 137620 KB Output is correct
25 Correct 4289 ms 141048 KB Output is correct
26 Correct 4032 ms 137708 KB Output is correct
27 Correct 4838 ms 156408 KB Output is correct
28 Correct 1027 ms 162940 KB Output is correct
29 Correct 3958 ms 161116 KB Output is correct
30 Correct 3882 ms 160904 KB Output is correct
31 Correct 4035 ms 161328 KB Output is correct
32 Correct 1367 ms 63480 KB Output is correct
33 Correct 507 ms 60004 KB Output is correct
34 Correct 848 ms 56572 KB Output is correct
35 Correct 854 ms 56704 KB Output is correct
36 Correct 1138 ms 57136 KB Output is correct
37 Correct 1130 ms 57208 KB Output is correct