oj.uz

Submission #129658

# Submission time Handle Problem Language Result Execution time Memory
129658 2019-07-12T22:38:05 Z qkxwsm Collapse (JOI18_collapse) C++14
65 / 100
 15000 ms 312612 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 400013
#define MAGIC 521

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, Q;
vi ans;
vector<array<int, 4> > events;
int die[MAXN];
vi ord, cand;
vi ch[MAXN];
map<int, int> rec[MAXN];

struct dsu
{
	int dsu[MAXN], siz[MAXN];
	vi edits;
	void init()
	{
		FOR(i, 0, N)
		{
			dsu[i] = i;
			siz[i] = 1;
		}
	}
	void rollback()
	{
		for (int u : edits)
		{
			dsu[u] = u;
			siz[u] = 1;
		}
		edits.clear();
	}
	int get(int u)
	{
		return (u == dsu[u] ? u : dsu[u] = get(dsu[u]));
	}
	bool merge(int u, int v)
	{
		u = get(u); v = get(v);
		if (u == v) return false;
		if (siz[u] > siz[v]) swap(u, v);
		siz[v] += siz[u];
		dsu[u] = v;
		edits.PB(u);
		return true;
	}
};

dsu D[2];

bool cmp(int a, int b)
{
	return events[a][2] < events[b][2];
}

void proc(int l, int r)
{
	//build the set of edges now!
	D[0].init(); D[1].init();
	cand.clear(); ord.clear();
	FOR(i, 0, N)
	{
		ch[i].clear();
	}
	FOR(i, l, r + 1)
	{
		if (events[i][1] == 2)
		{
			ord.PB(i);
		}
	}
	sort(ALL(ord), cmp);
	FOR(i, 0, l)
	{
		if (events[i][1] != 0) continue;
		int u = events[i][2], v = events[i][3];
		if (die[i] <= r) cand.PB(i);
		else
		{
			ch[v].PB(u);
		}
	}
	int cc = 0, cp = 0;
	for (int p : ord)
	{
		int u = events[p][2], qid = events[p][3], t = events[p][0];
		while(cp <= u)
		{
			cc++;
			for (int v : ch[cp])
			{
				if (D[0].merge(cp, v)) cc--;
			}
			cp++;
		}
		int res = cc;
		for (int x : cand)
		{
			int v = events[x][2], w = events[x][3];
			if (die[x] > t && w <= u)
			{
				v = D[0].get(v); w = D[0].get(w);
				if (D[1].merge(v, w)) res--;
			}
		}
		FOR(j, l, p)
		{
			if (events[j][1] != 0) continue;
			int v = events[j][2], w = events[j][3];
			if (die[j] > t && w <= u)
			{
				v = D[0].get(v); w = D[0].get(w);
				if (D[1].merge(v, w)) res--;
			}
		}
		D[1].rollback();
		ans[qid] += res;
	}
	return;
}
void solve()
{
	FOR(i, 0, N) rec[i].clear();
	FOR(i, 0, SZ(events))
	{
		if (events[i][1] == 2) continue;
		if (events[i][1] == 0)
		{
			rec[events[i][2]][events[i][3]] = i;
			die[i] = SZ(events);
		}
		else
		{
			die[rec[events[i][2]][events[i][3]]] = i;
		}
	}
	for (int i = 0; i < SZ(events); i += MAGIC)
	{
		proc(i, min(i + MAGIC, SZ(events)) - 1);
	}
}
vi simulateCollapse(int n, vi t, vi x, vi y, vi w, vi p)
{
	N = n; Q = SZ(w);
	ans.resize(Q);
	FOR(i, 0, SZ(t))
	{
		if (x[i] > y[i]) swap(x[i], y[i]);
		events.PB({i, t[i], x[i], y[i]});
	}
	FOR(i, 0, Q)
	{
		events.PB({w[i], 2, p[i], i});
	}
	sort(ALL(events));
	FOR(i, 0, SZ(events))
	{
		events[i][0] = i;
	}
	//hm ok each edge has a birth and death time.
	solve();
	for (auto &e : events)
	{
		if (e[1] == 2)
		{
			e[2] = N - 2 - e[2];
		}
		else
		{
			e[2] = N - 1 - e[2];
			e[3] = N - 1 - e[3];
			swap(e[2], e[3]);
		}
	}
	solve();
	return ans;
	//event: disconnect u -> v, connect u -> v, ask qid x pos y: so you store time, typ, who it happens to
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 29304 KB Output is correct
2 Correct 34 ms 28920 KB Output is correct
3 Correct 34 ms 28920 KB Output is correct
4 Correct 34 ms 28920 KB Output is correct
5 Correct 65 ms 29176 KB Output is correct
6 Correct 49 ms 29300 KB Output is correct
7 Correct 34 ms 28920 KB Output is correct
8 Correct 35 ms 28920 KB Output is correct
9 Correct 68 ms 29276 KB Output is correct
10 Correct 73 ms 29428 KB Output is correct
11 Correct 59 ms 30112 KB Output is correct
12 Correct 56 ms 30068 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 33004 KB Output is correct
2 Correct 192 ms 33060 KB Output is correct
3 Correct 13868 ms 39024 KB Output is correct
4 Correct 189 ms 33256 KB Output is correct
5 Correct 13787 ms 38552 KB Output is correct
6 Correct 242 ms 34284 KB Output is correct
7 Correct 1006 ms 45632 KB Output is correct
8 Correct 14073 ms 40824 KB Output is correct
9 Correct 415 ms 34920 KB Output is correct
10 Correct 432 ms 34928 KB Output is correct
11 Correct 530 ms 35816 KB Output is correct
12 Correct 14649 ms 42452 KB Output is correct
13 Correct 11890 ms 62628 KB Output is correct
14 Correct 2991 ms 113600 KB Output is correct
15 Correct 2453 ms 113488 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 33008 KB Output is correct
2 Correct 193 ms 33132 KB Output is correct
3 Correct 203 ms 33260 KB Output is correct
4 Correct 201 ms 33132 KB Output is correct
5 Correct 212 ms 33896 KB Output is correct
6 Correct 260 ms 34540 KB Output is correct
7 Correct 1177 ms 47456 KB Output is correct
8 Correct 2343 ms 80500 KB Output is correct
9 Correct 445 ms 34792 KB Output is correct
10 Correct 514 ms 36848 KB Output is correct
11 Correct 4129 ms 180884 KB Output is correct
12 Correct 5798 ms 312284 KB Output is correct
13 Correct 4633 ms 181028 KB Output is correct
14 Correct 5750 ms 312612 KB Output is correct
15 Correct 4173 ms 181004 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 29304 KB Output is correct
2 Correct 34 ms 28920 KB Output is correct
3 Correct 34 ms 28920 KB Output is correct
4 Correct 34 ms 28920 KB Output is correct
5 Correct 65 ms 29176 KB Output is correct
6 Correct 49 ms 29300 KB Output is correct
7 Correct 34 ms 28920 KB Output is correct
8 Correct 35 ms 28920 KB Output is correct
9 Correct 68 ms 29276 KB Output is correct
10 Correct 73 ms 29428 KB Output is correct
11 Correct 59 ms 30112 KB Output is correct
12 Correct 56 ms 30068 KB Output is correct
13 Correct 176 ms 33004 KB Output is correct
14 Correct 192 ms 33060 KB Output is correct
15 Correct 13868 ms 39024 KB Output is correct
16 Correct 189 ms 33256 KB Output is correct
17 Correct 13787 ms 38552 KB Output is correct
18 Correct 242 ms 34284 KB Output is correct
19 Correct 1006 ms 45632 KB Output is correct
20 Correct 14073 ms 40824 KB Output is correct
21 Correct 415 ms 34920 KB Output is correct
22 Correct 432 ms 34928 KB Output is correct
23 Correct 530 ms 35816 KB Output is correct
24 Correct 14649 ms 42452 KB Output is correct
25 Correct 11890 ms 62628 KB Output is correct
26 Correct 2991 ms 113600 KB Output is correct
27 Correct 2453 ms 113488 KB Output is correct
28 Correct 177 ms 33008 KB Output is correct
29 Correct 193 ms 33132 KB Output is correct
30 Correct 203 ms 33260 KB Output is correct
31 Correct 201 ms 33132 KB Output is correct
32 Correct 212 ms 33896 KB Output is correct
33 Correct 260 ms 34540 KB Output is correct
34 Correct 1177 ms 47456 KB Output is correct
35 Correct 2343 ms 80500 KB Output is correct
36 Correct 445 ms 34792 KB Output is correct
37 Correct 514 ms 36848 KB Output is correct
38 Correct 4129 ms 180884 KB Output is correct
39 Correct 5798 ms 312284 KB Output is correct
40 Correct 4633 ms 181028 KB Output is correct
41 Correct 5750 ms 312612 KB Output is correct
42 Correct 4173 ms 181004 KB Output is correct
43 Correct 13887 ms 41800 KB Output is correct
44 Correct 1579 ms 50700 KB Output is correct
45 Correct 14175 ms 42972 KB Output is correct
46 Correct 2312 ms 80872 KB Output is correct
47 Correct 441 ms 34920 KB Output is correct
48 Correct 447 ms 34904 KB Output is correct
49 Correct 567 ms 36816 KB Output is correct
50 Correct 2280 ms 46844 KB Output is correct
51 Execution timed out 15029 ms 44280 KB Time limit exceeded
52 Halted 0 ms 0 KB -