oj.uz

Submission #129661

# Submission time Handle Problem Language Result Execution time Memory
129661 2019-07-12T22:48:39 Z qkxwsm Collapse (JOI18_collapse) C++14
100 / 100
 14938 ms 312408 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);
		if (siz[v] = siz[u]) siz[v]++;
		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
}

Compilation message

collapse.cpp: In member function 'bool dsu::merge(int, int)':
collapse.cpp:80:14: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   if (siz[v] = siz[u]) siz[v]++;
       ~~~~~~~^~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 29176 KB Output is correct
2 Correct 33 ms 28920 KB Output is correct
3 Correct 33 ms 28792 KB Output is correct
4 Correct 33 ms 28892 KB Output is correct
5 Correct 67 ms 29176 KB Output is correct
6 Correct 53 ms 29300 KB Output is correct
7 Correct 33 ms 28920 KB Output is correct
8 Correct 40 ms 28892 KB Output is correct
9 Correct 66 ms 29304 KB Output is correct
10 Correct 91 ms 29304 KB Output is correct
11 Correct 60 ms 29940 KB Output is correct
12 Correct 58 ms 29940 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 32776 KB Output is correct
2 Correct 178 ms 32620 KB Output is correct
3 Correct 14052 ms 37676 KB Output is correct
4 Correct 180 ms 32620 KB Output is correct
5 Correct 13878 ms 37912 KB Output is correct
6 Correct 240 ms 33604 KB Output is correct
7 Correct 972 ms 45264 KB Output is correct
8 Correct 14124 ms 40284 KB Output is correct
9 Correct 420 ms 34112 KB Output is correct
10 Correct 426 ms 34236 KB Output is correct
11 Correct 512 ms 35076 KB Output is correct
12 Correct 14938 ms 42036 KB Output is correct
13 Correct 11684 ms 62328 KB Output is correct
14 Correct 2902 ms 113124 KB Output is correct
15 Correct 2522 ms 113124 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 32748 KB Output is correct
2 Correct 182 ms 32620 KB Output is correct
3 Correct 184 ms 32620 KB Output is correct
4 Correct 191 ms 32620 KB Output is correct
5 Correct 199 ms 33384 KB Output is correct
6 Correct 251 ms 33644 KB Output is correct
7 Correct 1173 ms 46048 KB Output is correct
8 Correct 2446 ms 78804 KB Output is correct
9 Correct 428 ms 34152 KB Output is correct
10 Correct 512 ms 35944 KB Output is correct
11 Correct 4662 ms 178760 KB Output is correct
12 Correct 5897 ms 309968 KB Output is correct
13 Correct 4724 ms 178540 KB Output is correct
14 Correct 6065 ms 310136 KB Output is correct
15 Correct 4591 ms 178704 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 29176 KB Output is correct
2 Correct 33 ms 28920 KB Output is correct
3 Correct 33 ms 28792 KB Output is correct
4 Correct 33 ms 28892 KB Output is correct
5 Correct 67 ms 29176 KB Output is correct
6 Correct 53 ms 29300 KB Output is correct
7 Correct 33 ms 28920 KB Output is correct
8 Correct 40 ms 28892 KB Output is correct
9 Correct 66 ms 29304 KB Output is correct
10 Correct 91 ms 29304 KB Output is correct
11 Correct 60 ms 29940 KB Output is correct
12 Correct 58 ms 29940 KB Output is correct
13 Correct 169 ms 32776 KB Output is correct
14 Correct 178 ms 32620 KB Output is correct
15 Correct 14052 ms 37676 KB Output is correct
16 Correct 180 ms 32620 KB Output is correct
17 Correct 13878 ms 37912 KB Output is correct
18 Correct 240 ms 33604 KB Output is correct
19 Correct 972 ms 45264 KB Output is correct
20 Correct 14124 ms 40284 KB Output is correct
21 Correct 420 ms 34112 KB Output is correct
22 Correct 426 ms 34236 KB Output is correct
23 Correct 512 ms 35076 KB Output is correct
24 Correct 14938 ms 42036 KB Output is correct
25 Correct 11684 ms 62328 KB Output is correct
26 Correct 2902 ms 113124 KB Output is correct
27 Correct 2522 ms 113124 KB Output is correct
28 Correct 169 ms 32748 KB Output is correct
29 Correct 182 ms 32620 KB Output is correct
30 Correct 184 ms 32620 KB Output is correct
31 Correct 191 ms 32620 KB Output is correct
32 Correct 199 ms 33384 KB Output is correct
33 Correct 251 ms 33644 KB Output is correct
34 Correct 1173 ms 46048 KB Output is correct
35 Correct 2446 ms 78804 KB Output is correct
36 Correct 428 ms 34152 KB Output is correct
37 Correct 512 ms 35944 KB Output is correct
38 Correct 4662 ms 178760 KB Output is correct
39 Correct 5897 ms 309968 KB Output is correct
40 Correct 4724 ms 178540 KB Output is correct
41 Correct 6065 ms 310136 KB Output is correct
42 Correct 4591 ms 178704 KB Output is correct
43 Correct 13851 ms 39908 KB Output is correct
44 Correct 1573 ms 48828 KB Output is correct
45 Correct 14109 ms 40480 KB Output is correct
46 Correct 2735 ms 78944 KB Output is correct
47 Correct 428 ms 34100 KB Output is correct
48 Correct 435 ms 34152 KB Output is correct
49 Correct 559 ms 35624 KB Output is correct
50 Correct 2286 ms 45536 KB Output is correct
51 Correct 14873 ms 42004 KB Output is correct
52 Correct 14782 ms 80728 KB Output is correct
53 Correct 14265 ms 80448 KB Output is correct
54 Correct 13593 ms 114164 KB Output is correct
55 Correct 13294 ms 113848 KB Output is correct
56 Correct 11537 ms 180132 KB Output is correct
57 Correct 9137 ms 180656 KB Output is correct
58 Correct 10636 ms 180540 KB Output is correct
59 Correct 4572 ms 181276 KB Output is correct
60 Correct 6267 ms 312408 KB Output is correct