oj.uz

Submission #498138

# Submission time Handle Problem Language Result Execution time Memory
498138 2021-12-24T12:23:10 Z luanaamorim Factories (JOI14_factories) C++17
100 / 100
 7621 ms 140172 KB 
#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring>
#include <set>
#include <stack>
#include <bitset>
#include "factories.h"
#define ll long long
#define INF (ll) (1e17)
#define MAXL 21
#define MAX (int) (1e6 + 5)
#define MOD 1000000007
#define par pair<int, int>
#define all(v) v.begin(), v.end()
#define sz(x) (int) ((x).size())
#define esq(x) (x<<1)
#define dir(x) ((x<<1)|1)
#define lsb(x) (x & -x)
#define W(x) cout << #x << ": " << x << endl
#define Wii(x) cout << x.first << ' ' << x.second << endl
#define _ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

//lca

int up[MAX][MAXL], tin[MAX], tout[MAX], t;
ll nivel[MAX];
vector<par> grafo[MAX];

void dfs(int u, int p = 0)
{
	up[u][0] = p;
	for (int i = 1; i < MAXL; i++)
		up[u][i] = up[up[u][i-1]][i-1];
	tin[u] = ++t;
	for (auto[v, w] : grafo[u])
	{
		if (v==p) continue;
		nivel[v] = nivel[u] + w;
		dfs(v, u);
	}

	tout[u] = ++t;
}

int anc(int u, int v)
{
	return (tin[u] <= tin[v] && tout[v] <= tout[u]);
}

int LCA(int u, int v)
{
	if (anc(u, v)) return u;
	if (anc(v, u)) return v;

	for (int i = MAXL-1; i >= 0; i--)
		if (!anc(up[v][i], u) && up[v][i]) v = up[v][i];
	return up[v][0];
}

ll dist(int u, int v)
{
	return (nivel[u] + nivel[v] - (nivel[LCA(u, v)]<<1));
}

//centroid

bitset<MAX> vis;
int pai[MAX], sub[MAX];

int tam(int u, int p = 0)
{
	if (vis[u]) return 0;
	sub[u] = 1;
	for (auto[v, w] : grafo[u])
		if (v!=p) sub[u] += tam(v, u);
	return sub[u];
}

int centroid(int u, int p, int t)
{
	for (auto[v, w] : grafo[u])
		if (!vis[v] && v!=p && sub[v]>(t>>1)) return centroid(v, u, t);
	return u;
}

void build(int u, int p = 0)
{
	tam(u);
	int c = centroid(u, 0, sub[u]);
	vis[c] = 1, pai[c] = p;

	for (auto[v, w] : grafo[c])
		if (!vis[v]) build(v, c);
}

//problem

ll resp[MAX];

void ini(int u)
{
	int k = u;
	while (k)
	{ 
		resp[k] = INF;
		k = pai[k];
	}		
}

void update(int u)
{
	int k = u;
	while (k)
	{ 
		resp[k] = min(resp[k], dist(u, k));
		k = pai[k];
	}	
}	

ll query(int u)
{
	ll k = u, r = INF;
	while (k)
	{ 
		r = min(r, dist(u, k) + resp[k]);
		k = pai[k];
	}

	return r;
}

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

	dfs(1);
	build(1);

	for (int i = 0; i < MAX; i++)
		resp[i] = INF;
}

ll Query(int s, int a[], int t, int b[])
{
	ll r = INF;

	for (int i = 0; i < s; i++)
		update(a[i]+1);

	for (int i = 0; i < t; i++)
		r = min(r, query(b[i]+1));

	for (int i = 0; i < s; i++)
		ini(a[i]+1);

	return r;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 32004 KB Output is correct
2 Correct 452 ms 40352 KB Output is correct
3 Correct 972 ms 40360 KB Output is correct
4 Correct 946 ms 40388 KB Output is correct
5 Correct 522 ms 40696 KB Output is correct
6 Correct 216 ms 40364 KB Output is correct
7 Correct 1018 ms 40372 KB Output is correct
8 Correct 1043 ms 40476 KB Output is correct
9 Correct 504 ms 40644 KB Output is correct
10 Correct 196 ms 40360 KB Output is correct
11 Correct 1004 ms 40388 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31820 KB Output is correct
2 Correct 1981 ms 116060 KB Output is correct
3 Correct 4734 ms 117468 KB Output is correct
4 Correct 673 ms 116712 KB Output is correct
5 Correct 3418 ms 140172 KB Output is correct
6 Correct 4914 ms 124972 KB Output is correct
7 Correct 2996 ms 58320 KB Output is correct
8 Correct 330 ms 59092 KB Output is correct
9 Correct 1224 ms 61752 KB Output is correct
10 Correct 2828 ms 59584 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 32004 KB Output is correct
2 Correct 452 ms 40352 KB Output is correct
3 Correct 972 ms 40360 KB Output is correct
4 Correct 946 ms 40388 KB Output is correct
5 Correct 522 ms 40696 KB Output is correct
6 Correct 216 ms 40364 KB Output is correct
7 Correct 1018 ms 40372 KB Output is correct
8 Correct 1043 ms 40476 KB Output is correct
9 Correct 504 ms 40644 KB Output is correct
10 Correct 196 ms 40360 KB Output is correct
11 Correct 1004 ms 40388 KB Output is correct
12 Correct 20 ms 31820 KB Output is correct
13 Correct 1981 ms 116060 KB Output is correct
14 Correct 4734 ms 117468 KB Output is correct
15 Correct 673 ms 116712 KB Output is correct
16 Correct 3418 ms 140172 KB Output is correct
17 Correct 4914 ms 124972 KB Output is correct
18 Correct 2996 ms 58320 KB Output is correct
19 Correct 330 ms 59092 KB Output is correct
20 Correct 1224 ms 61752 KB Output is correct
21 Correct 2828 ms 59584 KB Output is correct
22 Correct 2527 ms 120888 KB Output is correct
23 Correct 2583 ms 123024 KB Output is correct
24 Correct 7434 ms 122480 KB Output is correct
25 Correct 7434 ms 124112 KB Output is correct
26 Correct 7598 ms 120732 KB Output is correct
27 Correct 3826 ms 139516 KB Output is correct
28 Correct 777 ms 121708 KB Output is correct
29 Correct 7559 ms 119416 KB Output is correct
30 Correct 7621 ms 118864 KB Output is correct
31 Correct 7533 ms 119484 KB Output is correct
32 Correct 1143 ms 61496 KB Output is correct
33 Correct 313 ms 58020 KB Output is correct
34 Correct 942 ms 55024 KB Output is correct
35 Correct 1012 ms 55112 KB Output is correct
36 Correct 2587 ms 55648 KB Output is correct
37 Correct 2624 ms 55484 KB Output is correct