oj.uz

Submission #129330

# Submission time Handle Problem Language Result Execution time Memory
129330 2019-07-12T03:53:39 Z qkxwsm Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 28680 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;
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()
{
	vi nodes;
	FOR(i, 0, SZ(block))
	{
		if (block[i][1] != 2)
		{
			nodes.PB(block[i][2]);
			nodes.PB(block[i][3]);
		}
	}
	sort(ALL(nodes));
	nodes.erase(unique(ALL(nodes)), nodes.end());
	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) break;
			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 29 ms 17400 KB Output is correct
2 Correct 25 ms 17016 KB Output is correct
3 Correct 29 ms 17016 KB Output is correct
4 Correct 32 ms 17148 KB Output is correct
5 Correct 57 ms 17400 KB Output is correct
6 Correct 1129 ms 17816 KB Output is correct
7 Correct 27 ms 17144 KB Output is correct
8 Correct 31 ms 17144 KB Output is correct
9 Correct 185 ms 17528 KB Output is correct
10 Correct 278 ms 17656 KB Output is correct
11 Correct 469 ms 18060 KB Output is correct
12 Correct 793 ms 18244 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 20908 KB Output is correct
2 Correct 146 ms 20972 KB Output is correct
3 Correct 741 ms 25320 KB Output is correct
4 Correct 156 ms 20844 KB Output is correct
5 Correct 2024 ms 25320 KB Output is correct
6 Correct 7612 ms 21612 KB Output is correct
7 Execution timed out 15077 ms 28680 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 20844 KB Output is correct
2 Correct 148 ms 20972 KB Output is correct
3 Correct 153 ms 20844 KB Output is correct
4 Correct 162 ms 20972 KB Output is correct
5 Correct 284 ms 20944 KB Output is correct
6 Correct 8433 ms 21640 KB Output is correct
7 Execution timed out 15061 ms 26992 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 17400 KB Output is correct
2 Correct 25 ms 17016 KB Output is correct
3 Correct 29 ms 17016 KB Output is correct
4 Correct 32 ms 17148 KB Output is correct
5 Correct 57 ms 17400 KB Output is correct
6 Correct 1129 ms 17816 KB Output is correct
7 Correct 27 ms 17144 KB Output is correct
8 Correct 31 ms 17144 KB Output is correct
9 Correct 185 ms 17528 KB Output is correct
10 Correct 278 ms 17656 KB Output is correct
11 Correct 469 ms 18060 KB Output is correct
12 Correct 793 ms 18244 KB Output is correct
13 Correct 136 ms 20908 KB Output is correct
14 Correct 146 ms 20972 KB Output is correct
15 Correct 741 ms 25320 KB Output is correct
16 Correct 156 ms 20844 KB Output is correct
17 Correct 2024 ms 25320 KB Output is correct
18 Correct 7612 ms 21612 KB Output is correct
19 Execution timed out 15077 ms 28680 KB Time limit exceeded
20 Halted 0 ms 0 KB -