oj.uz

Submission #25293

# Submission time Handle Problem Language Result Execution time Memory
25293 2017-06-21T05:59:20 Z 김동현(#1058) Factories (JOI14_factories) C++14
15 / 100
 6000 ms 114880 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];

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);
	}
}

ll dis(int x, int y){
	ll ret = dd[x] + dd[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 ret - 2 * dd[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 ret - 2 * dd[sp[0][x]];
}

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);
	priority_queue<E> pq;
	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();
		if(c[cur.x]) return md[cur.x];
		if(cur.d > md[cur.x]) continue;
		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(S <= 10 && T <= 10) return g(S, X, T, Y);
	if(1LL * S * T > n + S + T) return f(S, X, T, Y);
	return g(S, X, T, Y);
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 84836 KB Output is correct
2 Correct 1123 ms 85232 KB Output is correct
3 Correct 3003 ms 85100 KB Output is correct
4 Correct 1069 ms 85440 KB Output is correct
5 Correct 983 ms 85384 KB Output is correct
6 Correct 1139 ms 85460 KB Output is correct
7 Correct 2979 ms 85100 KB Output is correct
8 Correct 1016 ms 85100 KB Output is correct
9 Correct 1049 ms 85388 KB Output is correct
10 Correct 1056 ms 85460 KB Output is correct
11 Correct 3016 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 4679 ms 110444 KB Output is correct
3 Execution timed out 6000 ms 114880 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 114660 KB Execution timed out
2 Halted 0 ms 0 KB -