oj.uz

Submission #921243

# Submission time Handle Problem Language Result Execution time Memory
921243 2024-02-03T15:30:43 Z BBart888 Factories (JOI14_factories) C++14
15 / 100
 401 ms 159668 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 = 2e5 + 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 12 ms 29264 KB Output is correct
2 Correct 198 ms 43208 KB Output is correct
3 Correct 213 ms 45116 KB Output is correct
4 Correct 210 ms 45068 KB Output is correct
5 Correct 231 ms 45396 KB Output is correct
6 Correct 156 ms 43324 KB Output is correct
7 Correct 210 ms 43364 KB Output is correct
8 Correct 221 ms 45120 KB Output is correct
9 Correct 225 ms 45404 KB Output is correct
10 Correct 141 ms 43352 KB Output is correct
11 Correct 215 ms 43344 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29216 KB Output is correct
2 Runtime error 401 ms 159668 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 29264 KB Output is correct
2 Correct 198 ms 43208 KB Output is correct
3 Correct 213 ms 45116 KB Output is correct
4 Correct 210 ms 45068 KB Output is correct
5 Correct 231 ms 45396 KB Output is correct
6 Correct 156 ms 43324 KB Output is correct
7 Correct 210 ms 43364 KB Output is correct
8 Correct 221 ms 45120 KB Output is correct
9 Correct 225 ms 45404 KB Output is correct
10 Correct 141 ms 43352 KB Output is correct
11 Correct 215 ms 43344 KB Output is correct
12 Correct 6 ms 29216 KB Output is correct
13 Runtime error 401 ms 159668 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -