oj.uz

답안 #256873

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
256873 2020-08-03T10:48:25 Z TeaTime 공장들 (JOI14_factories) C++17
0 / 100
 3453 ms 220632 KB 
#include "factories.h"
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <tuple>
#include <random>
#include <cmath>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
 
const ll SZ = 5e5 + 10, INF = 1e9;
int sizes[SZ], x[SZ], y[SZ];
bool used[SZ];
vector<vector<pair<ll, ll>>> vec;
 
vector<vector<pair<ll, ll>>> gr;
ll curC = 0;
vector<ll> bst;
set<ll> u;
 
ll sz(int v, int dist = 0, int par = -1) {
	ll s = 1;
	vec[v].push_back({ curC, dist });
 
	for (auto to : gr[v]) {
		if (!used[to.first] && to.first != par) {
			s += sz(to.first, dist + to.second, v);
		}
	}
 
	sizes[v] = s;
	return s;
}
 
ll cntr(int v, int c, int par = -1) {
	for (auto to : gr[v]) {
		if (to.first != par && !used[to.first] && sizes[to.first] >= c / 2) {
			return cntr(to.first, c, v);
		}
	}
 
	return v;
}
 
void decomp(int v) {
	used[v] = 1;
	curC = v;
	sz(v);
 
	for (auto to : gr[v]) {
		if (!used[to.first]) {
			decomp(cntr(to.first, sizes[to.first]));
		}
	}
}
 
void Init(int N, int A[], int B[], int D[]) {
	gr.resize(N);
	vec.resize(N);
	for (int i = 0; i < N - 1; i++) {
		gr[A[i]].push_back({ B[i], D[i] });
		gr[B[i]].push_back({ A[i], D[i] });
	}
 
	bst.resize(N);
	for (auto &c : bst) c = INF;
	decomp(0);
}
 
long long Query(int S, int X[], int T, int Y[]) {
	for (int i = 0; i < S; i++) {
		ll ind = X[i];
		for (auto cur : vec[ind]) {
			u.insert(cur.first);
			bst[cur.first] = min(bst[cur.first], cur.second);
		}
	}
 
	ll ans = INF;
	for (int i = 0; i < T; i++) {
		ll ind = Y[i];
		for (auto cur : vec[ind]) {
			ans = min(ans, bst[cur.first] + cur.second);
		}
	}
	for (auto cur : u) bst[cur] = INF;
	u.clear();
	return ans;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 768 KB Output is correct
2 Incorrect 1022 ms 19652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 640 KB Output is correct
2 Incorrect 3453 ms 220632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 768 KB Output is correct
2 Incorrect 1022 ms 19652 KB Output isn't correct
3 Halted 0 ms 0 KB -