Submission #25265

#	Time	Username	Problem	Language	Result	Execution time	Memory
25265		dotorya	Factories (JOI14_factories)	C++14	15 / 100	6000 ms	303528 KiB

factories

#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
//#include <unordered_map>  
//#include <unordered_set>  
#include <vector>  

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")  
using namespace std;

#define mp make_pair  
#define Fi first  
#define Se second  
#define pb(x) push_back(x)  
#define szz(x) ((int)(x).size())  
#define rep(i, n) for(int i=0;i<n;i++)  
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble  

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 17;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;

#include "factories.h"

bool dchk[500050];
int dep[500050];
int lr[500050][2];
ll par[500050][20][2];
int tus;
vector <pll> conn[500050];
void DFS(int n) {
	dchk[n] = true;
	lr[n][0] = ++tus;
	for (auto it : conn[n]) {
		if (dchk[it.second]) continue;
		par[it.second][0][0] = n, par[it.second][0][1] = it.first;
		for (int i = 1; i <= 19; i++) {
			int tp = par[it.second][i - 1][0];
			par[it.second][i][0] = par[tp][i - 1][0];
			par[it.second][i][1] = par[it.second][i - 1][1] + par[tp][i - 1][1];
		}
		dep[it.second] = dep[n] + 1;
		DFS(it.second);
	}
	lr[n][1] = tus;
}
pll lca(int a, int b) {
	pll rv = pll(0, 0);
	if (dep[a] > dep[b]) swap(a, b);
	int c = dep[b] - dep[a];
	for (int i = 19; i >= 0; i--) {
		if (c & (1 << i)) {
			rv.first += par[b][i][1];
			b = par[b][i][0];
		}
	}
	if (a == b) return pll(rv.first, a);

	for (int i = 19; i >= 0; i--) {
		if (par[a][i][0] != par[b][i][0]) {
			rv.first += par[a][i][1];
			rv.first += par[b][i][1];
			a = par[a][i][0];
			b = par[b][i][0];
		}
	}
	rv.first += par[a][0][1];
	rv.first += par[b][0][1];
	return pll(rv.first, par[a][0][0]);
}
void Init(int N, int A[], int B[], int D[]) {
	int i, j;
	for (i = 0; i <= N - 2; i++) {
		conn[A[i]].emplace_back(D[i], B[i]);
		conn[B[i]].emplace_back(D[i], A[i]);
	}

	tus = 0;
	DFS(0);
}

class Node {
public:
	ll mn, v;
	Node() {
		*this = Node(0, 0);
	}
	Node(ll mn, ll v) : mn(mn), v(v) {}
};
Node indt[1100000];
void propagate(int n) {
	indt[2 * n].v += indt[n].v;
	indt[2 * n].mn += indt[n].v;
	indt[2 * n + 1].v += indt[n].v;
	indt[2 * n + 1].mn += indt[n].v;
	indt[n].v = 0;
}
void update(int st, int en, int S, int E, int n, ll v) {
	if (st > en) return;
	if (st == S && en == E) {
		indt[n].v += v;
		indt[n].mn += v;
		return;
	}
	propagate(n);

	int M = (S + E) / 2;
	update(st, min(en, M), S, M, 2 * n, v);
	update(max(M + 1, st), en, M + 1, E, 2 * n + 1, v);
	indt[n].mn = min(indt[2 * n].mn, indt[2 * n + 1].mn);
}
ll getmn(int st, int en, int S, int E, int n) {
	if (st > en) return LL_INF;
	if (st == S && en == E) return indt[n].mn;
	propagate(n);

	int M = (S + E) / 2;
	return min(getmn(st, min(en, M), S, M, 2 * n), getmn(max(st, M + 1), en, M + 1, E, 2 * n + 1));
}

ll qans;
vector <int> Vv;
vector <pll> conn2[500050];
vector <pll> son2[500050];
ll dis[500050];
int lr2[500050][2];
int tchk[500050];
void DFS2(int n) {
	dchk[n] = true;
	lr2[n][0] = ++tus;
	for (auto it : conn2[n]) {
		if (dchk[it.second]) continue;
		son2[n].push_back(it);
		dis[it.second] = dis[n] + it.first;
		DFS2(it.second);
	}
	lr2[n][1] = tus;
}
void DFS3(int n) {
	if (tchk[n] == 1) qans = min(qans, getmn(1, Vv.size(), 1, IT_MAX, 1));
	for (auto it : son2[n]) {
		update(1, Vv.size(), 1, IT_MAX, 1, it.first);
		update(lr2[it.second][0], lr2[it.second][1], 1, IT_MAX, 1, -2 * it.first);
		DFS3(it.second);
		update(1, Vv.size(), 1, IT_MAX, 1, -it.first);
		update(lr2[it.second][0], lr2[it.second][1], 1, IT_MAX, 1, 2 * it.first);
	}
}
long long Query(int S, int X[], int T, int Y[]) {
	int i, j;
	for (i = 0; i < S; i++) Vv.push_back(X[i]);
	for (i = 0; i < T; i++) Vv.push_back(Y[i]);
	sort(all(Vv), [](int a, int b) {
		return lr[a][0] < lr[b][0];
	});

	vector <int> Vv2;
	for (i = 0; i + 1 < Vv.size(); i++) Vv2.push_back(lca(Vv[i], Vv[i + 1]).second);
	for (auto it : Vv2) Vv.push_back(it);
	sort(all(Vv), [](int a, int b) {
		return lr[a][0] < lr[b][0];
	});
	Vv.erase(unique(all(Vv)), Vv.end());
	for (auto it : Vv) tchk[it] = 0;
	for (i = 0; i < S; i++) tchk[X[i]] = 1;
	for (i = 0; i < T; i++) tchk[Y[i]] = -1;

	for (i = 0; i + 1 < Vv.size(); i++) {
		int x = Vv[i];
		int y = Vv[i + 1];
		x = lca(x, y).second;
		pll u = lca(x, y);
		conn2[x].emplace_back(u.first, y);
		conn2[y].emplace_back(u.first, x);
	}

	for (i = 0; i < Vv.size(); i++) {
		dchk[Vv[i]] = false;
		dis[Vv[i]] = 0;
	}
	tus = 0;
	DFS2(Vv[0]);
	for (IT_MAX = 2; IT_MAX <= Vv.size(); IT_MAX *= 2);
	for (i = 1; i < 2 * IT_MAX; i++) indt[i] = Node(0, 0);
	for (i = 0; i < Vv.size(); i++) {
		ll v = dis[Vv[i]];
		if (tchk[Vv[i]] != -1) v = LL_INF;
		update(lr2[Vv[i]][0], lr2[Vv[i]][0], 1, IT_MAX, 1, v);
	}
	qans = LL_INF;
	DFS3(Vv[0]);

	for (auto it : Vv) {
		conn2[it].clear();
		son2[it].clear();
	}
	Vv.clear();
	return qans;
}

Compilation message (stderr)

factories.cpp:23:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable:4996)  
 ^
factories.cpp:24:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/STACK:336777216")  
 ^
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:102:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:188:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i + 1 < Vv.size(); i++) Vv2.push_back(lca(Vv[i], Vv[i + 1]).second);
                    ^
factories.cpp:198:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i + 1 < Vv.size(); i++) {
                    ^
factories.cpp:207:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < Vv.size(); i++) {
                ^
factories.cpp:213:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (IT_MAX = 2; IT_MAX <= Vv.size(); IT_MAX *= 2);
                          ^
factories.cpp:215:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < Vv.size(); i++) {
                ^
factories.cpp:180:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^

• Subtask 1: 15 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67