oj.uz

Submission #129329

# Submission time Handle Problem Language Result Execution time Memory
129329 2019-07-12T03:46:45 Z qkxwsm Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 31056 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()
{
	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(i, 0, N)
	{
		for (int x : edges[i])
		{
			beg[i].erase(x);
		}
	}
	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--;
		}
		// cerr << "cc = " << cc << endl;
		int res = cc;
		FOR(j, 0, SZ(block))
		{
			int u = block[j][2], v = block[j][3];
			ins[u] = beg[u];
			ins[v] = beg[v];
		}
		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(j, 0, SZ(block))
		{
			int u = block[j][2], v = block[j][3];
			if (v <= x)
			{
				int ve = D[0].get(v);
				for (int w : ins[v])
				{
					// cerr << "merge " << v << ' ' << w << endl;
					if (D[1].merge(ve, D[0].get(w))) res--;
				}
				ins[v].clear();
			}
			if (u <= x)
			{
				int ve = D[0].get(u);
				for (int w : ins[u])
				{
					// cerr << "merge " << v << ' ' << w << endl;
					if (D[1].merge(ve, D[0].get(w))) res--;
				}
				ins[u].clear();
			}
		}
		FOR(j, 0, SZ(block))
		{
			int u = block[j][2], v = block[j][3];
			u = D[0].get(u);
			D[1].dsu[u] = u; D[1].siz[u] = 1;
			v = D[0].get(v);
			D[1].dsu[v] = v; D[1].siz[v] = 1;
		}
		// cerr << res << endl;
		ans[qid] += res;
	}
	FOR(i, 0, N)
	{
		for (int x : beg[i])
		{
			edges[i].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 338 ms 17400 KB Output is correct
2 Correct 321 ms 17144 KB Output is correct
3 Correct 343 ms 17144 KB Output is correct
4 Correct 331 ms 17144 KB Output is correct
5 Correct 602 ms 17400 KB Output is correct
6 Correct 574 ms 17716 KB Output is correct
7 Correct 387 ms 17144 KB Output is correct
8 Correct 483 ms 17200 KB Output is correct
9 Correct 571 ms 17668 KB Output is correct
10 Correct 941 ms 17736 KB Output is correct
11 Correct 704 ms 18016 KB Output is correct
12 Correct 877 ms 18148 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5744 ms 21208 KB Output is correct
2 Correct 6709 ms 21148 KB Output is correct
3 Execution timed out 15078 ms 25320 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5698 ms 21380 KB Output is correct
2 Correct 6803 ms 21172 KB Output is correct
3 Correct 7383 ms 21196 KB Output is correct
4 Correct 7365 ms 21140 KB Output is correct
5 Correct 8058 ms 21156 KB Output is correct
6 Correct 10634 ms 21828 KB Output is correct
7 Execution timed out 15056 ms 31056 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 17400 KB Output is correct
2 Correct 321 ms 17144 KB Output is correct
3 Correct 343 ms 17144 KB Output is correct
4 Correct 331 ms 17144 KB Output is correct
5 Correct 602 ms 17400 KB Output is correct
6 Correct 574 ms 17716 KB Output is correct
7 Correct 387 ms 17144 KB Output is correct
8 Correct 483 ms 17200 KB Output is correct
9 Correct 571 ms 17668 KB Output is correct
10 Correct 941 ms 17736 KB Output is correct
11 Correct 704 ms 18016 KB Output is correct
12 Correct 877 ms 18148 KB Output is correct
13 Correct 5744 ms 21208 KB Output is correct
14 Correct 6709 ms 21148 KB Output is correct
15 Execution timed out 15078 ms 25320 KB Time limit exceeded
16 Halted 0 ms 0 KB -