oj.uz

Submission #129201

# Submission time Handle Problem Language Result Execution time Memory
129201 2019-07-11T20:14:17 Z qkxwsm Collapse (JOI18_collapse) C++14
30 / 100
 156 ms 29420 KB 
#include <bits/stdc++.h>
#include "collapse.h"

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define INF 1000000007
#define LLINF 2696969696969696969
#define MAXN 100013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, D, Q, B;
vector<array<int, 4> > segments;
map<int, int> med[MAXN];
int ans[MAXN];
vpi segs[3 * MAXN];
int dsu[MAXN], siz[MAXN];
vector<array<int, 3> > undo;
int cc;

void ins(int w, int L, int R, int a, int b, pii p)
{
	if (a <= L && R <= b)
	{
		segs[w].PB(p);
		return;
	}
	int mid = (L + R) >> 1;
	if (a <= mid) ins(w << 1, L, mid, a, b, p);
	if (mid < b) ins(w << 1 | 1, mid + 1, R, a, b, p);
}
int get(int u)
{
	return (u == dsu[u] ? u : get(dsu[u]));
}
void merge(int u, int v)
{
	u = get(u);
	v = get(v);
	if (u == v) return;
	if (siz[u] < siz[v]) swap(u, v);
	undo.PB({u, v, siz[u]});
	dsu[v] = u;
	siz[u] += siz[v];
	cc--;
	return;
}
void solve(int w, int L, int R)
{
	// cerr << "solve " << w << ' ' << L << ' ' << R << endl;
	for (pii p : segs[w])
	{
		merge(p.fi, p.se);
	}
	auto cur = undo; undo.clear();
	reverse(ALL(cur));
	if (L == R)
	{
		ans[L] = cc;
	}
	else
	{
		int mid = (L + R) >> 1;
		solve(w << 1, L, mid);
		solve(w << 1 | 1, mid + 1, R);
	}
	for (auto e : cur)
	{
		dsu[e[1]] = e[1];
		siz[e[0]] = e[2];
		cc++;
	}
	return;
}

vi simulateCollapse(int n, vi t, vi x, vi y, vi w, vi p)
{
	N = n; D = SZ(t); Q = SZ(w); B = p[0];
	FOR(i, 0, D)
	{
		int u = x[i], v = y[i]; if (u > v) swap(u, v);
		if (u <= B && B < v) continue;
		if (t[i])
		{
			segments[med[u][v]][3] = i - 1;
		}
		else
		{
			med[u][v] = SZ(segments);
			segments.PB({u, v, i, D - 1});
		}
	}
	for (auto e : segments)
	{
		// cerr << e[0] << " -> " << e[1] << " lasts " << e[2] << " " << e[3] << endl;
		ins(1, 0, D - 1, e[2], e[3], {e[0], e[1]});
	}
	cc = N;
	FOR(i, 0, N)
	{
		dsu[i] = i;
		siz[i] = 1;
	}
	solve(1, 0, D - 1);
	vi res(Q);
	// FOR(i, 0, D)
	// {
	// 	cerr << ans[i] << ' ';
	// }
	// cerr << endl;
	FOR(i, 0, Q)
	{
		res[i] = ans[w[i]];
	}
	return res;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12408 KB Output is correct
2 Incorrect 14 ms 12184 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 14072 KB Output is correct
2 Correct 41 ms 14072 KB Output is correct
3 Correct 92 ms 19524 KB Output is correct
4 Correct 39 ms 14072 KB Output is correct
5 Correct 109 ms 22384 KB Output is correct
6 Correct 46 ms 15480 KB Output is correct
7 Correct 133 ms 27728 KB Output is correct
8 Correct 118 ms 24176 KB Output is correct
9 Correct 43 ms 15608 KB Output is correct
10 Correct 46 ms 15608 KB Output is correct
11 Correct 48 ms 15992 KB Output is correct
12 Correct 137 ms 26172 KB Output is correct
13 Correct 156 ms 28012 KB Output is correct
14 Correct 151 ms 29420 KB Output is correct
15 Correct 145 ms 29164 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14072 KB Output is correct
2 Incorrect 39 ms 14492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12408 KB Output is correct
2 Incorrect 14 ms 12184 KB Output isn't correct
3 Halted 0 ms 0 KB -