oj.uz

Submission #532372

# Submission time Handle Problem Language Result Execution time Memory
532372 2022-03-02T19:12:39 Z mmonteiro Factories (JOI14_factories) C++17
100 / 100
 6382 ms 202064 KB 
#include <bits/stdc++.h>
using namespace std;
#include "factories.h"

const int MAX = 1e6 + 200;
const long long OO = 0x3f3f3f3f3f3f3f3f;

#define ii pair<int, int>
#define f first
#define s second

int n;
vector<ii> G[MAX];
vector<int> tl;
int SpT[22][MAX], pos[MAX], depth[MAX];
int CD[MAX], sz[MAX];
bool cut[MAX];
long long ans[MAX], weight[MAX];

void dfs(int v, int p, int d)
{
    depth[v] = d;
	pos[v] = tl.size();
	tl.push_back(v);
    for(auto [u, w] : G[v]) {
        if(u != p) {
			weight[u] = weight[v] + w;
            dfs(u, v, d + 1);
			tl.push_back(v);
		}
	}
}

void build() {
	int tam = tl.size();
	for(int i = 0; (1 << i) <= tam; i++) {
		for(int j = 0; j + (1 << i) <= tam; j++) {
			if(!i)
				SpT[i][j] = tl[j];
			else if(depth[SpT[i-1][j]] < depth[SpT[i-1][j+(1<<(i-1))]])
				SpT[i][j] = SpT[i-1][j];
			else
				SpT[i][j] = SpT[i-1][j+(1<<(i-1))];
		}
	}
}

int lca(int u, int v) {
	int i = min(pos[u], pos[v]);
	int j = max(pos[u], pos[v]);
	int k = log2(j-i+1);
	if(depth[SpT[k][i]] < depth[SpT[k][j+1-(1<<k)]])
		return SpT[k][i];
	else
		return SpT[k][j+1-(1<<k)];
}

int dfs2(int v, int p)
{
    int s = 1;
    for(auto [u, w] : G[v])
        if(!cut[u] and u != p)
            s += dfs2(u, v);
    return sz[v] = s;
}

int find_centroid(int v, int p, int tot)
{
    int next_v, cnt = 0;
    for(auto [u, w] : G[v])
        if(!cut[u] and u != p and sz[u] > cnt)
            cnt = sz[u], next_v = u;
    if(cnt > tot / 2) return find_centroid(next_v, v, tot);
    return v;
}

void build_centroid_tree(int v, int p)
{
    dfs2(v, -1);
    int u = find_centroid(v, -1, sz[v]);
    CD[u] = p;
    cut[u] = true;
    for(auto [w, h] : G[u])
        if(!cut[w])
            build_centroid_tree(w, u);
}

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

void paint(int v, int u)
{
    if(v == -1) return;
    ans[v] = min(ans[v], dist(v, u));
    paint(CD[v], u);
}

void unpaint(int v, int u)
{
    if(v == -1) return;
	if(ans[v] == OO) return;

    ans[v] = OO;
    unpaint(CD[v], u);
}

long long query(int v, int u, long long d)
{
    if(v == -1)
        return d;
    return query(CD[v], u, min(d, dist(v, u) + ans[v]));
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for(int i = 0; i < n-1; i++) {
        G[ A[i] ].push_back({B[i], D[i]});
        G[ B[i] ].push_back({A[i], D[i]});
    }
	for(int i = 0; i < N; ++i) ans[i] = OO;
	dfs(0, -1, 0);
	build(); 
    build_centroid_tree(0, -1);
}

long long Query(int S, int X[], int T, int Y[]) {
	long long rep = OO;

	for(int j = 0; j < S; ++j) 
		paint(X[j], X[j]);
	for(int j = 0; j < T; ++j)
		rep = min(rep, query(Y[j], Y[j], OO));

	for(int j = 0; j < S; ++j) 
		unpaint(X[j], X[j]);
	
	return rep;
}

// void mount() {
// 	int A[] = {0, 1, 2, 2, 4, 1};
// 	int B[] = {1, 2, 3, 4, 5, 6};
// 	int D[] = {4, 4, 5, 6, 5, 3};
// 	Init(7, A, B, D);
// }

// int test1() {
// 	int X[] = {0, 6};
// 	int Y[] = {3, 4};
// 	return Query(2, Y, 2, X);
// }

// int test2() {
// 	int X[] = {0, 1, 3};
// 	int Y[] = {4, 6};
// 	return Query(2, Y, 3, X);
// }

// int test3() {
// 	int X[] = {2};
// 	int Y[] = {5};
// 	return Query(1, Y, 1, X);
// }

// int main() {

// 	mount();
// 	assert(test1() == 12);
// 	assert(test2() == 3);
// 	assert(test3() == 11);

// 	return 0;
// }

Compilation message

factories.cpp: In function 'int find_centroid(int, int, int)':
factories.cpp:69:9: warning: 'next_v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |     int next_v, cnt = 0;
      |         ^~~~~~
factories.cpp: In function 'void build_centroid_tree(int, int)':
factories.cpp:69:9: warning: 'next_v' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24268 KB Output is correct
2 Correct 488 ms 32956 KB Output is correct
3 Correct 645 ms 32968 KB Output is correct
4 Correct 602 ms 33048 KB Output is correct
5 Correct 742 ms 33368 KB Output is correct
6 Correct 236 ms 32960 KB Output is correct
7 Correct 624 ms 32964 KB Output is correct
8 Correct 660 ms 33092 KB Output is correct
9 Correct 751 ms 33260 KB Output is correct
10 Correct 246 ms 32956 KB Output is correct
11 Correct 663 ms 32968 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24000 KB Output is correct
2 Correct 2241 ms 150080 KB Output is correct
3 Correct 3049 ms 152552 KB Output is correct
4 Correct 754 ms 150796 KB Output is correct
5 Correct 4375 ms 180704 KB Output is correct
6 Correct 3303 ms 155116 KB Output is correct
7 Correct 1889 ms 69004 KB Output is correct
8 Correct 384 ms 69416 KB Output is correct
9 Correct 2039 ms 73148 KB Output is correct
10 Correct 2146 ms 70356 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24268 KB Output is correct
2 Correct 488 ms 32956 KB Output is correct
3 Correct 645 ms 32968 KB Output is correct
4 Correct 602 ms 33048 KB Output is correct
5 Correct 742 ms 33368 KB Output is correct
6 Correct 236 ms 32960 KB Output is correct
7 Correct 624 ms 32964 KB Output is correct
8 Correct 660 ms 33092 KB Output is correct
9 Correct 751 ms 33260 KB Output is correct
10 Correct 246 ms 32956 KB Output is correct
11 Correct 663 ms 32968 KB Output is correct
12 Correct 15 ms 24000 KB Output is correct
13 Correct 2241 ms 150080 KB Output is correct
14 Correct 3049 ms 152552 KB Output is correct
15 Correct 754 ms 150796 KB Output is correct
16 Correct 4375 ms 180704 KB Output is correct
17 Correct 3303 ms 155116 KB Output is correct
18 Correct 1889 ms 69004 KB Output is correct
19 Correct 384 ms 69416 KB Output is correct
20 Correct 2039 ms 73148 KB Output is correct
21 Correct 2146 ms 70356 KB Output is correct
22 Correct 3198 ms 151916 KB Output is correct
23 Correct 3244 ms 154312 KB Output is correct
24 Correct 4740 ms 154460 KB Output is correct
25 Correct 4833 ms 182120 KB Output is correct
26 Correct 4911 ms 178296 KB Output is correct
27 Correct 6382 ms 202064 KB Output is correct
28 Correct 1073 ms 179068 KB Output is correct
29 Correct 4871 ms 178140 KB Output is correct
30 Correct 5138 ms 177456 KB Output is correct
31 Correct 4912 ms 178028 KB Output is correct
32 Correct 2096 ms 75192 KB Output is correct
33 Correct 392 ms 70944 KB Output is correct
34 Correct 1332 ms 67620 KB Output is correct
35 Correct 1357 ms 67620 KB Output is correct
36 Correct 1759 ms 68228 KB Output is correct
37 Correct 1768 ms 68220 KB Output is correct