oj.uz

Submission #368840

# Submission time Handle Problem Language Result Execution time Memory
368840 2021-02-20T07:35:37 Z kig9981 Collapse (JOI18_collapse) C++17
100 / 100
 14698 ms 417164 KB 
#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

const int BC=400, SZ=1<<17;
vector<int> adj[100000], BB, tree[2*SZ];
vector<tuple<int,int,int>> qry;
vector<pair<int,int>> E, L[100000], R[100000];
map<pair<int,int>,int> idx;
int N, ans[100000], B[100000], LL[100000], color[100000], cnt[100000], RR[100000];
bool EX[100000];

void flip_edge(int c, int i)
{
	BB.push_back(c);
	EX[c]^=1;
}

int find_(int a)
{
	while(color[a]!=a) a=color[a];
	return a;
}

void union_(int a, int b)
{
	a=find_(a); b=find_(b);
	if(a==b) return;
	if(cnt[a]<cnt[b]) swap(a,b);
	cnt[color[b]=a]+=cnt[b];
	BB.push_back(b);
}

void restore(int sz)
{
	while(BB.size()>sz) {
		cnt[color[BB.back()]]-=cnt[BB.back()];
		color[BB.back()]=BB.back();
		BB.pop_back();
	}
}

void solve(int s, int e)
{
	int m=(s+e)>>1, bsz=BB.size(), bsz2;
	for(auto[v,r]: L[s]) if(r>=e) union_(E[v].first,E[v].second);
	for(auto[v,l]: R[e]) if(l<=s) union_(E[v].first,E[v].second);
	if(s==e) {
		ans[get<2>(qry[m])]=N-BB.size();
		restore(bsz);
		return;
	}
	bsz2=BB.size();
	for(int i=m;++i<e;) for(auto[v,l]: R[i]) if(l<=s) union_(E[v].first,E[v].second);
	solve(s,m);
	restore(bsz2);
	for(int i=m;i>s;i--) for(auto[v,r]: L[i]) if(r>=e) union_(E[v].first,E[v].second);
	solve(m+1,e);
	restore(bsz);
}

vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P)
{
	int C=T.size(), Q=W.size(), w, p;
	::N=N;
	for(int i=0;i<C;i++) {
		if(X[i]>Y[i]) swap(X[i],Y[i]);
		if(idx.count({X[i],Y[i]})==0) {
			idx[{X[i],Y[i]}]=E.size();
			E.emplace_back(X[i],Y[i]);
		}
		B[i]=idx[{X[i],Y[i]}];
		adj[X[i]].push_back(i);
		adj[Y[i]].push_back(i);
	}
	for(int i=0;i<Q;i++) qry.emplace_back(W[i],P[i],i);
	sort(qry.begin(),qry.end(),[&](tuple<int,int,int> a, tuple<int,int,int> b) {
		if(get<0>(a)/BC!=get<0>(b)/BC) return get<0>(a)/BC<get<0>(b)/BC;
		return get<1>(a)<get<1>(b);
	});
	memset(LL,w=p=-1,sizeof(LL));
	memset(RR,-1,sizeof(RR));
	for(int i=0;i<Q;i++) {
		auto[cw,cp,j]=qry[i];
		while(w<cw) {
			int c=B[++w];
			auto[a,b]=E[c];
			if(a<=p && p<b) continue;
			flip_edge(c,i);
		}
		while(w>cw) {
			int c=B[w--];
			auto[a,b]=E[c];
			if(a<=p && p<b) continue;
			flip_edge(c,i);
		}
		while(p<cp) {
			int c=++p;
			for(auto t: adj[c]) if(t<=w) flip_edge(B[t],i);
		}
		while(p>cp) {
			int c=p--;
			for(auto t: adj[c]) if(t<=w) flip_edge(B[t],i);
		}
		for(auto v: BB) if(RR[v]!=i) {
			RR[v]=i;
			if(LL[v]>-1 && !EX[v]) {
				L[LL[v]].emplace_back(v,i-1);
				R[i-1].emplace_back(v,LL[v]);
				LL[v]=-1;
			}
			else if(LL[v]==-1 && EX[v]) LL[v]=i;
		}
		BB.clear();
	}
	for(int i=0;i<E.size();i++) if(EX[i]) {
		L[LL[i]].emplace_back(i,Q-1);
		R[Q-1].emplace_back(i,LL[i]);
	}
	for(int i=0;i<N;i++) cnt[color[i]=i]=1;
	solve(0,Q-1);
	return vector<int>(ans,ans+Q);
}

Compilation message

collapse.cpp: In function 'void restore(int)':
collapse.cpp:44:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |  while(BB.size()>sz) {
      |        ~~~~~~~~~^~~
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:124:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |  for(int i=0;i<E.size();i++) if(EX[i]) {
      |              ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14828 KB Output is correct
2 Correct 14 ms 14572 KB Output is correct
3 Correct 15 ms 14956 KB Output is correct
4 Correct 18 ms 15084 KB Output is correct
5 Correct 30 ms 15488 KB Output is correct
6 Correct 59 ms 21116 KB Output is correct
7 Correct 12 ms 14672 KB Output is correct
8 Correct 16 ms 14828 KB Output is correct
9 Correct 36 ms 16236 KB Output is correct
10 Correct 71 ms 19456 KB Output is correct
11 Correct 75 ms 21100 KB Output is correct
12 Correct 82 ms 21484 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 17888 KB Output is correct
2 Correct 94 ms 20324 KB Output is correct
3 Correct 344 ms 31504 KB Output is correct
4 Correct 155 ms 27720 KB Output is correct
5 Correct 680 ms 69928 KB Output is correct
6 Correct 516 ms 98628 KB Output is correct
7 Correct 775 ms 111708 KB Output is correct
8 Correct 662 ms 77788 KB Output is correct
9 Correct 59 ms 18656 KB Output is correct
10 Correct 94 ms 21476 KB Output is correct
11 Correct 621 ms 84560 KB Output is correct
12 Correct 737 ms 87284 KB Output is correct
13 Correct 915 ms 106084 KB Output is correct
14 Correct 972 ms 110924 KB Output is correct
15 Correct 819 ms 107620 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 18036 KB Output is correct
2 Correct 87 ms 20328 KB Output is correct
3 Correct 136 ms 23904 KB Output is correct
4 Correct 146 ms 28768 KB Output is correct
5 Correct 705 ms 102844 KB Output is correct
6 Correct 600 ms 118164 KB Output is correct
7 Correct 3277 ms 290524 KB Output is correct
8 Correct 6321 ms 412360 KB Output is correct
9 Correct 71 ms 18760 KB Output is correct
10 Correct 844 ms 108640 KB Output is correct
11 Correct 11465 ms 390332 KB Output is correct
12 Correct 14698 ms 414768 KB Output is correct
13 Correct 11510 ms 403468 KB Output is correct
14 Correct 13676 ms 417032 KB Output is correct
15 Correct 10581 ms 390544 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14828 KB Output is correct
2 Correct 14 ms 14572 KB Output is correct
3 Correct 15 ms 14956 KB Output is correct
4 Correct 18 ms 15084 KB Output is correct
5 Correct 30 ms 15488 KB Output is correct
6 Correct 59 ms 21116 KB Output is correct
7 Correct 12 ms 14672 KB Output is correct
8 Correct 16 ms 14828 KB Output is correct
9 Correct 36 ms 16236 KB Output is correct
10 Correct 71 ms 19456 KB Output is correct
11 Correct 75 ms 21100 KB Output is correct
12 Correct 82 ms 21484 KB Output is correct
13 Correct 61 ms 17888 KB Output is correct
14 Correct 94 ms 20324 KB Output is correct
15 Correct 344 ms 31504 KB Output is correct
16 Correct 155 ms 27720 KB Output is correct
17 Correct 680 ms 69928 KB Output is correct
18 Correct 516 ms 98628 KB Output is correct
19 Correct 775 ms 111708 KB Output is correct
20 Correct 662 ms 77788 KB Output is correct
21 Correct 59 ms 18656 KB Output is correct
22 Correct 94 ms 21476 KB Output is correct
23 Correct 621 ms 84560 KB Output is correct
24 Correct 737 ms 87284 KB Output is correct
25 Correct 915 ms 106084 KB Output is correct
26 Correct 972 ms 110924 KB Output is correct
27 Correct 819 ms 107620 KB Output is correct
28 Correct 49 ms 18036 KB Output is correct
29 Correct 87 ms 20328 KB Output is correct
30 Correct 136 ms 23904 KB Output is correct
31 Correct 146 ms 28768 KB Output is correct
32 Correct 705 ms 102844 KB Output is correct
33 Correct 600 ms 118164 KB Output is correct
34 Correct 3277 ms 290524 KB Output is correct
35 Correct 6321 ms 412360 KB Output is correct
36 Correct 71 ms 18760 KB Output is correct
37 Correct 844 ms 108640 KB Output is correct
38 Correct 11465 ms 390332 KB Output is correct
39 Correct 14698 ms 414768 KB Output is correct
40 Correct 11510 ms 403468 KB Output is correct
41 Correct 13676 ms 417032 KB Output is correct
42 Correct 10581 ms 390544 KB Output is correct
43 Correct 1763 ms 77136 KB Output is correct
44 Correct 4978 ms 416144 KB Output is correct
45 Correct 2196 ms 93892 KB Output is correct
46 Correct 6245 ms 414120 KB Output is correct
47 Correct 74 ms 19552 KB Output is correct
48 Correct 101 ms 23396 KB Output is correct
49 Correct 707 ms 102016 KB Output is correct
50 Correct 1057 ms 122484 KB Output is correct
51 Correct 3564 ms 102488 KB Output is correct
52 Correct 6640 ms 188684 KB Output is correct
53 Correct 5604 ms 184880 KB Output is correct
54 Correct 8343 ms 248100 KB Output is correct
55 Correct 7272 ms 236360 KB Output is correct
56 Correct 8295 ms 294964 KB Output is correct
57 Correct 9165 ms 346456 KB Output is correct
58 Correct 12039 ms 361708 KB Output is correct
59 Correct 10465 ms 389188 KB Output is correct
60 Correct 13439 ms 417164 KB Output is correct