oj.uz

Submission #129341

# Submission time Handle Problem Language Result Execution time Memory
129341 2019-07-12T04:17:49 Z qkxwsm Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 28596 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
#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;
unordered_set<int> edges[MAXN], ins[MAXN], beg[MAXN];
vector<array<int, 4> > events;
vector<array<int, 4> > block;
bitset<MAXN> seen;
vi ord;

bool cmp(int a, int b)
{
	return block[a][2] < block[b][2];
}
struct dsu
{
	int dsu[MAXN], siz[MAXN];
	void init()
	{
		FOR(i, 0, N)
		{
			dsu[i] = i;
			siz[i] = 1;
		}
	}
	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;
		return true;
	}
};

dsu D[2];

void proc()
{
	seen.reset();
	vi nodes;
	FOR(i, 0, SZ(block))
	{
		if (block[i][1] == 2) continue;
		if (!seen[block[i][2]])
		{
			nodes.PB(block[i][2]);
			seen[block[i][2]] = true;
		}
		if (!seen[block[i][3]])
		{
			nodes.PB(block[i][3]);
			seen[block[i][3]] = true;
		}
	}
	D[0].init(); D[1].init();
	FOR(i, 0, N)
	{
		beg[i] = edges[i];
	}
	FOR(i, 0, SZ(block))
	{
		if (block[i][1] == 1)
		{
			int u = block[i][2], v = block[i][3];
			if (edges[v].find(u) != edges[v].end()) edges[v].erase(u);
		}
	}
	for (int u : nodes)
	{
		for (int v : edges[u])
		{
			beg[v].erase(v);
		}
	}
	int cp = -1, cc = 0;
	ord.clear();
	FOR(i, 0, SZ(block))
	{
		if (block[i][1] == 2) ord.PB(i);
	}
	sort(ALL(ord), cmp);
	for (int idx : ord)
	{
		int t = block[idx][0], x = block[idx][2], qid = block[idx][3];
		while(cp < x)
		{
			cp++; cc++;
			for (int w : edges[cp]) if (D[0].merge(cp, w)) cc--;
		}
		int res = cc;
		for (int u : nodes)
		{
			ins[u] = beg[u];
		}
		FOR(j, 0, SZ(block))
		{
			if (block[j][0] > t) break;
			if (block[j][1] == 2) continue;
			int u = block[j][2], v = block[j][3];
			if (v > x) continue;
			if (block[j][1] == 1)
			{
				if (ins[v].find(u) != ins[v].end()) ins[v].erase(u);
			}
			else
			{
				ins[v].insert(u);
			}
		}
		for (int u : nodes)
		{
			if (u > x) continue;
			int ve = D[0].get(u);
			for (int w : ins[u])
			{
				if (D[1].merge(ve, D[0].get(w))) res--;
			}
			ins[u].clear();
		}
		for (int u : nodes)
		{
			int v = D[0].get(u);
			D[1].dsu[v] = v; D[1].siz[v] = 1;
		}
		// cerr << res << endl;
		ans[qid] += res;
	}
	for (int u : nodes)
	{
		for (int x : beg[u])
		{
			edges[u].insert(x);
		}
	}
	FOR(i, 0, SZ(block))
	{
		if (block[i][1] == 2) continue;
		int u = block[i][2], v = block[i][3];
		if (block[i][1] == 1)
		{
			if (edges[v].find(u) != edges[v].end()) edges[v].erase(u);
		}
		else
		{
			edges[v].insert(u);
		}
	}
	//build the set of edges now!
}
void solve()
{
	//find # of cc's with value LESS THAN whatever
	//sort all the queries in the block.
	//after processing the block, the sets should store all active edges.
	// FOR(i, 0, SZ(events))
	// {
	// 	assert(events[i][1] == 2 || events[i][2] < events[i][3]);
	// }
	for (int i = 0; i < SZ(events); i += MAGIC)
	{
		for (int j = i; j < SZ(events) && j < i + MAGIC; j++)
		{
			block.PB(events[j]);
		}
		proc();
		block.clear();
	}
}
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;
	}
	// cerr << "SOLVE\n";
	solve();
	FOR(i, 0, N)
	{
		edges[i].clear();
		ins[i].clear();
	}
	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]);
		}
	}
	// cerr << "SOLVE\n";
	solve();
	return ans;
	//event: disconnect u -> v, connect u -> v, ask qid x pos y: so you store time, typ, who it happens to
	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17400 KB Output is correct
2 Correct 25 ms 17076 KB Output is correct
3 Correct 29 ms 17144 KB Output is correct
4 Correct 31 ms 17144 KB Output is correct
5 Correct 57 ms 17400 KB Output is correct
6 Correct 1194 ms 17912 KB Output is correct
7 Correct 27 ms 17144 KB Output is correct
8 Correct 28 ms 17272 KB Output is correct
9 Correct 211 ms 17532 KB Output is correct
10 Correct 299 ms 17656 KB Output is correct
11 Correct 481 ms 18012 KB Output is correct
12 Correct 797 ms 18356 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 20972 KB Output is correct
2 Correct 155 ms 20972 KB Output is correct
3 Correct 720 ms 25292 KB Output is correct
4 Correct 156 ms 20844 KB Output is correct
5 Correct 2056 ms 25320 KB Output is correct
6 Correct 7671 ms 21668 KB Output is correct
7 Execution timed out 15083 ms 28596 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 20844 KB Output is correct
2 Correct 148 ms 20972 KB Output is correct
3 Correct 155 ms 20972 KB Output is correct
4 Correct 159 ms 20876 KB Output is correct
5 Correct 288 ms 20972 KB Output is correct
6 Correct 8587 ms 21544 KB Output is correct
7 Execution timed out 15082 ms 27084 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17400 KB Output is correct
2 Correct 25 ms 17076 KB Output is correct
3 Correct 29 ms 17144 KB Output is correct
4 Correct 31 ms 17144 KB Output is correct
5 Correct 57 ms 17400 KB Output is correct
6 Correct 1194 ms 17912 KB Output is correct
7 Correct 27 ms 17144 KB Output is correct
8 Correct 28 ms 17272 KB Output is correct
9 Correct 211 ms 17532 KB Output is correct
10 Correct 299 ms 17656 KB Output is correct
11 Correct 481 ms 18012 KB Output is correct
12 Correct 797 ms 18356 KB Output is correct
13 Correct 136 ms 20972 KB Output is correct
14 Correct 155 ms 20972 KB Output is correct
15 Correct 720 ms 25292 KB Output is correct
16 Correct 156 ms 20844 KB Output is correct
17 Correct 2056 ms 25320 KB Output is correct
18 Correct 7671 ms 21668 KB Output is correct
19 Execution timed out 15083 ms 28596 KB Time limit exceeded
20 Halted 0 ms 0 KB -