oj.uz

Submission #547814

# Submission time Handle Problem Language Result Execution time Memory
547814 2022-04-11T19:47:24 Z blue Collapse (JOI18_collapse) C++17
30 / 100
 10295 ms 29248 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 = 450;





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);


	set<pii> edgeset;

	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]});
		}

		if(bl != 0)
		{
			for(int i = bl*bs - bs; i <= bl*bs - 1; i++)
			{
				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())
			{
				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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Output is correct
2 Correct 3 ms 440 KB Output is correct
3 Correct 6 ms 468 KB Output is correct
4 Correct 9 ms 476 KB Output is correct
5 Incorrect 49 ms 620 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2752 KB Output is correct
2 Correct 37 ms 2764 KB Output is correct
3 Incorrect 908 ms 5060 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2764 KB Output is correct
2 Correct 55 ms 2840 KB Output is correct
3 Correct 105 ms 2860 KB Output is correct
4 Correct 178 ms 2864 KB Output is correct
5 Correct 1826 ms 2764 KB Output is correct
6 Correct 1917 ms 3724 KB Output is correct
7 Correct 2922 ms 10188 KB Output is correct
8 Correct 4599 ms 13456 KB Output is correct
9 Correct 66 ms 17324 KB Output is correct
10 Correct 2808 ms 16496 KB Output is correct
11 Correct 7411 ms 27208 KB Output is correct
12 Correct 10100 ms 27336 KB Output is correct
13 Correct 7699 ms 27332 KB Output is correct
14 Correct 10295 ms 27324 KB Output is correct
15 Correct 7381 ms 29248 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Output is correct
2 Correct 3 ms 440 KB Output is correct
3 Correct 6 ms 468 KB Output is correct
4 Correct 9 ms 476 KB Output is correct
5 Incorrect 49 ms 620 KB Output isn't correct
6 Halted 0 ms 0 KB -