oj.uz

Submission #368799

# Submission time Handle Problem Language Result Execution time Memory
368799 2021-02-20T07:14:39 Z kig9981 Collapse (JOI18_collapse) C++17
35 / 100
 1977 ms 524292 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=300, SZ=1<<17;
vector<int> adj[100000], BB, tree[2*SZ];
vector<tuple<int,int,int>> qry;
vector<pair<int,int>> E;
map<pair<int,int>,int> idx;
int N, ans[100000], B[100000], LL[100000], color[100000], cnt[100000];
bool EX[100000];

void add_edge(int s, int e, int v)
{
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) tree[s++].push_back(v);
		if(~e&1) tree[e--].push_back(v);
	}
}

void flip_edge(int c, int i)
{
	if(EX[c]) add_edge(LL[c],i-1,c);
	else LL[c]=i;
	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 bit, int s, int e)
{
	int m=(s+e)>>1, bsz=BB.size();
	if(qry.size()<=s) return;
	for(auto v: tree[bit]) union_(E[v].first,E[v].second);
	if(s==e) {
		ans[get<2>(qry[m])]=N-BB.size();
		restore(bsz);
		return;
	}
	solve(2*bit,s,m);
	solve(2*bit+1,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));
	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(int i=0;i<E.size();i++) if(EX[i]) add_edge(LL[i],Q-1,i);
	for(int i=0;i<N;i++) cnt[color[i]=i]=1;
	solve(1,0,SZ-1);
	return vector<int>(ans,ans+Q);
}

Compilation message

collapse.cpp: In function 'void restore(int)':
collapse.cpp:53:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |  while(BB.size()>sz) {
      |        ~~~~~~~~~^~~
collapse.cpp: In function 'void solve(int, int, int)':
collapse.cpp:63:15: warning: comparison of integer expressions of different signedness: 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |  if(qry.size()<=s) return;
      |     ~~~~~~~~~~^~~
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:118: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]
  118 |  for(int i=0;i<E.size();i++) if(EX[i]) add_edge(LL[i],Q-1,i);
      |              ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 9708 KB Output is correct
2 Correct 8 ms 9452 KB Output is correct
3 Correct 10 ms 9708 KB Output is correct
4 Correct 12 ms 9708 KB Output is correct
5 Correct 23 ms 10044 KB Output is correct
6 Correct 41 ms 14444 KB Output is correct
7 Correct 9 ms 9580 KB Output is correct
8 Correct 11 ms 9836 KB Output is correct
9 Correct 26 ms 10348 KB Output is correct
10 Correct 45 ms 12012 KB Output is correct
11 Correct 79 ms 14468 KB Output is correct
12 Correct 58 ms 14572 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 12768 KB Output is correct
2 Correct 50 ms 14456 KB Output is correct
3 Correct 226 ms 24580 KB Output is correct
4 Correct 101 ms 18144 KB Output is correct
5 Correct 420 ms 34424 KB Output is correct
6 Correct 354 ms 38680 KB Output is correct
7 Correct 459 ms 53912 KB Output is correct
8 Correct 405 ms 39996 KB Output is correct
9 Correct 56 ms 14304 KB Output is correct
10 Correct 79 ms 16740 KB Output is correct
11 Correct 349 ms 36604 KB Output is correct
12 Correct 477 ms 43832 KB Output is correct
13 Correct 614 ms 53212 KB Output is correct
14 Correct 585 ms 56284 KB Output is correct
15 Correct 547 ms 54996 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 12752 KB Output is correct
2 Correct 54 ms 14564 KB Output is correct
3 Correct 76 ms 16480 KB Output is correct
4 Correct 127 ms 18656 KB Output is correct
5 Correct 320 ms 40296 KB Output is correct
6 Correct 318 ms 48996 KB Output is correct
7 Runtime error 1977 ms 524292 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 9708 KB Output is correct
2 Correct 8 ms 9452 KB Output is correct
3 Correct 10 ms 9708 KB Output is correct
4 Correct 12 ms 9708 KB Output is correct
5 Correct 23 ms 10044 KB Output is correct
6 Correct 41 ms 14444 KB Output is correct
7 Correct 9 ms 9580 KB Output is correct
8 Correct 11 ms 9836 KB Output is correct
9 Correct 26 ms 10348 KB Output is correct
10 Correct 45 ms 12012 KB Output is correct
11 Correct 79 ms 14468 KB Output is correct
12 Correct 58 ms 14572 KB Output is correct
13 Correct 41 ms 12768 KB Output is correct
14 Correct 50 ms 14456 KB Output is correct
15 Correct 226 ms 24580 KB Output is correct
16 Correct 101 ms 18144 KB Output is correct
17 Correct 420 ms 34424 KB Output is correct
18 Correct 354 ms 38680 KB Output is correct
19 Correct 459 ms 53912 KB Output is correct
20 Correct 405 ms 39996 KB Output is correct
21 Correct 56 ms 14304 KB Output is correct
22 Correct 79 ms 16740 KB Output is correct
23 Correct 349 ms 36604 KB Output is correct
24 Correct 477 ms 43832 KB Output is correct
25 Correct 614 ms 53212 KB Output is correct
26 Correct 585 ms 56284 KB Output is correct
27 Correct 547 ms 54996 KB Output is correct
28 Correct 44 ms 12752 KB Output is correct
29 Correct 54 ms 14564 KB Output is correct
30 Correct 76 ms 16480 KB Output is correct
31 Correct 127 ms 18656 KB Output is correct
32 Correct 320 ms 40296 KB Output is correct
33 Correct 318 ms 48996 KB Output is correct
34 Runtime error 1977 ms 524292 KB Execution killed with signal 9
35 Halted 0 ms 0 KB -