oj.uz

Submission #25542

# Submission time Handle Problem Language Result Execution time Memory
25542 2017-06-23T00:42:51 Z kdh9949 Factories (JOI14_factories) C++14
100 / 100
 5879 ms 159488 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct E{ int x, d; };

const ll inf = 1e18;
int n, q, c[500010], s[500010], p[500010], d[500010], bc[500010];
ll md[19][500010], bd[500010];
vector<E> e[500010];

int sf(int x, int p){
	s[x] = 1;
	for(auto &i : e[x]) if(!c[i.x] && i.x != p) s[x] += sf(i.x, x);
	return s[x];
}

int cf(int x, int p, int t){
	for(auto &i : e[x])
		if(!c[i.x] && i.x != p && s[i.x] > t / 2) return cf(i.x, x, t);
	return x;
}

void g(int x, int p, int d, ll v){
	md[d][x] = v;
	for(auto &i : e[x]) if(!c[i.x] && i.x != p) g(i.x, x, d, v + i.d);
}

int f(int x, int de){
	x = cf(x, 0, sf(x, 0));
	d[x] = de;
	c[x] = 1;
	for(auto &i : e[x]){
		if(c[i.x]) continue;
		g(i.x, x, de, i.d);
		p[f(i.x, de + 1)] = x;
	}
	return x;
}

ll upd(int x, int g){
	ll ret = inf;
	for(int t = x, u = d[x]; t; t = p[t], u--){
		if(!g && (bc[t] != q || bd[t] > md[u][x])){
			bd[t] = md[u][x];
			bc[t] = q;
		}
		else if(g && bc[t] == q){
			ret = min(ret, bd[t] + md[u][x]);
		}
	}
	return ret;
}

void Init(int N, int A[], int B[], int D[]){
	n = N;
	for(int i = 0, x, y, z; i < n - 1; i++){
		x = A[i] + 1; y = B[i] + 1; z = D[i];
		e[x].push_back({y, z});
		e[y].push_back({x, z});
	}
	f(1, 0);
}

ll Query(int S, int X[], int T, int Y[]){
	q++;
	for(int i = 0; i < S; i++) upd(X[i] + 1, 0);
	ll ret = inf;
	for(int i = 0; i < T; i++) ret = min(ret, upd(Y[i] + 1, 1));
	return ret;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 123900 KB Output is correct
2 Correct 343 ms 124164 KB Output is correct
3 Correct 466 ms 124164 KB Output is correct
4 Correct 416 ms 124164 KB Output is correct
5 Correct 536 ms 124116 KB Output is correct
6 Correct 306 ms 124200 KB Output is correct
7 Correct 483 ms 124164 KB Output is correct
8 Correct 466 ms 124164 KB Output is correct
9 Correct 473 ms 124120 KB Output is correct
10 Correct 373 ms 124200 KB Output is correct
11 Correct 439 ms 124164 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 123900 KB Output is correct
2 Correct 2549 ms 142644 KB Output is correct
3 Correct 4093 ms 144720 KB Output is correct
4 Correct 916 ms 143612 KB Output is correct
5 Correct 5739 ms 159488 KB Output is correct
6 Correct 4586 ms 144400 KB Output is correct
7 Correct 1579 ms 127972 KB Output is correct
8 Correct 523 ms 128132 KB Output is correct
9 Correct 1553 ms 130068 KB Output is correct
10 Correct 1493 ms 127900 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 3089 ms 142644 KB Output is correct
2 Correct 2959 ms 142644 KB Output is correct
3 Correct 4026 ms 143984 KB Output is correct
4 Correct 4293 ms 144412 KB Output is correct
5 Correct 4529 ms 144312 KB Output is correct
6 Correct 5879 ms 155156 KB Output is correct
7 Correct 1106 ms 143612 KB Output is correct
8 Correct 4829 ms 144036 KB Output is correct
9 Correct 4923 ms 143832 KB Output is correct
10 Correct 3829 ms 144064 KB Output is correct
11 Correct 1186 ms 130068 KB Output is correct
12 Correct 469 ms 128132 KB Output is correct
13 Correct 736 ms 127596 KB Output is correct
14 Correct 899 ms 127596 KB Output is correct
15 Correct 1309 ms 127904 KB Output is correct
16 Correct 1569 ms 127896 KB Output is correct