oj.uz

Submission #503691

# Submission time Handle Problem Language Result Execution time Memory
503691 2022-01-08T15:35:02 Z amunduzbaev Collapse (JOI18_collapse) C++14
30 / 100
 168 ms 28620 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){
	assert(0);
}

}

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);
	} if(*max_element(t.begin(), t.end()) == 0){
		return Second::solve(n, t, a, b, in, p);
	} assert(0);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1092 KB Output is correct
2 Runtime error 2 ms 588 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6172 KB Output is correct
2 Correct 33 ms 13192 KB Output is correct
3 Correct 109 ms 19480 KB Output is correct
4 Correct 38 ms 13068 KB Output is correct
5 Correct 120 ms 20108 KB Output is correct
6 Correct 55 ms 14192 KB Output is correct
7 Correct 151 ms 27048 KB Output is correct
8 Correct 121 ms 20828 KB Output is correct
9 Correct 32 ms 7708 KB Output is correct
10 Correct 40 ms 14348 KB Output is correct
11 Correct 49 ms 14732 KB Output is correct
12 Correct 136 ms 22796 KB Output is correct
13 Correct 149 ms 25672 KB Output is correct
14 Correct 168 ms 28620 KB Output is correct
15 Correct 160 ms 28512 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 6360 KB Output is correct
2 Runtime error 18 ms 5276 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1092 KB Output is correct
2 Runtime error 2 ms 588 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -