oj.uz

Submission #921245

# Submission time Handle Problem Language Result Execution time Memory
921245 2024-02-03T15:31:19 Z BBart888 Factories (JOI14_factories) C++14
100 / 100
 4718 ms 237476 KB 
#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <cassert>
#include <cstring>
#include <climits>
#include <functional>
#include <cstdlib>
#include <complex>
#include <array>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <random>
#define fileIO(name) if(fopen(name".in", "r")) {freopen(name".in", "r", stdin); freopen(name".out", "w", stdout);}



using namespace std;
const int MAXN = 1e6 + 111;
using ll = long long;
const int P = 31;
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
using ld = long double;
const ld EPS = 1e-5;
using pii = pair<int, int>;
typedef complex<ll> Point;

int sz[MAXN];
int par[MAXN];
ll best[MAXN];
ll dis[MAXN][25];
vector<pair<int,ll>> adj[MAXN];
bool vis[MAXN];
int lev[MAXN];

int find_size(int v, int p)
{
	if (vis[v])
		return 0;
	sz[v] = 1;
	for (auto u : adj[v])
	{
		if (u.first == p)
			continue;
		sz[v] += find_size(u.first, v);
	}
	return sz[v];
}

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

void calc_it(int v, int p,int C)
{
	for (auto u : adj[v])
	{
		if (u.first == p || vis[u.first])
			continue;
		dis[u.first][lev[u.first] - lev[C]] = dis[v][lev[v] - lev[C]] + u.second;
		calc_it(u.first, v, C);
	}
}

void decompose2(int v, int p)
{
	find_size(v, v);
	
	int c = find_centroid(v, v, sz[v]);

	vis[c] = true;
	calc_it(c, p, c);
	
	for (auto u : adj[c])
	{
		if (u.first == p || vis[u.first])
			continue;
		decompose2(u.first, c);
	}
}


void decompose1(int v, int p)
{
	find_size(v, v);

	int c = find_centroid(v, v, sz[v]);

	vis[c] = true;
	par[c] = p;

	if (p != -1)
		lev[c] = lev[p] + 1;

	for (auto u : adj[c])
	{
		if (u.first == p || vis[u.first])
			continue;
		decompose1(u.first, c);
	}
}


void Init(int n, int a[], int b[], int d[])
{
	for (int i = 0; i < n - 1; i++)
	{
		adj[a[i] + 1].push_back(make_pair(b[i] + 1, d[i]));
		adj[b[i] + 1].push_back(make_pair(a[i] + 1, d[i]));
	}

	fill(best, best + MAXN, 1e18);
	decompose1(1, -1);
	fill(vis, vis + MAXN, false);
	decompose2(1, -1);
}



ll Query(int s, int x[], int t, int y[])
{
	ll ans = 1e18;
	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++)
	{
		int a = x[i];
		int j = 0;
		while (a != -1)
		{
			best[a] = min(best[a], dis[x[i]][j]);
			j++;
			a = par[a];
		}
	}

	for (int i = 0; i < t; i++)
	{
		int b = y[i];
		int j = 0;
		while (b != -1)
		{
			ans = min(ans, best[b] + dis[y[i]][j]);
			j++;
			b = par[b];
		}
	}

	for (int i = 0; i < s; i++)
	{
		int a = x[i];
		while (a != -1)
		{
			best[a] = 1e18;
			a = par[a];
		}
	}

	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 56152 KB Output is correct
2 Correct 197 ms 58880 KB Output is correct
3 Correct 220 ms 60412 KB Output is correct
4 Correct 213 ms 60500 KB Output is correct
5 Correct 234 ms 60916 KB Output is correct
6 Correct 144 ms 58884 KB Output is correct
7 Correct 218 ms 58960 KB Output is correct
8 Correct 219 ms 60616 KB Output is correct
9 Correct 228 ms 60916 KB Output is correct
10 Correct 143 ms 58868 KB Output is correct
11 Correct 214 ms 58864 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 56156 KB Output is correct
2 Correct 1841 ms 190800 KB Output is correct
3 Correct 3204 ms 212768 KB Output is correct
4 Correct 551 ms 206760 KB Output is correct
5 Correct 4139 ms 237036 KB Output is correct
6 Correct 3153 ms 213864 KB Output is correct
7 Correct 626 ms 103676 KB Output is correct
8 Correct 241 ms 104392 KB Output is correct
9 Correct 750 ms 107464 KB Output is correct
10 Correct 667 ms 104448 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 56152 KB Output is correct
2 Correct 197 ms 58880 KB Output is correct
3 Correct 220 ms 60412 KB Output is correct
4 Correct 213 ms 60500 KB Output is correct
5 Correct 234 ms 60916 KB Output is correct
6 Correct 144 ms 58884 KB Output is correct
7 Correct 218 ms 58960 KB Output is correct
8 Correct 219 ms 60616 KB Output is correct
9 Correct 228 ms 60916 KB Output is correct
10 Correct 143 ms 58868 KB Output is correct
11 Correct 214 ms 58864 KB Output is correct
12 Correct 14 ms 56156 KB Output is correct
13 Correct 1841 ms 190800 KB Output is correct
14 Correct 3204 ms 212768 KB Output is correct
15 Correct 551 ms 206760 KB Output is correct
16 Correct 4139 ms 237036 KB Output is correct
17 Correct 3153 ms 213864 KB Output is correct
18 Correct 626 ms 103676 KB Output is correct
19 Correct 241 ms 104392 KB Output is correct
20 Correct 750 ms 107464 KB Output is correct
21 Correct 667 ms 104448 KB Output is correct
22 Correct 1877 ms 214408 KB Output is correct
23 Correct 2008 ms 215580 KB Output is correct
24 Correct 3373 ms 217824 KB Output is correct
25 Correct 3205 ms 219852 KB Output is correct
26 Correct 3945 ms 218320 KB Output is correct
27 Correct 4718 ms 237476 KB Output is correct
28 Correct 645 ms 213204 KB Output is correct
29 Correct 3234 ms 217732 KB Output is correct
30 Correct 3376 ms 217516 KB Output is correct
31 Correct 3390 ms 217548 KB Output is correct
32 Correct 717 ms 109432 KB Output is correct
33 Correct 278 ms 103144 KB Output is correct
34 Correct 465 ms 101952 KB Output is correct
35 Correct 462 ms 101972 KB Output is correct
36 Correct 534 ms 104532 KB Output is correct
37 Correct 618 ms 102724 KB Output is correct