oj.uz

답안 #302449

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
302449 2020-09-18T17:09:05 Z hexan 공장들 (JOI14_factories) C++14
0 / 100
 24 ms 24192 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define all(x) (x).begin(), (x).end()
#define size(x) (ll)x.size()
#define x first
#define y second
#define chkmax(x, y) x = max(x, y)
#define chkmin(x, y) x = min(x, y)

const int N = 5e5 + 1;
const int lg = 20;
vector<pair<int, int>> g[N];
vector<int> nxt[N];
int dist[N];
int p[N];
ll w[N];
int root = -1;

void kek(int x, int p) {
	for(auto to : g[x]) {
		if (to.x == p) continue;
		w[to.x] = w[x] + to.y;
		kek(to.x, x);
	}
}

int dfs(int v, int pa, int &c, int n) {
	int sz = 1;
	for(auto to : g[v]) {
		if (to.x == pa || p[to.x] != -1) continue;
		sz += dfs(to.x, v, c, n);
	}
	if (c == -1 && (sz * 2 >=  n || pa == -1))
		c = v;
	return sz;
}

void dec(int v, int n) {
	for(auto to : g[v]) {
		if (p[to.x] == -1) {
			int nx = -1;
			dfs(to.x, -1, nx, n / 2);
			nxt[v].push_back(nx);
			p[nx] = v;
			dec(nx, n / 2);
		}
	}
}

int n;
const ll INF = 1e18;
ll used[2][N], f[2][N];

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for(int i = 0; i < n - 1; i++) {
		//--A[i]; --B[i];
		g[A[i]].emplace_back(B[i], D[i]);
		g[B[i]].emplace_back(A[i], D[i]);
	}
	fill(p, p + N, -1);
	dfs(0, -1, root, n);
	p[root] = root;
	dec(root, N);
	for(int i = 0; i < 2; i++) {
		for(int j = 0; j < n; j++) {
			f[i][j] = INF;
		}
	}
	kek(root, -1);
}


int timer = 0;

ll ans;

long long Query(int S, int X[], int T, int Y[]) {
	timer++;	
	ans = INF;
	for(int i : {0, 1}) {
		for(int j = 0; j < (i == 0 ? S : T); j++) {
			int x;
			if (!i) x = X[j];
			else x = Y[j];
			ll st = x;
			ll val = w[x];
			while (1) {
				if (used[i][x] != timer) {
					used[i][x] = timer;
					f[i][x] = INF;
				}
				f[i][x] = min(f[i][x], abs(val - w[x]));
				chkmin(ans, f[0][x] + f[1][x]);
				if (p[x] != x) {
					x = p[x];
				} else {
					break;
				}
			}
		}
	}	
	return ans;
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:91:7: warning: unused variable 'st' [-Wunused-variable]
   91 |    ll st = x;
      |       ^~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 24192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 23936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 24 ms 24192 KB Output isn't correct
2 Halted 0 ms 0 KB -