oj.uz

Submission #52211

# Submission time Handle Problem Language Result Execution time Memory
52211 2018-06-25T04:58:40 Z 윤교준(#1348) Factories (JOI14_factories) C++11
33 / 100
 6000 ms 510052 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define pb push_back
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
void fg(vector<pii> G[], int a, int b, int c) { G[a].pb({b, c}); G[b].pb({a, c}); }
void fg(vector<int> G[], int a, int b) { G[a].pb(b); G[b].pb(a); }
void init();

const int MAXN = 500005;

vector<pii> G[MAXN];

int prt[MAXN][19];
ll dl[MAXN];
int dep[MAXN], dfsi[MAXN];

int A[MAXN], B[MAXN], C[MAXN];

int N;

int lca(int a, int b) {
	if(dep[a] > dep[b]) swap(a, b);
	int dt = dep[b] - dep[a];
	for(int i = 0; i < 19; i++) if(dt & (1<<i))
		b = prt[b][i];
	if(a == b) return a;
	for(int i = 18; ~i; i--) if(prt[a][i] != prt[b][i]) {
		a = prt[a][i]; b = prt[b][i];
	}
	return prt[a][0];
}

void dfs(int idx, int &c) {
	for(pii e : G[idx]) {
		int v = e.first;
		if(dep[v]) continue;
		dep[v] = dep[idx] + 1;
		dl[v] = dl[idx] + e.second;
		prt[v][0] = idx;
		dfs(v, c);
	}
	c++; dfsi[idx] = c;
}

void Init(int N, int A[], int B[], int D[]) {
	::N = N;
	for(int i = 0; i < N-1; i++) {
		::A[i+1] = A[i]+1;
		::B[i+1] = B[i]+1;
		::C[i+1] = D[i];
		fg(G, A[i]+1, B[i]+1, D[i]);
	}
	init();
}

vector<int> SG[MAXN];

ll mnt1[MAXN], mnt2[MAXN];
int TV[MAXN], TL[MAXN], TLO[MAXN];
int ud[MAXN];
int typ[MAXN];

ll Ans;

void f(int idx) {
	if(1 == typ[idx]) mnt1[idx] = 0;
	if(2 == typ[idx]) mnt2[idx] = 0;

	for(int v : SG[idx]) if(dfsi[v] < dfsi[idx]) {
		f(v);

		ll l = dl[v] - dl[idx];
		upmin(Ans, mnt1[idx] + mnt2[v] + l);
		upmin(Ans, mnt1[v] + mnt2[idx] + l);
		upmin(mnt1[idx], mnt1[v] + l);
		upmin(mnt2[idx], mnt2[v] + l);
	}
}

int uf(int i) { return ud[i] == i ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) { ud[uf(b)] = uf(a); }
long long Query(int Xn, int X[], int Yn, int Y[]) {
	Ans = INFLL;

	for(int i = 0; i < Xn; i++) X[i]++;
	for(int i = 0; i < Yn; i++) Y[i]++;

	for(int i = 0; i < Xn; i++) typ[X[i]] = 1;
	for(int i = 0; i < Yn; i++) typ[Y[i]] = 2;
	
	for(int i = 0; i < Xn; i++) TV[i] = X[i];
	for(int i = 0; i < Yn; i++) TV[Xn+i] = Y[i];
	sort(TV, TV+Xn+Yn, [&](int a, int b) {
		return dfsi[a] < dfsi[b];
	});

	for(int i = 1; i < Xn+Yn; i++)
		TL[i] = lca(TV[i-1], TV[i]);
	
	iota(TLO, TLO+Xn+Yn, 0);
	sort(TLO+1, TLO+Xn+Yn, [&](int a, int b) {
		return TL[a] == TL[b] ? a < b : dfsi[TL[a]] < dfsi[TL[b]];
	});

	for(int oi = 1; oi < Xn+Yn; oi++) {
		int idx = TLO[oi];
		int a = TV[idx-1], b = TV[idx];
		a = uf(a); b = uf(b);
		if(a == b) continue;
		if(a == TL[idx]) {
			fg(SG, a, b);
			uf(a, b);
		} else if(b == TL[idx]) {
			fg(SG, a, b);
			uf(b, a);
		} else {
			fg(SG, a, TL[idx]);
			fg(SG, b, TL[idx]);
			uf(TL[idx], a);
			uf(TL[idx], b);
		}
	}

	int ridx = TL[TLO[Xn+Yn-1]];

	f(ridx);

	

	for(int i = 0; i < Xn; i++) typ[X[i]] = 0;
	for(int i = 0; i < Yn; i++) typ[Y[i]] = 0;
	for(int i = 0; i < Xn+Yn; i++) ud[TV[i]] = TV[i];
	for(int i = 1; i < Xn+Yn; i++) ud[TL[i]] = TL[i];
	for(int i = 0; i < Xn+Yn; i++) SG[TV[i]].clear();
	for(int i = 1; i < Xn+Yn; i++) SG[TL[i]].clear();
	for(int i = 0; i < Xn+Yn; i++) mnt1[TV[i]] = mnt2[TV[i]] = INFLL;
	for(int i = 1; i < Xn+Yn; i++) mnt1[TL[i]] = mnt2[TL[i]] = INFLL;

	return Ans;
}

void init() {
	{
		int c = 0;
		dep[1] = 1;
		dfs(1, c);
	}
	for(int j = 1; j < 19; j++) for(int i = 1; i <= N; i++)
		prt[i][j] = prt[prt[i][j-1]][j-1];
	
	iota(ud, ud+MAXN, 0);
	fill(mnt1, mnt1+MAXN, INFLL);
	fill(mnt2, mnt2+MAXN, INFLL);
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 34040 KB Output is correct
2 Correct 1085 ms 42684 KB Output is correct
3 Correct 1152 ms 42992 KB Output is correct
4 Correct 1027 ms 43060 KB Output is correct
5 Correct 833 ms 43092 KB Output is correct
6 Correct 860 ms 43092 KB Output is correct
7 Correct 1159 ms 43092 KB Output is correct
8 Correct 1041 ms 43096 KB Output is correct
9 Correct 881 ms 43216 KB Output is correct
10 Correct 745 ms 43216 KB Output is correct
11 Correct 1050 ms 43216 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 43216 KB Output is correct
2 Correct 2448 ms 132236 KB Output is correct
3 Correct 3225 ms 150168 KB Output is correct
4 Correct 1954 ms 169092 KB Output is correct
5 Correct 3089 ms 204460 KB Output is correct
6 Correct 3744 ms 207840 KB Output is correct
7 Correct 3045 ms 207840 KB Output is correct
8 Correct 1733 ms 207840 KB Output is correct
9 Correct 2586 ms 207840 KB Output is correct
10 Correct 2863 ms 207840 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 34040 KB Output is correct
2 Correct 1085 ms 42684 KB Output is correct
3 Correct 1152 ms 42992 KB Output is correct
4 Correct 1027 ms 43060 KB Output is correct
5 Correct 833 ms 43092 KB Output is correct
6 Correct 860 ms 43092 KB Output is correct
7 Correct 1159 ms 43092 KB Output is correct
8 Correct 1041 ms 43096 KB Output is correct
9 Correct 881 ms 43216 KB Output is correct
10 Correct 745 ms 43216 KB Output is correct
11 Correct 1050 ms 43216 KB Output is correct
12 Correct 32 ms 43216 KB Output is correct
13 Correct 2448 ms 132236 KB Output is correct
14 Correct 3225 ms 150168 KB Output is correct
15 Correct 1954 ms 169092 KB Output is correct
16 Correct 3089 ms 204460 KB Output is correct
17 Correct 3744 ms 207840 KB Output is correct
18 Correct 3045 ms 207840 KB Output is correct
19 Correct 1733 ms 207840 KB Output is correct
20 Correct 2586 ms 207840 KB Output is correct
21 Correct 2863 ms 207840 KB Output is correct
22 Correct 4284 ms 290304 KB Output is correct
23 Correct 3835 ms 317376 KB Output is correct
24 Correct 4589 ms 340092 KB Output is correct
25 Correct 4852 ms 367996 KB Output is correct
26 Correct 5004 ms 387920 KB Output is correct
27 Correct 4124 ms 428032 KB Output is correct
28 Correct 3035 ms 440868 KB Output is correct
29 Correct 5157 ms 461380 KB Output is correct
30 Correct 5322 ms 485292 KB Output is correct
31 Execution timed out 6016 ms 510052 KB Time limit exceeded
32 Halted 0 ms 0 KB -