oj.uz

Submission #240117

# Submission time Handle Problem Language Result Execution time Memory
240117 2020-06-18T06:11:31 Z frodakcin Factories (JOI14_factories) C++11
100 / 100
 6329 ms 331592 KB 
#include "factories.h"

#include <cstring>
#include <vector>

template<typename T> bool ckmax(T& a, T b){return a<b?a=b,1:0;}
template<typename T> bool ckmin(T& a, T b){return b<a?a=b,1:0;}

using ll = long long;

const ll INF = 0x3f3f3f3f3f3f3f3f;
const int MN = 5e5+10;

struct edge{public: int n,w;};
std::vector<edge> a[MN];
struct group{public: int c;ll d;};
std::vector<group> g[MN];
int s[MN];
bool r[MN];
ll ans, bt[MN], bs[MN];

int dfs(int n, int p=-1)
{
	s[n]=1;
	for(auto x:a[n])
		if(!r[x.n]&&x.n!=p)
			s[n]+=dfs(x.n, n);
	return s[n];
}
int get_centroid(int n, int ms, int p=-1)
{
	for(auto x:a[n])
		if(!r[x.n]&&x.n!=p)
			if(s[x.n]*2>=ms)
				return get_centroid(x.n, ms, n);
	return n;
}
int top;
void dfs2(int n, int p=-1, ll d=0)
{
	g[n].push_back({top, d});
	for(auto x:a[n])
		if(!r[x.n]&&x.n!=p)
			dfs2(x.n, n, d+x.w);
}
void work(int n)
{
	int c=get_centroid(n, dfs(n));
	top=c;
	dfs2(c);
	r[c]=1;
	for(auto x:a[c])
		if(!r[x.n])
			work(x.n);
}
void Init(int N, int A[], int B[], int D[])
{
	for(int i=0;i+1<N;++i)
		a[A[i]].push_back({B[i], D[i]}), a[B[i]].push_back({A[i], D[i]});
	work(0);
	memset(bs, 0x3f, sizeof bs);
	memset(bt, 0x3f, sizeof bt);
}

long long Query(int S, int X[], int T, int Y[])
{
	ans=INF;
	for(int i=0;i<S;++i)
		for(auto x:g[X[i]])
			ckmin(bs[x.c], x.d);
	for(int i=0;i<T;++i)
		for(auto x:g[Y[i]])
			ckmin(bt[x.c], x.d), ckmin(ans, bs[x.c]+bt[x.c]);
	for(int i=0;i<S;++i)
		for(auto x:g[X[i]])
			bs[x.c]=bt[x.c]=INF;
	for(int i=0;i<T;++i)
		for(auto x:g[Y[i]])
			bs[x.c]=bt[x.c]=INF;
  return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 32128 KB Output is correct
2 Correct 518 ms 40824 KB Output is correct
3 Correct 546 ms 41592 KB Output is correct
4 Correct 553 ms 41464 KB Output is correct
5 Correct 589 ms 41848 KB Output is correct
6 Correct 397 ms 40568 KB Output is correct
7 Correct 534 ms 41464 KB Output is correct
8 Correct 550 ms 41616 KB Output is correct
9 Correct 600 ms 41848 KB Output is correct
10 Correct 407 ms 40568 KB Output is correct
11 Correct 539 ms 41592 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 31872 KB Output is correct
2 Correct 2974 ms 193288 KB Output is correct
3 Correct 4113 ms 261516 KB Output is correct
4 Correct 1218 ms 90076 KB Output is correct
5 Correct 5380 ms 328464 KB Output is correct
6 Correct 4366 ms 262264 KB Output is correct
7 Correct 1481 ms 74592 KB Output is correct
8 Correct 733 ms 52844 KB Output is correct
9 Correct 1677 ms 87328 KB Output is correct
10 Correct 1595 ms 75804 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 32128 KB Output is correct
2 Correct 518 ms 40824 KB Output is correct
3 Correct 546 ms 41592 KB Output is correct
4 Correct 553 ms 41464 KB Output is correct
5 Correct 589 ms 41848 KB Output is correct
6 Correct 397 ms 40568 KB Output is correct
7 Correct 534 ms 41464 KB Output is correct
8 Correct 550 ms 41616 KB Output is correct
9 Correct 600 ms 41848 KB Output is correct
10 Correct 407 ms 40568 KB Output is correct
11 Correct 539 ms 41592 KB Output is correct
12 Correct 26 ms 31872 KB Output is correct
13 Correct 2974 ms 193288 KB Output is correct
14 Correct 4113 ms 261516 KB Output is correct
15 Correct 1218 ms 90076 KB Output is correct
16 Correct 5380 ms 328464 KB Output is correct
17 Correct 4366 ms 262264 KB Output is correct
18 Correct 1481 ms 74592 KB Output is correct
19 Correct 733 ms 52844 KB Output is correct
20 Correct 1677 ms 87328 KB Output is correct
21 Correct 1595 ms 75804 KB Output is correct
22 Correct 3934 ms 192704 KB Output is correct
23 Correct 3776 ms 197336 KB Output is correct
24 Correct 5772 ms 263540 KB Output is correct
25 Correct 5251 ms 266616 KB Output is correct
26 Correct 5010 ms 263772 KB Output is correct
27 Correct 6329 ms 331592 KB Output is correct
28 Correct 1976 ms 94080 KB Output is correct
29 Correct 4948 ms 263840 KB Output is correct
30 Correct 4937 ms 264184 KB Output is correct
31 Correct 5080 ms 263760 KB Output is correct
32 Correct 1895 ms 88032 KB Output is correct
33 Correct 929 ms 53232 KB Output is correct
34 Correct 1277 ms 67704 KB Output is correct
35 Correct 1289 ms 68476 KB Output is correct
36 Correct 1527 ms 73336 KB Output is correct
37 Correct 1556 ms 73208 KB Output is correct