oj.uz

Submission #74245

# Submission time Handle Problem Language Result Execution time Memory
74245 2018-08-30T15:08:11 Z kingpig9 Factories (JOI14_factories) C++11
18 / 100
 8000 ms 289292 KB 
#include <bits/stdc++.h>
#include "factories.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

//#define debug(...) fprintf(stderr, __VA_ARGS__)
#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

const int MAXN = 5e5 + 10;
const int MAXLG = 19;
const ll INF = 1e16;

void setmin (ll &a, ll b) {
	if (a > b) {
		a = b;
	}
}

int N;
#warning DON'T CONFUSE CENTROID DECOMPOSITION TREE WITH ORIGINAL TREE!!!!!!!
vector<int> adj[MAXN];
map<pii, ll> mpw;
//0 = white, 1 = red, 2 = blue
int par[MAXN][MAXLG];
int depth[MAXN];	//depth in terms of # of edges (ignoring the weights!)
ll droot[MAXN];	//dist to root
int ent[MAXN], exi[MAXN];

ll getw (int a, int b) {
	return mpw.at(minmax(a, b));
}

void dfslca (int x, int p, int de, ll dr) {
	static int cur = 0;
	ent[x] = cur++;

	depth[x] = de;
	droot[x] = dr;
	par[x][0] = p;
	for (int i = 1; i < MAXLG; i++) {
		int pp = par[x][i - 1];
		if (pp == -1) {
			break;
		}
		par[x][i] = par[pp][i - 1];
	}

	for (int y : adj[x]) {
		if (y != p) {
			dfslca(y, x, de + 1, dr + getw(x, y));
		}
	}

	exi[x] = cur;
}

int getpar (int x, int d) {
	for (int i = 0; d; i++, d >>= 1) {
		if (d & 1) {
			x = par[x][i];
		}
	}
	return x;
}

int lca (int x, int y) {
	if (depth[x] < depth[y]) {
		swap(x, y);
	}
	x = getpar(x, depth[x] - depth[y]);
	if (x == y) {
		return x;
	}

	for (int i = MAXLG - 1; i >= 0; i--) {
		if (par[x][i] != par[y][i]) {
			x = par[x][i];
			y = par[y][i];
		}
	}
	return par[x][0];
}

//might be a hint.
ll dist (int x, int y, int c = -1) {
	if (c == -1) {
		c = lca(x, y);
	}
	return droot[x] + droot[y] - 2 * droot[c];
}

void calc_lca() {
	fillchar(par, -1);
	dfslca(0, -1, 0, 0ll);
}

void Init (int nn, int a[], int b[], int d[]) {
	N = nn;
	for (int i = 0; i < N - 1; i++) {
		adj[a[i]].push_back(b[i]);
		adj[b[i]].push_back(a[i]);
		mpw[minmax(a[i], b[i])] = d[i];
	}
	calc_lca();
}

bool cmpo (int x, int y) {
	return ent[x] < ent[y];
}

bool insub (int x, int y) {
	return ent[x] < ent[y] && exi[y] <= exi[x];
}

int color[MAXN];
set<pll> cadj[MAXN];
vector<int> verts;
int vertsind;
ll ans;

void dfsv() {
	int x = verts[vertsind++];
	//debug("x = %d\n", x);
	while (vertsind < verts.size()) {
		int y = verts[vertsind];
		if (insub(x, y)) {
			ll d = dist(x, y);
			debug("cadj %d %d, dist = %lld\n", x, y, d);
			cadj[x].insert(pll(y, d));
			cadj[y].insert(pll(x, d));
			dfsv();
		} else {
			break;
		}
	}
}

int sub[MAXN];

int findsub (int x, int p) {
	sub[x] = 1;
	for (pll py : cadj[x]) {
		int y = py.fi;
		if (y != p) {
			sub[x] += findsub(y, x);
		}
	}
	debug("sub[%d] = %d\n", x, sub[x]);
	return sub[x];
}

int findcent (int x) {
	int s = findsub(x, -1);
	debug("sz %d is %d\n", x, s);
	int p = -1, cur = x;
	while (true) {
		bool ok = true;
		for (pll py : cadj[x]) {
			int y = py.fi;
			if (y != p) {
				if (sub[y] * 2 >= s) {
					p = cur;
					cur = y;
					ok = false;
					break;
				}
			}
		}

		if (ok) {
			return cur;
		}
	}
}

void dfsub (int x, int p, ll dr, ll &near1, ll &near2) {
	if (color[x] == 1) {
		setmin(near1, dr);
	} else if (color[x] == 2) {
		setmin(near2, dr);
	}

	for (pll py : cadj[x]) {
		int y = py.fi;
		if (y != p) {
			dfsub(y, x, dr + py.se, near1, near2);
		}
	}
}

void dfsc (int x) {
	int ff = x;
	x = findcent(x);
	debug("x = %d, centx = %d\n", ff, x);

	ll cnear1 = INF, cnear2 = INF;
	for (pll py : cadj[x]) {
		int y = py.fi;
		ll near1 = INF, near2 = INF;
		debug("me\n");
		dfsub(y, x, py.se, near1, near2);
		debug("g\n");
		debug("near1 = %lld, near2 = %lld\n", near1, near2);
		debug("cnear1 = %lld, cnear2 = %lld\n", cnear1, cnear2);

		setmin(ans, near1 + cnear2);
		setmin(ans, near2 + cnear1);
		
		if (color[x] == 1) {
			setmin(ans, near2);
		} else if (color[x] == 2) {
			setmin(ans, near1);
		}

		//At the end
		setmin(cnear1, near1);
		setmin(cnear2, near2);
	}

	//delete the ones
	while (!cadj[x].empty()) {
		int y = cadj[x].begin()->fi;
		//assert(cadj[y].lower_bound(pll(x, -1)) != cadj[y].end());
		debug("erase %d %d\n", x, y);
		cadj[y].erase(cadj[y].lower_bound(pll(x, -1)));
		cadj[x].erase(cadj[x].begin());
		dfsc(y);
	}
}

ll Query (int S, int X[], int T, int Y[]) {
	for (int i = 0; i < S; i++) {
		color[X[i]] = 1;
	}
	for (int i = 0; i < T; i++) {
		color[Y[i]] = 2;
	}
#warning DON'T RETURN UNTIL YOU RESET STUFF!!!
	for (int i = 0; i < S; i++) {
		verts.push_back(X[i]);
	}
	for (int i = 0; i < T; i++) {
		verts.push_back(Y[i]);
	}
	sort(all(verts), cmpo);
	for (int i = 0; i + 1 < S + T; i++) {
		verts.push_back(lca(verts[i], verts[i + 1]));
	}
	sort(all(verts), cmpo);
	verts.resize(unique(all(verts)) - verts.begin());

	vertsind = 0;
	dfsv();

	ans = INF;
	dfsc(verts[0]);

	//END
	verts.clear();
	for (int i = 0; i < S; i++) {
		color[X[i]] = 0;
	}
	for (int i = 0; i < T; i++) {
		color[Y[i]] = 0;
	}
	debug("------RETURN ANS---------\n");
	return ans;
}

Compilation message

factories.cpp:28:13: warning: missing terminating ' character
 #warning DON'T CONFUSE CENTROID DECOMPOSITION TREE WITH ORIGINAL TREE!!!!!!!
             ^
factories.cpp:28:2: warning: #warning DON'T CONFUSE CENTROID DECOMPOSITION TREE WITH ORIGINAL TREE!!!!!!! [-Wcpp]
 #warning DON'T CONFUSE CENTROID DECOMPOSITION TREE WITH ORIGINAL TREE!!!!!!!
  ^~~~~~~
factories.cpp:246:13: warning: missing terminating ' character
 #warning DON'T RETURN UNTIL YOU RESET STUFF!!!
             ^
factories.cpp:246:2: warning: #warning DON'T RETURN UNTIL YOU RESET STUFF!!! [-Wcpp]
 #warning DON'T RETURN UNTIL YOU RESET STUFF!!!
  ^~~~~~~
factories.cpp: In function 'void dfsv()':
factories.cpp:132:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (vertsind < verts.size()) {
         ~~~~~~~~~^~~~~~~~~~~~~~
factories.cpp: In function 'void dfsc(int)':
factories.cpp:200:6: warning: unused variable 'ff' [-Wunused-variable]
  int ff = x;
      ^~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 73392 KB Output is correct
2 Correct 3679 ms 91700 KB Output is correct
3 Correct 6831 ms 100940 KB Output is correct
4 Execution timed out 8096 ms 111028 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 111028 KB Output is correct
2 Correct 3421 ms 194332 KB Output is correct
3 Correct 4725 ms 215744 KB Output is correct
4 Correct 2627 ms 231944 KB Output is correct
5 Correct 4038 ms 289292 KB Output is correct
6 Correct 4922 ms 289292 KB Output is correct
7 Correct 4979 ms 289292 KB Output is correct
8 Correct 2075 ms 289292 KB Output is correct
9 Correct 3076 ms 289292 KB Output is correct
10 Correct 4499 ms 289292 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 73392 KB Output is correct
2 Correct 3679 ms 91700 KB Output is correct
3 Correct 6831 ms 100940 KB Output is correct
4 Execution timed out 8096 ms 111028 KB Time limit exceeded
5 Halted 0 ms 0 KB -