oj.uz

Submission #547806

# Submission time Handle Problem Language Result Execution time Memory
547806 2022-04-11T19:38:22 Z blue Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 28292 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 = 250;





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 6 ms 544 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 6 ms 452 KB Output is correct
4 Correct 10 ms 340 KB Output is correct
5 Correct 35 ms 468 KB Output is correct
6 Correct 78 ms 780 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 6 ms 1108 KB Output is correct
9 Correct 52 ms 1228 KB Output is correct
10 Correct 103 ms 1256 KB Output is correct
11 Correct 111 ms 1640 KB Output is correct
12 Correct 107 ms 1612 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2728 KB Output is correct
2 Correct 37 ms 2764 KB Output is correct
3 Correct 2753 ms 5184 KB Output is correct
4 Correct 187 ms 3140 KB Output is correct
5 Correct 3558 ms 6704 KB Output is correct
6 Correct 791 ms 3816 KB Output is correct
7 Correct 10045 ms 13336 KB Output is correct
8 Correct 3677 ms 8516 KB Output is correct
9 Correct 48 ms 15308 KB Output is correct
10 Correct 102 ms 15276 KB Output is correct
11 Correct 1171 ms 16040 KB Output is correct
12 Correct 4974 ms 19560 KB Output is correct
13 Correct 9413 ms 22972 KB Output is correct
14 Execution timed out 15070 ms 27144 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2892 KB Output is correct
2 Correct 56 ms 2824 KB Output is correct
3 Correct 106 ms 2980 KB Output is correct
4 Correct 173 ms 2896 KB Output is correct
5 Correct 1028 ms 2904 KB Output is correct
6 Correct 1047 ms 3340 KB Output is correct
7 Correct 5815 ms 9732 KB Output is correct
8 Correct 12142 ms 15344 KB Output is correct
9 Correct 77 ms 17808 KB Output is correct
10 Correct 1721 ms 17432 KB Output is correct
11 Execution timed out 15078 ms 28292 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 544 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 6 ms 452 KB Output is correct
4 Correct 10 ms 340 KB Output is correct
5 Correct 35 ms 468 KB Output is correct
6 Correct 78 ms 780 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 6 ms 1108 KB Output is correct
9 Correct 52 ms 1228 KB Output is correct
10 Correct 103 ms 1256 KB Output is correct
11 Correct 111 ms 1640 KB Output is correct
12 Correct 107 ms 1612 KB Output is correct
13 Correct 25 ms 2728 KB Output is correct
14 Correct 37 ms 2764 KB Output is correct
15 Correct 2753 ms 5184 KB Output is correct
16 Correct 187 ms 3140 KB Output is correct
17 Correct 3558 ms 6704 KB Output is correct
18 Correct 791 ms 3816 KB Output is correct
19 Correct 10045 ms 13336 KB Output is correct
20 Correct 3677 ms 8516 KB Output is correct
21 Correct 48 ms 15308 KB Output is correct
22 Correct 102 ms 15276 KB Output is correct
23 Correct 1171 ms 16040 KB Output is correct
24 Correct 4974 ms 19560 KB Output is correct
25 Correct 9413 ms 22972 KB Output is correct
26 Execution timed out 15070 ms 27144 KB Time limit exceeded
27 Halted 0 ms 0 KB -