oj.uz

Submission #103829

# Submission time Handle Problem Language Result Execution time Memory
103829 2019-04-02T20:53:15 Z igba Factories (JOI14_factories) C++17
100 / 100
 5151 ms 174968 KB 
#include <bits/stdc++.h>
#include "factories.h"
 
using namespace std;
#define mkp make_pair
const int MAXN = 5 * 100100, MAXLN = 20;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
int n, sz[MAXN], cdp[MAXN], lvl[MAXN];
long long aux[MAXN];
bool rmd[MAXN], flg[MAXN];
vector<pair<int, int>> g[MAXN];
long long dist[MAXN][MAXLN];
 
void szdfs(int v, int p = -1)
{
	sz[v] = 1;
	for(const auto&[w, u] : g[v])
		if(u != p && !rmd[u])
			szdfs(u, v), sz[v] += sz[u];
}
 
int getCentroid(int v, int p = -1, int rt = -1)
{
	if(rt == -1)
		rt = v;
	for(const auto&[w, u] : g[v])
		if(u != p && !rmd[u] && sz[u] > sz[rt] / 2)
			return getCentroid(u, v, rt);
	return v;
}

void distdfs(int v, int lvl, long long d = 0, int p = -1)
{
	dist[v][lvl] = d;
	for(const auto&[w, u] : g[v])
		if(u != p && !rmd[u])
			distdfs(u, lvl, d + w, v);
}

void cd(int v, int cp = -1, int x = 0)
{
	szdfs(v);
	int c = getCentroid(v);
	lvl[c] = x;
	distdfs(c, x);
	cdp[c] = cp, rmd[c] = true;
	for(const auto&[w, u] : g[c])
		if(!rmd[u])
			cd(u, c, x + 1);
}
 
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(mkp(D[i], B[i])), g[B[i]].push_back(mkp(D[i], A[i]));
	for(int i = 0; i < n; ++i)
		aux[i] = LINF;
	cd(0);
}
 
long long Query(int S, int X[], int T, int Y[])
{
	long long ans = LINF;
	vector<int> s;
	for(int i = 0, cur; i < S; ++i)
	{
		cur = X[i];
		while(cur != -1)
		{
			if(!flg[cur])
				s.push_back(cur), flg[cur] = true;
			aux[cur] = min(aux[cur], dist[X[i]][lvl[cur]]), cur = cdp[cur];
		}
	}
	for(int i = 0, cur; i < T; ++i)
	{
		cur = Y[i];
		while(cur != -1)
			ans = min(ans, aux[cur] + dist[Y[i]][lvl[cur]]), cur = cdp[cur];
	}
	for(const int& x : s)
		aux[x] = LINF, flg[x] = false;
	return ans;
}

Compilation message

factories.cpp: In function 'void szdfs(int, int)':
factories.cpp:17:22: warning: unused variable 'w' [-Wunused-variable]
  for(const auto&[w, u] : g[v])
                      ^
factories.cpp: In function 'int getCentroid(int, int, int)':
factories.cpp:26:22: warning: unused variable 'w' [-Wunused-variable]
  for(const auto&[w, u] : g[v])
                      ^
factories.cpp: In function 'void cd(int, int, int)':
factories.cpp:47:22: warning: unused variable 'w' [-Wunused-variable]
  for(const auto&[w, u] : g[c])
                      ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12544 KB Output is correct
2 Correct 317 ms 21508 KB Output is correct
3 Correct 350 ms 21396 KB Output is correct
4 Correct 356 ms 21564 KB Output is correct
5 Correct 366 ms 21592 KB Output is correct
6 Correct 272 ms 21368 KB Output is correct
7 Correct 359 ms 21564 KB Output is correct
8 Correct 353 ms 21444 KB Output is correct
9 Correct 357 ms 21592 KB Output is correct
10 Correct 249 ms 21368 KB Output is correct
11 Correct 362 ms 21496 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12288 KB Output is correct
2 Correct 2551 ms 132764 KB Output is correct
3 Correct 3811 ms 133468 KB Output is correct
4 Correct 1296 ms 151860 KB Output is correct
5 Correct 5081 ms 168824 KB Output is correct
6 Correct 3845 ms 153484 KB Output is correct
7 Correct 1140 ms 58448 KB Output is correct
8 Correct 553 ms 59440 KB Output is correct
9 Correct 1356 ms 62184 KB Output is correct
10 Correct 1202 ms 59772 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12544 KB Output is correct
2 Correct 317 ms 21508 KB Output is correct
3 Correct 350 ms 21396 KB Output is correct
4 Correct 356 ms 21564 KB Output is correct
5 Correct 366 ms 21592 KB Output is correct
6 Correct 272 ms 21368 KB Output is correct
7 Correct 359 ms 21564 KB Output is correct
8 Correct 353 ms 21444 KB Output is correct
9 Correct 357 ms 21592 KB Output is correct
10 Correct 249 ms 21368 KB Output is correct
11 Correct 362 ms 21496 KB Output is correct
12 Correct 18 ms 12288 KB Output is correct
13 Correct 2551 ms 132764 KB Output is correct
14 Correct 3811 ms 133468 KB Output is correct
15 Correct 1296 ms 151860 KB Output is correct
16 Correct 5081 ms 168824 KB Output is correct
17 Correct 3845 ms 153484 KB Output is correct
18 Correct 1140 ms 58448 KB Output is correct
19 Correct 553 ms 59440 KB Output is correct
20 Correct 1356 ms 62184 KB Output is correct
21 Correct 1202 ms 59772 KB Output is correct
22 Correct 2816 ms 159588 KB Output is correct
23 Correct 3153 ms 162484 KB Output is correct
24 Correct 4443 ms 161040 KB Output is correct
25 Correct 4665 ms 164156 KB Output is correct
26 Correct 4204 ms 160044 KB Output is correct
27 Correct 5151 ms 174968 KB Output is correct
28 Correct 1396 ms 162588 KB Output is correct
29 Correct 4526 ms 159664 KB Output is correct
30 Correct 4363 ms 159552 KB Output is correct
31 Correct 4485 ms 159828 KB Output is correct
32 Correct 1378 ms 62968 KB Output is correct
33 Correct 668 ms 60288 KB Output is correct
34 Correct 901 ms 56696 KB Output is correct
35 Correct 884 ms 56392 KB Output is correct
36 Correct 1213 ms 56824 KB Output is correct
37 Correct 1118 ms 56972 KB Output is correct