oj.uz

Submission #220488

# Submission time Handle Problem Language Result Execution time Memory
220488 2020-04-08T02:04:50 Z arnold518 Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 19720 KB 
#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int SQ = 330;

struct Query { int t, x, y, p; };

int N, C, Q;
Query A[MAXN+10], B[MAXN+10], V[MAXN*2+10];
vector<int> ans;

struct UF
{
	int par[MAXN+10], sz[MAXN+10];
	vector<int> S;
	void init()
	{
		int i, j;
		S.clear();
		for(i=1; i<=N; i++) par[i]=i, sz[i]=1;
	}
	int Find(int x) { return x==par[x] ? x : Find(par[x]); }
	int Union(int x, int y)
	{
		x=Find(x); y=Find(y);
		if(x==y) return 0;
		if(sz[x]<sz[y]) swap(x, y);
		sz[x]+=sz[y]; par[y]=x;
		S.push_back(y);
		return 1;
	}
	void restore()
	{
		int v=S.back(); S.pop_back();
		sz[par[v]]-=sz[v];
		par[v]=v;
	}
}uf;

vector<int> simulateCollapse(int _N, vector<int> _T, vector<int> _X, vector<int> _Y, vector<int> _W, vector<int> _P)
{
	int i, j, k, p, q;

	N=_N; C=_T.size(); Q=_W.size(); ans.resize(Q, N);
	for(i=0; i<C; i++) if(_X[i]>_Y[i]) swap(_X[i], _Y[i]);
	for(i=0; i<C; i++) A[i+1]={_T[i], _X[i]+1, _Y[i]+1, i+1};
	for(i=0; i<Q; i++) B[i+1]={-1, _P[i]+1, i, _W[i]+1};

	for(i=1; i<=C; i++) V[i]=A[i];
	for(i=1; i<=Q; i++) V[i+C]=B[i];

	sort(V+1, V+C+Q+1, [&](const Query &p, const Query &q)
	{
		if(p.p!=q.p) return p.p<q.p;
		else return p.t>q.t;
	});

	for(i=0; i<=(C+Q)/SQ; i++)
	{
		int l=max(1, i*SQ), r=min(C+Q, (i+1)*SQ-1);
		set<pii> S;
		vector<pii> E1, E2;
		vector<int> query;

		for(j=1; j<l; j++)
		{
			if(V[j].t==0) S.insert({V[j].x, V[j].y});
			else if(V[j].t==1) S.erase({V[j].x, V[j].y});
		}
		for(j=l; j<=r; j++)
		{
			if(V[j].t==-1)
			{
				query.push_back(j);
			}
			else
			{
				if(S.count({V[j].x, V[j].y}))
				{
					S.erase({V[j].x, V[j].y});
					E2.push_back({V[j].x, V[j].y});
				}
			}
		}
		for(auto it : S) E1.push_back(it);

		sort(E1.begin(), E1.end(), [&](const pii &p, const pii &q) { return p.second<q.second; });
		sort(E2.begin(), E2.end(), [&](const pii &p, const pii &q) { return p.second<q.second; });
		sort(query.begin(), query.end(), [&](const int &p, const int &q) { return V[p].x<V[q].x; });

		uf.init(); j=0;
		for(auto &it : query)
		{
			for(; j<E1.size() && E1[j].second<=V[it].x; j++) uf.Union(E1[j].first, E1[j].second);
			set<pii> S1, S2;
			for(p=l; p<=it; p++)
			{
				if(V[p].t==-1) continue;
				if(V[p].y>V[it].x) continue;
				if(V[p].t==0) S1.insert({V[p].x, V[p].y});
				else S1.erase({V[p].x, V[p].y});
				S2.insert({V[p].x, V[p].y});
			}
			int cnt=0;
			for(auto jt : S1) cnt+=uf.Union(jt.first, jt.second);
			for(auto jt : E2) if(jt.second<=V[it].x && !S2.count(jt)) cnt+=uf.Union(jt.first, jt.second);
			ans[V[it].y]-=uf.S.size();
			while(cnt--) uf.restore();
		}

		sort(E1.begin(), E1.end(), [&](const pii &p, const pii &q) { return p.first>q.first; });
		sort(E2.begin(), E2.end(), [&](const pii &p, const pii &q) { return p.first>q.first; });
		sort(query.begin(), query.end(), [&](const int &p, const int &q) { return V[p].x>V[q].x; });

		uf.init(); j=0;
		for(auto &it : query)
		{
			for(; j<E1.size() && E1[j].first>V[it].x; j++) uf.Union(E1[j].first, E1[j].second);
			set<pii> S1, S2;
			for(p=l; p<=it; p++)
			{
				if(V[p].t==-1) continue;
				if(V[p].x<=V[it].x) continue;
				if(V[p].t==0) S1.insert({V[p].x, V[p].y});
				else S1.erase({V[p].x, V[p].y});
				S2.insert({V[p].x, V[p].y});
			}
			int cnt=0;
			for(auto jt : S1) cnt+=uf.Union(jt.first, jt.second);
			for(auto jt : E2) if(jt.first>V[it].x && !S2.count(jt)) cnt+=uf.Union(jt.first, jt.second);
			ans[V[it].y]-=uf.S.size();
			while(cnt--) uf.restore();
		}
	}

	return ans;
}

Compilation message

collapse.cpp: In member function 'void UF::init()':
collapse.cpp:24:10: warning: unused variable 'j' [-Wunused-variable]
   int i, j;
          ^
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:100:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(; j<E1.size() && E1[j].second<=V[it].x; j++) uf.Union(E1[j].first, E1[j].second);
          ~^~~~~~~~~~
collapse.cpp:124:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(; j<E1.size() && E1[j].first>V[it].x; j++) uf.Union(E1[j].first, E1[j].second);
          ~^~~~~~~~~~
collapse.cpp:48:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k, p, q;
            ^
collapse.cpp:48:18: warning: unused variable 'q' [-Wunused-variable]
  int i, j, k, p, q;
                  ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1024 KB Output is correct
2 Correct 8 ms 512 KB Output is correct
3 Correct 8 ms 640 KB Output is correct
4 Correct 9 ms 640 KB Output is correct
5 Correct 59 ms 1016 KB Output is correct
6 Correct 94 ms 1232 KB Output is correct
7 Correct 8 ms 768 KB Output is correct
8 Correct 8 ms 768 KB Output is correct
9 Correct 63 ms 1144 KB Output is correct
10 Correct 87 ms 1144 KB Output is correct
11 Correct 105 ms 1780 KB Output is correct
12 Correct 99 ms 1400 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 6264 KB Output is correct
2 Correct 112 ms 6264 KB Output is correct
3 Correct 3696 ms 12664 KB Output is correct
4 Correct 113 ms 6264 KB Output is correct
5 Correct 4578 ms 13036 KB Output is correct
6 Correct 397 ms 7304 KB Output is correct
7 Execution timed out 15030 ms 19720 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 6264 KB Output is correct
2 Correct 110 ms 6264 KB Output is correct
3 Correct 116 ms 6344 KB Output is correct
4 Correct 118 ms 6476 KB Output is correct
5 Correct 150 ms 6576 KB Output is correct
6 Correct 441 ms 7300 KB Output is correct
7 Correct 10470 ms 16544 KB Output is correct
8 Execution timed out 15076 ms 19296 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1024 KB Output is correct
2 Correct 8 ms 512 KB Output is correct
3 Correct 8 ms 640 KB Output is correct
4 Correct 9 ms 640 KB Output is correct
5 Correct 59 ms 1016 KB Output is correct
6 Correct 94 ms 1232 KB Output is correct
7 Correct 8 ms 768 KB Output is correct
8 Correct 8 ms 768 KB Output is correct
9 Correct 63 ms 1144 KB Output is correct
10 Correct 87 ms 1144 KB Output is correct
11 Correct 105 ms 1780 KB Output is correct
12 Correct 99 ms 1400 KB Output is correct
13 Correct 106 ms 6264 KB Output is correct
14 Correct 112 ms 6264 KB Output is correct
15 Correct 3696 ms 12664 KB Output is correct
16 Correct 113 ms 6264 KB Output is correct
17 Correct 4578 ms 13036 KB Output is correct
18 Correct 397 ms 7304 KB Output is correct
19 Execution timed out 15030 ms 19720 KB Time limit exceeded
20 Halted 0 ms 0 KB -