oj.uz

Submission #547804

# Submission time Handle Problem Language Result Execution time Memory
547804 2022-04-11T19:36:51 Z blue Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 5368 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 = 2;





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 249 ms 528 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 4 ms 440 KB Output is correct
5 Correct 634 ms 716 KB Output is correct
6 Correct 1536 ms 928 KB Output is correct
7 Correct 5 ms 1108 KB Output is correct
8 Correct 6 ms 1108 KB Output is correct
9 Correct 1046 ms 1296 KB Output is correct
10 Correct 1509 ms 1524 KB Output is correct
11 Correct 2762 ms 1868 KB Output is correct
12 Correct 2573 ms 1720 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2752 KB Output is correct
2 Correct 39 ms 2764 KB Output is correct
3 Execution timed out 15066 ms 5052 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2764 KB Output is correct
2 Correct 47 ms 2720 KB Output is correct
3 Correct 59 ms 2760 KB Output is correct
4 Correct 68 ms 2772 KB Output is correct
5 Correct 401 ms 2780 KB Output is correct
6 Correct 4669 ms 3104 KB Output is correct
7 Execution timed out 15086 ms 5368 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 528 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 4 ms 440 KB Output is correct
5 Correct 634 ms 716 KB Output is correct
6 Correct 1536 ms 928 KB Output is correct
7 Correct 5 ms 1108 KB Output is correct
8 Correct 6 ms 1108 KB Output is correct
9 Correct 1046 ms 1296 KB Output is correct
10 Correct 1509 ms 1524 KB Output is correct
11 Correct 2762 ms 1868 KB Output is correct
12 Correct 2573 ms 1720 KB Output is correct
13 Correct 24 ms 2752 KB Output is correct
14 Correct 39 ms 2764 KB Output is correct
15 Execution timed out 15066 ms 5052 KB Time limit exceeded
16 Halted 0 ms 0 KB -