oj.uz

Submission #1054563

# Submission time Handle Problem Language Result Execution time Memory
1054563 2024-08-12T10:43:15 Z aymanrs Collapse (JOI18_collapse) C++17
30 / 100
 2522 ms 34644 KB 
#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
const int nx = 4e5+10;
list<pair<int,int>> st[nx];
int re[100000], sz[100000];
int a_,b_,x_,y_;
void adde(int i, int l, int r){
	if(r<a_||b_<l) return;
	if(a_<=l&&r<=b_){
		st[i].emplace_back(x_,y_);
		return;
	}
	int m = l+r>>1;
	adde(i<<1, l, m);adde(i<<1|1, m+1, r);
}
int ti[100000], co;
void dfs(int i, int l, int r){
	stack<pair<int, int>> s;
	for(auto [a,b] : st[i]){
		while(re[a]!=a) a=re[a];
		while(re[b]!=b) b=re[b];
		if(a==b)continue;
		co--;
		if(sz[a]>b){
			sz[a]+=sz[b];
			re[b]=a;
			s.emplace(a, b);
		} else {
			sz[b]+=sz[a];
			re[a]=b;
			s.emplace(b,a);
		}
	}
	st[i].clear();
	if(l!=r){
		int m = l+r>>1;
		dfs(i<<1, l, m);
		dfs(i<<1|1, m+1, r);
	} else {
		ti[l]=co;
	}
	while(!s.empty()){
		int a = s.top().first, b = s.top().second;
		s.pop();
		sz[a]-=sz[b];
		re[b]=b;
		co++;
	}
}
std::vector<int> simulateCollapse(
	int N,
	std::vector<int> T,
	std::vector<int> X,
	std::vector<int> Y,
	std::vector<int> W,
	std::vector<int> P
) {
	int q = W.size(), c = T.size();
	vector<int> ans(q);
	map<pair<int, int>, int> tadd;
	int p_ = P[0];
	for(int i = 0;i < N;i++){
		re[i]=i;
		sz[i]=1;
	}
	co=N;
	for(int i = 0;i < c;i++){
		if(X[i] > Y[i]) swap(X[i], Y[i]);
		if(X[i] <= p_ && Y[i] > p_) continue;
		if(T[i]){
			auto p = tadd.find(make_pair(X[i], Y[i]));
			a_ = p->second;b_ = i-1;x_ = X[i];y_ = Y[i];
			adde(1, 0, c-1);
			p->second=-1;
		} else {
			tadd[make_pair(X[i], Y[i])] = i;
		}
	}
	for(auto p : tadd){
		if(p.second==-1) continue;
		a_ = p.second;b_ = c-1;x_ = p.first.first;y_ = p.first.second;
		adde(1,0,c-1);
	}
	dfs(1, 0, c-1);
	for(int i = 0;i < q;i++) ans[i] = ti[W[i]];
	return ans;
}

Compilation message

collapse.cpp: In function 'void adde(int, int, int)':
collapse.cpp:14:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |  int m = l+r>>1;
      |          ~^~
collapse.cpp: In function 'void dfs(int, int, int)':
collapse.cpp:37:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |   int m = l+r>>1;
      |           ~^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Incorrect 2 ms 10844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12632 KB Output is correct
2 Correct 13 ms 12636 KB Output is correct
3 Correct 40 ms 19868 KB Output is correct
4 Correct 13 ms 13148 KB Output is correct
5 Correct 52 ms 22240 KB Output is correct
6 Correct 18 ms 14236 KB Output is correct
7 Correct 271 ms 34384 KB Output is correct
8 Correct 55 ms 24656 KB Output is correct
9 Correct 15 ms 13404 KB Output is correct
10 Correct 15 ms 13408 KB Output is correct
11 Correct 16 ms 13912 KB Output is correct
12 Correct 72 ms 26196 KB Output is correct
13 Correct 1541 ms 31436 KB Output is correct
14 Correct 92 ms 34644 KB Output is correct
15 Correct 2522 ms 34012 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12632 KB Output is correct
2 Incorrect 13 ms 12656 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Incorrect 2 ms 10844 KB Output isn't correct
3 Halted 0 ms 0 KB -