oj.uz

Submission #503710

# Submission time Handle Problem Language Result Execution time Memory
503710 2022-01-08T16:42:02 Z amunduzbaev Collapse (JOI18_collapse) C++14
30 / 100
 2269 ms 524292 KB 
#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 Second{

vector<int> solve(int n, vector<int> t, vector<int> a,
vector<int> b, vector<int> in, vector<int> p){
	vector<set<ar<int, 2>>> ee(t.size());
	set<ar<int, 2>> ss;
	for(int i=0;i<(int)t.size();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]});
		ee[i] = ss;
	}
	
	vector<int> rr;
	for(int i=0;i<(int)in.size();i++){
		int P = p[i];
		
		vector<vector<int>> edges(n);
		for(auto x : ee[in[i]]){
			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.push_back(res);
	} return rr;
}

}

vector<int> simulateCollapse(
int n, vector<int> t, vector<int> a,
vector<int> b, vector<int> in, vector<int> p) {
	
	if(*max_element(p.begin(), p.end()) == *min_element(p.begin(), p.end())){
		return First::solve(n, t, a, b, in, p);
	} return Second::solve(n, t, a, b, in, p);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1100 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 5 ms 432 KB Output is correct
4 Correct 8 ms 412 KB Output is correct
5 Correct 13 ms 3808 KB Output is correct
6 Runtime error 836 ms 524292 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6540 KB Output is correct
2 Correct 34 ms 13360 KB Output is correct
3 Correct 119 ms 19480 KB Output is correct
4 Correct 39 ms 13068 KB Output is correct
5 Correct 124 ms 19832 KB Output is correct
6 Correct 57 ms 14204 KB Output is correct
7 Correct 155 ms 26508 KB Output is correct
8 Correct 122 ms 19944 KB Output is correct
9 Correct 29 ms 7732 KB Output is correct
10 Correct 39 ms 14348 KB Output is correct
11 Correct 55 ms 14832 KB Output is correct
12 Correct 136 ms 22880 KB Output is correct
13 Correct 152 ms 24520 KB Output is correct
14 Correct 163 ms 27612 KB Output is correct
15 Correct 166 ms 28424 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6440 KB Output is correct
2 Correct 51 ms 3640 KB Output is correct
3 Correct 93 ms 3732 KB Output is correct
4 Correct 190 ms 3740 KB Output is correct
5 Correct 2269 ms 9900 KB Output is correct
6 Runtime error 891 ms 524292 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1100 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 5 ms 432 KB Output is correct
4 Correct 8 ms 412 KB Output is correct
5 Correct 13 ms 3808 KB Output is correct
6 Runtime error 836 ms 524292 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -