Submission #503716

#	Time	Username	Problem	Language	Result	Execution time	Memory
503716		amunduzbaev	Collapse (JOI18_collapse)	C++14	35 / 100	1692 ms	26220 KiB

collapse

#include "collapse.h"

#include "bits/stdc++.h"
using namespace std;

#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array

namespace First{

struct node{
	int l, r, a, b;
};

struct DSU{
	vector<int> par, sz;
	int n;
	vector<ar<int, 2>> last;
	
	void init(int N){
		n = N;
		par.resize(n), sz.resize(n);
		for(int i=0;i<n;i++) par[i] = i, sz[i] = 1;
	}
	
	int f(int x){ return (par[x] == x ? x : f(par[x])); }
	
	void merge(int a, int b){
		a = f(a), b = f(b);
		if(a == b) return;
		if(sz[a] < sz[b]) swap(a, b);
		par[b] = a, sz[a] += sz[b];
		last.push_back({a, b}), n--;
	}
	
	void roll_back(int m){
		while((int)last.size() > m){
			int a = last.back()[0], b = last.back()[1]; last.pop_back();
			par[b] = b, sz[a] -= sz[b], n++;
		}
	}
};

vector<int> solve(int n, vector<int> t, vector<int> a,
vector<int> b, vector<int> in, vector<int> p){
	int P = p[0];
	int q = in.size(), m = a.size();
	map<ar<int, 2>, int> mm;
	vector<node> edges;
	for(int i=0;i<m;i++){
		if(a[i] > b[i]) swap(a[i], b[i]);
		if(a[i] <= P && P < b[i]) continue;
		if(t[i] == 0){
			mm[{a[i], b[i]}] = i;
		} else {
			edges.push_back({mm[{a[i], b[i]}], i - 1, a[i], b[i]});
			mm.erase({a[i], b[i]});
		}
	}
	
	for(auto x : mm){
		edges.push_back({x.second, m - 1, x.first[0], x.first[1]});
	}
	
	for(int i=0;i<q;i++){
		edges.push_back({in[i], in[i], -1, i});
	} vector<int> res(q);
	DSU dsu;
	dsu.init(n);
	
	function<void(int, int, vector<node>)> go = [&](int l, int r, vector<node> qq){
		int m = dsu.last.size();
		if(l == r){
			for(auto x : qq){
				if(~x.a){
					if(x.l <= l && l <= x.r) dsu.merge(x.a, x.b);
				} else {
					if(l == x.l) res[x.b] = dsu.n;
				}
			}
			
			dsu.roll_back(m);
			return;
		}
		
		vector<node> q2;
		int mid = (l + r) >> 1;
		for(auto x : qq){
			if(~x.a){
				if(x.l <= l && r <= x.r) dsu.merge(x.a, x.b);
				else if(max(x.l, l) <= min(x.r, r)) q2.push_back(x);
			} else {
				if(l <= x.l && x.l <= r) q2.push_back(x);
			}
		}
		
		go(l, mid, q2), go(mid + 1, r, q2);
		dsu.roll_back(m);
	};
	
	go(0, m - 1, edges);
	
	return res;
}

}

namespace SMOL{

vector<int> solve(int n, vector<int> t, vector<int> a,
vector<int> b, vector<int> in, vector<int> p){
	int m = (int)t.size(), q = (int)in.size();
	vector<int> v(q), rr(q);
	iota(v.begin(), v.end(), 0);
	sort(v.begin(), v.end(), [&](int i, int j){
		return (in[i] < in[j]);
	});
	set<ar<int, 2>> ss;
	int j = 0;
	
	auto check = [&](int i){
		int P = p[i];
		
		vector<vector<int>> edges(n);
		for(auto x : ss){
			if(x[0] <= P && x[1] > P) continue;
			edges[x[0]].push_back(x[1]);
			edges[x[1]].push_back(x[0]);
		}
		vector<int> used(n);
		int res = 0;
		
		function<void(int)> dfs = [&](int u){
			used[u] = 1;
			for(auto x : edges[u]){
				if(used[x]) continue;
				dfs(x);
			}
		};
		
		for(int i=0;i<n;i++){
			if(used[i]) continue;
			res++, dfs(i);
		}
		
		rr[i] = res; //.push_back(res);
	};
	
	for(int i=0;i<m;i++){
		if(a[i] > b[i]) swap(a[i], b[i]);
		if(t[i]) ss.erase({a[i], b[i]});
		else ss.insert({a[i], b[i]});
		
		while(j < q && in[v[j]] == i){
			check(v[j]);
			j++;
		}
	}
	
	return rr;
}

}

namespace Second{

vector<int> solve(int n, vector<int> t, vector<int> a,
vector<int> b, vector<int> in, vector<int> p){
	assert(0);
}

}

vector<int> simulateCollapse(
int n, vector<int> t, vector<int> a,
vector<int> b, vector<int> in, vector<int> p) {
	int q = in.size(), m = t.size();
	if(n <= 5000 && q <= 5000 && m <= 5000) return SMOL::solve(n, t, a, b, in, p);
	//~ assert(0);
	if(*max_element(p.begin(), p.end()) == *min_element(p.begin(), p.end())){
		return First::solve(n, t, a, b, in, p);
	} if(*max_element(t.begin(), t.end()) == 0){
		return Second::solve(n, t, a, b, in, p);
	} else assert(0);
}

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