oj.uz

Submission #25354

# Submission time Handle Problem Language Result Execution time Memory
25354 2017-06-21T09:58:03 Z kdh9949 Factories (JOI14_factories) C++14
33 / 100
 6000 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 6 ms 123900 KB Output is correct
2 Correct 373 ms 124164 KB Output is correct
3 Correct 393 ms 124164 KB Output is correct
4 Correct 453 ms 124164 KB Output is correct
5 Correct 463 ms 124112 KB Output is correct
6 Correct 339 ms 124200 KB Output is correct
7 Correct 459 ms 124164 KB Output is correct
8 Correct 403 ms 124164 KB Output is correct
9 Correct 479 ms 124116 KB Output is correct
10 Correct 299 ms 124200 KB Output is correct
11 Correct 503 ms 124164 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 123900 KB Output is correct
2 Correct 2793 ms 142644 KB Output is correct
3 Correct 4349 ms 144724 KB Output is correct
4 Correct 876 ms 143612 KB Output is correct
5 Correct 5796 ms 159488 KB Output is correct
6 Correct 4116 ms 144400 KB Output is correct
7 Correct 986 ms 127972 KB Output is correct
8 Correct 449 ms 128132 KB Output is correct
9 Correct 1246 ms 130068 KB Output is correct
10 Correct 1079 ms 127904 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 3056 ms 142644 KB Output is correct
2 Correct 3163 ms 142644 KB Output is correct
3 Correct 4639 ms 143984 KB Output is correct
4 Correct 5203 ms 144412 KB Output is correct
5 Correct 5466 ms 144312 KB Output is correct
6 Execution timed out 6000 ms 155152 KB Execution timed out
7 Halted 0 ms 0 KB -