oj.uz

Submission #25283

# Submission time Handle Problem Language Result Execution time Memory
25283 2017-06-21T05:51:14 Z 김동현(#1058) Factories (JOI14_factories) C++14
15 / 100
 6000 ms 114884 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct E{
	int x; ll d;
	bool operator<(const E &oth) const {
		return d > oth.d;
	}
};

const ll inf = 1e18;
int n, c[500010], d[500010], sp[19][500010];
ll dd[500010], md[500010];
vector<E> e[500010];
priority_queue<E> pq;

void dfs(int x, int p, int de, ll dde){
	sp[0][x] = p;
	d[x] = de;
	dd[x] = dde;
	for(int i = 1; i < 19; i++) sp[i][x] = sp[i - 1][sp[i - 1][x]];
	for(auto &i : e[x]){
		if(i.x != p) dfs(i.x, x, de + 1, dde + i.d);
	}
}

int lca(int x, int y){
	if(d[x] < d[y]) swap(x, y);
	for(int i = 18; i >= 0; i--){
		if(d[sp[i][x]] >= d[y]) x = sp[i][x];
	}
	if(x == y) return x;
	for(int i = 18; i >= 0; i--){
		if(sp[i][x] && sp[i][y] && sp[i][x] != sp[i][y]){
			x = sp[i][x];
			y = sp[i][y];
		}
	}
	return sp[0][x];
}

ll dis(int x, int y){
	return dd[x] + dd[y] - 2 * dd[lca(x, y)];
}

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});
	}
	dfs(1, 0, 1, 0);
}

ll f(int x, int a[], int y, int b[]){
	fill(md + 1, md + n + 1, inf);
	fill(c + 1, c + n + 1, 0);
	for(int i = 0; i < x; i++){ pq.push({a[i] + 1, 0}); md[a[i] + 1] = 0; }
	while(!pq.empty()){
		E cur = pq.top(); pq.pop();
		for(auto &i : e[cur.x]){
			ll nd = cur.d + i.d;
			if(md[i.x] > nd){
				md[i.x] = nd;
				pq.push({i.x, nd});
			}
		}
	}
	ll ret = inf;
	for(int i = 0; i < y; i++) ret = min(ret, md[b[i] + 1]);
	return ret;
}

ll g(int x, int a[], int y, int b[]){
	ll ret = inf;
	for(int i = 0; i < x; i++){
		for(int j = 0; j < y; j++){
			ret = min(ret, dis(a[i] + 1, b[j] + 1));
		}
	}
	return ret;
}

ll Query(int S, int X[], int T, int Y[]) {
	if(1LL * S * T > n + S + T) return f(S, X, T, Y);
	else return g(S, X, T, Y);
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 84836 KB Output is correct
2 Correct 1079 ms 85232 KB Output is correct
3 Correct 2996 ms 85100 KB Output is correct
4 Correct 1163 ms 85380 KB Output is correct
5 Correct 1113 ms 85388 KB Output is correct
6 Correct 1086 ms 85400 KB Output is correct
7 Correct 2933 ms 85100 KB Output is correct
8 Correct 1096 ms 85100 KB Output is correct
9 Correct 1086 ms 85388 KB Output is correct
10 Correct 996 ms 85400 KB Output is correct
11 Correct 3006 ms 85100 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 84836 KB Output is correct
2 Correct 5306 ms 110444 KB Output is correct
3 Execution timed out 6000 ms 114884 KB Execution timed out
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6000 ms 113644 KB Execution timed out
2 Halted 0 ms 0 KB -