oj.uz

Submission #547808

# Submission time Handle Problem Language Result Execution time Memory
547808 2022-04-11T19:39:51 Z blue Collapse (JOI18_collapse) C++17
35 / 100
 15000 ms 28620 KB 
#include "collapse.h"
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <iostream>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
#define sz(x) int(x.size())

const int bs = 350;





struct dss
{
	int Z;
	vi parent;
	vi subtree;

	dss()
	{
		;
	}

	dss(int Z_)
	{
		Z = Z_;
		parent = subtree = vi(Z);
		for(int i = 0; i < Z; i++)
		{
			parent[i] = i;
			subtree[i] = 1;
		}
	}

	int root(int u)
	{
		if(parent[u] == u) return u;
		else return (parent[u] = root(parent[u]));
	}

	bool join(int u, int v)
	{
		u = root(u);
		v = root(v);
		if(u == v) return 0;
		if(subtree[u] < subtree[v]) swap(u, v);
		parent[v] = u;
		subtree[u] += subtree[v];
		return 1;
	}

	bool connected(int u, int v)
	{
		return root(u) == root(v);
	}
};






vi simulateCollapse(int N, vi T, vi X, vi Y, vi W, vi P)
{	
	int C = sz(X);
	int Q = sz(W);

	for(int i = 0; i < C; i++)
	{
		if(X[i] > Y[i])
			swap(X[i], Y[i]);
	}

	vi queries[N];
	for(int q = 0; q < Q; q++)
		queries[P[q]].push_back(q);

	vi res(Q);




	for(int bl = 0; bl*bs < C; bl++)
	{
		int l = bl*bs, r = min((bl+1)*bs - 1, C-1);

		// cerr << "\n\n\n\n\n\n\n";
		// cerr << "l r = " << l << ' ' << r << '\n';

		set<pii> critical;
		for(int i = l; i <= r; i++)
		{
			critical.insert({X[i], Y[i]});
		}

		set<pii> edgeset;

		for(int i = 0; i < l; i++)
		{
			// if(critical.find({X[i], Y[i]}) != critical.end())
			// 	continue;

			if(T[i] == 0)
				edgeset.insert({X[i], Y[i]});
			else
				edgeset.erase({X[i], Y[i]});
		}

		set<pii> yescritical;

		for(pii z : critical)
		{
			if(edgeset.find(z) != edgeset.end())
			{
				edgeset.erase(z);
				yescritical.insert(z);
			}
		}

		vi fwdedge[N], backedge[N];
		for(auto e : edgeset)
		{
			fwdedge[e.first].push_back(e.second);
			backedge[e.second].push_back(e.first);
		}

		// cerr << "critical edges\n";
		// for(pii f : critical) cerr << f.first << ' ' << f.second << '\n';
		// 	cerr << '\n';
		// cerr << '\n';





























		dss dsu1(N);

		int comps = 0;

		vi checkedge[N];
		vi vis(N, 0);


		for(int i = 0; i <= N-2; i++)
		{
			comps++;

			for(int j : backedge[i])
			{
				comps -= dsu1.join(i, j);
			}

			for(int q : queries[i])
			{
				int t = W[q];

				if(!(l <= t && t <= r)) continue;

				set<pii> currcritical;

				for(pii w : yescritical)
					if(w.second <= P[q])
						currcritical.insert(w);

				vi vertlist;

				for(int ei = l; ei <= t; ei++)
				{
					if(Y[ei] >= P[q] + 1) continue;

					if(T[ei] == 0)
						currcritical.insert({X[ei], Y[ei]});
					else
						currcritical.erase({X[ei], Y[ei]});
				}

				for(auto k : currcritical)
				{
					int rx = dsu1.root(k.first);
					int ry = dsu1.root(k.second);

					checkedge[rx].push_back(ry);
					checkedge[ry].push_back(rx);

					vertlist.push_back(rx);
					vertlist.push_back(ry);
				}

				int thiscomps = comps;

				for(int z : vertlist)
				{
					if(vis[z]) continue;

					queue<int> tbv;
					tbv.push(z);
					vis[z] = 1;

					while(!tbv.empty())
					{
						int u = tbv.front();
						tbv.pop();

						for(int v : checkedge[u])
						{
							if(vis[v]) continue;
							vis[v] = 1;
							thiscomps--;
							tbv.push(v);
						}
					}
				}

				for(int v : vertlist)
				{
					vis[v] = 0;
					checkedge[v].clear();
				}

				res[q] += thiscomps;
				// cerr << "thiscomps = " << thiscomps << '\n';
			}
		}






















		dss dsu2(N);

		comps = 0;

		for(int i = 0; i < N; i++)
			checkedge[i].clear();

		vis = vi(N, 0);


		for(int i = N-1; i >= 1; i--)
		{
			comps++;

			for(int j : fwdedge[i])
			{
				comps -= dsu2.join(i, j);
			}

			for(int q : queries[i-1])
			{
				int t = W[q];
				if(!(l <= t && t <= r)) continue;

				set<pii> currcritical;

				for(pii w : yescritical)
					if(w.first >= P[q] + 1)
						currcritical.insert(w);

				vi vertlist;

				for(int ei = l; ei <= t; ei++)
				{
					if(X[ei] <= P[q]) continue;

					if(T[ei] == 0)
						currcritical.insert({X[ei], Y[ei]});
					else
						currcritical.erase({X[ei], Y[ei]});
				}

				// cerr << "l = " << l << ", t = " << t << '\n';

				for(auto k : currcritical)
				{
					int rx = dsu2.root(k.first);
					int ry = dsu2.root(k.second);

					checkedge[rx].push_back(ry);
					checkedge[ry].push_back(rx);

					vertlist.push_back(rx);
					vertlist.push_back(ry);
				}

				int thiscomps = comps;

				for(int z : vertlist)
				{
					if(vis[z]) continue;

					queue<int> tbv;
					tbv.push(z);
					vis[z] = 1;

					while(!tbv.empty())
					{
						int u = tbv.front();
						tbv.pop();

						for(int v : checkedge[u])
						{
							if(vis[v]) continue;
							vis[v] = 1;
							thiscomps--;
							tbv.push(v);
						}
					}
				}

				for(int v : vertlist)
				{
					vis[v] = 0;
					checkedge[v].clear();
				}

				res[q] += thiscomps;
				// cerr << "thiscomps = " << thiscomps << '\n';
			}
		}
	}




	return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 596 KB Output is correct
2 Correct 5 ms 444 KB Output is correct
3 Correct 12 ms 468 KB Output is correct
4 Correct 10 ms 440 KB Output is correct
5 Correct 43 ms 604 KB Output is correct
6 Correct 115 ms 860 KB Output is correct
7 Correct 4 ms 1080 KB Output is correct
8 Correct 6 ms 1108 KB Output is correct
9 Correct 61 ms 1304 KB Output is correct
10 Correct 148 ms 1472 KB Output is correct
11 Correct 152 ms 1744 KB Output is correct
12 Correct 129 ms 1716 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2884 KB Output is correct
2 Correct 39 ms 2880 KB Output is correct
3 Correct 2299 ms 5280 KB Output is correct
4 Correct 172 ms 3148 KB Output is correct
5 Correct 3176 ms 5788 KB Output is correct
6 Correct 1028 ms 3760 KB Output is correct
7 Correct 6600 ms 11552 KB Output is correct
8 Correct 3199 ms 6236 KB Output is correct
9 Correct 48 ms 14516 KB Output is correct
10 Correct 122 ms 14404 KB Output is correct
11 Correct 1471 ms 15028 KB Output is correct
12 Correct 4350 ms 16996 KB Output is correct
13 Correct 7485 ms 20120 KB Output is correct
14 Correct 13278 ms 25092 KB Output is correct
15 Correct 10282 ms 27492 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2764 KB Output is correct
2 Correct 50 ms 2704 KB Output is correct
3 Correct 100 ms 2860 KB Output is correct
4 Correct 179 ms 2860 KB Output is correct
5 Correct 1263 ms 2772 KB Output is correct
6 Correct 1477 ms 3172 KB Output is correct
7 Correct 4824 ms 9396 KB Output is correct
8 Correct 10599 ms 13128 KB Output is correct
9 Correct 69 ms 17108 KB Output is correct
10 Correct 2446 ms 16272 KB Output is correct
11 Correct 13446 ms 26224 KB Output is correct
12 Execution timed out 15071 ms 28620 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 596 KB Output is correct
2 Correct 5 ms 444 KB Output is correct
3 Correct 12 ms 468 KB Output is correct
4 Correct 10 ms 440 KB Output is correct
5 Correct 43 ms 604 KB Output is correct
6 Correct 115 ms 860 KB Output is correct
7 Correct 4 ms 1080 KB Output is correct
8 Correct 6 ms 1108 KB Output is correct
9 Correct 61 ms 1304 KB Output is correct
10 Correct 148 ms 1472 KB Output is correct
11 Correct 152 ms 1744 KB Output is correct
12 Correct 129 ms 1716 KB Output is correct
13 Correct 26 ms 2884 KB Output is correct
14 Correct 39 ms 2880 KB Output is correct
15 Correct 2299 ms 5280 KB Output is correct
16 Correct 172 ms 3148 KB Output is correct
17 Correct 3176 ms 5788 KB Output is correct
18 Correct 1028 ms 3760 KB Output is correct
19 Correct 6600 ms 11552 KB Output is correct
20 Correct 3199 ms 6236 KB Output is correct
21 Correct 48 ms 14516 KB Output is correct
22 Correct 122 ms 14404 KB Output is correct
23 Correct 1471 ms 15028 KB Output is correct
24 Correct 4350 ms 16996 KB Output is correct
25 Correct 7485 ms 20120 KB Output is correct
26 Correct 13278 ms 25092 KB Output is correct
27 Correct 10282 ms 27492 KB Output is correct
28 Correct 26 ms 2764 KB Output is correct
29 Correct 50 ms 2704 KB Output is correct
30 Correct 100 ms 2860 KB Output is correct
31 Correct 179 ms 2860 KB Output is correct
32 Correct 1263 ms 2772 KB Output is correct
33 Correct 1477 ms 3172 KB Output is correct
34 Correct 4824 ms 9396 KB Output is correct
35 Correct 10599 ms 13128 KB Output is correct
36 Correct 69 ms 17108 KB Output is correct
37 Correct 2446 ms 16272 KB Output is correct
38 Correct 13446 ms 26224 KB Output is correct
39 Execution timed out 15071 ms 28620 KB Time limit exceeded
40 Halted 0 ms 0 KB -