Submission #67619

#	Time	Username	Problem	Language	Result	Execution time	Memory
67619		top34051	Collapse (JOI18_collapse)	C++17	100 / 100	8042 ms	287872 KiB

collapse

//subtask3
#include "collapse.h"
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 1e5 + 5;
const int sq = 320;

class DSU {
public:
	int n,com;
	int head[maxn], sz[maxn];
	stack<pii> stk;

	void init(int _n) {
		n = com = _n;
		for(int i=0;i<n;i++) {
			head[i] = i;
			sz[i] = 1;
		}
	}

	int findhead(int x) {
		if(x==head[x]) return x;
		return findhead(head[x]);
	}

	void add_edge(int u, int v) {
		int x = findhead(u), y = findhead(v);
		if(sz[x] > sz[y]) swap(x,y);
		stk.push({x,y});
		if(x!=y) {
			head[x] = y;
			sz[y] += sz[x];
			com--;
		}
	}

	void pop_edge() {
		int x = stk.top().X, y = stk.top().Y; stk.pop();
		if(x!=y) {
            head[x] = x;
            sz[y] -= sz[x];
            com++;
		}
	}

	int size() {
	    return com;
	}
} dsu;

struct trp {
	int x,y,id;
};

int n,m,q;
int ft[maxn];
map<pii,int> occur;

vector<trp> op;
vector<int> good, amb;
vector<int> ask[maxn];
int ans[maxn];

bool cmpL(trp a, trp b) {
    if(a.y != b.y) return a.y < b.y;
    return a.id < b.id;
}

bool cmpR(trp a, trp b) {
    if(a.x != b.x) return a.x > b.x;
    return a.id < b.id;
}

vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> D, vector<int> P) {
	n = N; m = T.size(); q = D.size();
	for(int i=0;i<m;i++) {
		if(X[i]>Y[i]) swap(X[i],Y[i]);
		if(T[i]==0) {
			ft[i] = m-1;
			occur[{X[i],Y[i]}] = i;
		}
		else ft[occur[{X[i],Y[i]}]] = i-1;
	}

	for(int i=0;i<q;i++) ask[D[i]].push_back(i);

	for(int s=0;s<m;s+=sq) {
		int e = min(m,s+sq-1);

		//eliminate all invalid edge (ft[i] < s)
		vector<int> tmp;
		for(auto i : good) {
			if(ft[i] < s) continue;
			tmp.push_back(i);
		}
		good = tmp;

		//---------------------------------------------------------------------------

		op.clear(); amb.clear();
		for(int i=s;i<=e;i++) {
			for(auto x : ask[i]) op.push_back({P[x],P[x],x});
		}
		for(auto i : good) {
			if(ft[i]>=e) op.push_back({X[i],Y[i],-1});
			else amb.push_back(i);
		}
		for(int i=s;i<=e;i++) amb.push_back(i);

		sort(op.begin(),op.end(),cmpL);

		dsu.init(n);
		for(auto t : op) {
			int x = t.id;
			if(x<0) dsu.add_edge(t.x,t.y);
			else {
				int ex = 0;
				for(auto i : amb) {
					if(Y[i]<=t.x && i<=D[x] && D[x]<=ft[i]) {
						dsu.add_edge(X[i],Y[i]);
						ex++;
					}
				}
				ans[x] += dsu.size();
				while(ex--) dsu.pop_edge();
			}
		}

		//---------------------------------------------------------------------------

		op.clear();
		for(int i=s;i<=e;i++) {
			for(auto x : ask[i]) op.push_back({P[x]+1,P[x]+1,x});
		}
		for(auto i : good) {
			if(ft[i]>=e) op.push_back({X[i],Y[i],-1});
			else amb.push_back(i);
		}

		sort(op.begin(),op.end(),cmpR);

		dsu.init(n);
		for(auto t : op) {
			int x = t.id;
			if(x<0) dsu.add_edge(t.x,t.y);
			else {
				int ex = 0;
				for(auto i : amb) {
					if(t.y<=X[i] && i<=D[x] && D[x]<=ft[i]) {
						dsu.add_edge(X[i],Y[i]);
						ex++;
					}
				}
				ans[x] += dsu.size();
				while(ex--) dsu.pop_edge();
			}
		}

		//---------------------------------------------------------------------------

		for(int i=s;i<=e;i++) {
			if(T[i]==0) good.push_back(i);
		}

	}

	vector<int> vec;
	for(int i=0;i<q;i++) vec.push_back(ans[i]-n);
	return vec;
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35