oj.uz

Submission #65095

# Submission time Handle Problem Language Result Execution time Memory
65095 2018-08-06T15:36:47 Z zscoder Collapse (JOI18_collapse) C++17
100 / 100
 9743 ms 99964 KB 
#include "collapse.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

struct DSU
{
	vector<int> par;
	vector<int> rank;
	vector<int> used;
	void init(int n)
	{
		par.clear(); rank.clear(); used.clear();
		for(int i=0;i<n;i++)
		{
			par.pb(i); rank.pb(1);
		}
	}
	int rt(int u)
	{
		if(par[u]==u) return u;
		else return rt(par[u]);
	}
	bool merge(int u, int v)
	{
		u=rt(u); v=rt(v);
		if(u==v) return false;
		////cerr<<"MERGE : "<<u<<' '<<v<<'\n';
		if(rank[u]<rank[v]) swap(u,v);
		used.pb(u); used.pb(v);
		rank[u]+=rank[v];
		par[v]=u;
		return true;
	}
	void reset()
	{
		for(int v:used) par[v]=v,rank[v]=1;
		used.clear();
	}
};

int ans[123456];

const int C = 800;
int n;

ii rev(ii edge)
{
	return mp(n-1-edge.fi,n-1-edge.se);
}

bool cmp(ii a, ii b)
{
	if(a.se!=b.se) return a.se<b.se;
	else return a.fi<b.fi;
}

void solve(vector<pair<int,pair<int,shared_ptr<vector<ii> > > > > query, vector<ii> fixed)
{
	int ptr_fixed = 0;
	DSU general; general.init(n); DSU specific; specific.init(n);
	int cc=0;
	for(auto x:query) 
	{
		int pos = x.fi; int lab = x.se.fi;
		while(ptr_fixed<fixed.size()&&fixed[ptr_fixed].se<=pos)
		{
			//cerr<<"MERGE : "<<fixed[ptr_fixed].fi<<' '<<fixed[ptr_fixed].se<<'\n';
			cc+=general.merge(fixed[ptr_fixed].fi,fixed[ptr_fixed].se); //amortized O(n)
			ptr_fixed++;
		}
		//O(sqrt(n))
		int c=0;
		for(auto it: *x.se.se)
		{
			if(it.se<=pos) 
			{
				//cerr<<"MERGE : "<<it.fi<<' '<<it.se<<' '<<general.rt(it.fi)<<' '<<general.rt(it.se)<<'\n';
				c+=specific.merge(general.rt(it.fi),general.rt(it.se));
			}
		}
		//cerr<<"CC : "<<lab<<' '<<pos<<' '<<cc+c<<'\n';
		ans[lab]+=pos+1-(cc+c);
		specific.reset();
	}
}

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
) 
{
	vi answer; answer.resize(int(W.size())); n=N;
	set<ii> curset; //set of current paths
	vector<pair<int,ii> > queries;
	for(int i=0;i<T.size();i++)
	{
		if(X[i]>Y[i]) swap(X[i],Y[i]);
	}
	for(int i=0;i<W.size();i++)
	{
		queries.pb(mp(W[i],mp(P[i],i)));
	}
	sort(queries.begin(),queries.end());
	int curptr = 0;
	for(int l=0;l<T.size();l+=C) //O(sqrt(N))
	{
		int r = min(l+C-1,int(T.size())-1);
		//solve all queries where l<=W<=r
		set<ii> fixed = curset; //stores the edges that wont be changed this block
		set<ii> change; //stores the set of edges that will be changed this block
		for(int i=l;i<=r;i++) change.insert(mp(X[i],Y[i]));
		set<ii> dynamic; //stores the current progress of the edges changed in this block
		for(auto edge:change)
		{
			if(fixed.find(edge)!=fixed.end())
			{
				fixed.erase(edge); dynamic.insert(edge);
			}
		}
		vector<pair<int,pair<int,shared_ptr<vector<ii> > > > > query1,query2;
		for(int i=l;i<=r;i++) //O(sqrt(N))
		{
			if(!T[i])
			{
				curset.insert(mp(X[i],Y[i])); dynamic.insert(mp(X[i],Y[i]));
			}
			else
			{
				curset.erase(mp(X[i],Y[i])); dynamic.erase(mp(X[i],Y[i]));
			}
			shared_ptr<vector<ii> > p1(new vector<ii>), p2(new vector<ii>); //shared_ptr new trick acquired
			for(auto edge:dynamic) //O(sqrt(N))
			{
				p1->pb(edge);
				p2->pb(mp(rev(edge).se,rev(edge).fi));
			}
			while(curptr<queries.size()&&queries[curptr].fi<=i)
			{
				query1.pb(mp(queries[curptr].se.fi,mp(queries[curptr].se.se, p1)));
				query2.pb(mp(n-2-queries[curptr].se.fi,mp(queries[curptr].se.se, p2)));
				curptr++;
			}
		}
		sort(query1.begin(),query1.end());
		sort(query2.begin(),query2.end()); //hope shared pointer doesn't get sorted
		vector<ii> fixed2;
		for(auto x:fixed) fixed2.pb(x);
		sort(fixed2.begin(),fixed2.end(),cmp);
		solve(query1, fixed2);
		for(auto &x:fixed2) {x.fi=n-1-x.fi; x.se=n-1-x.se; swap(x.fi,x.se);}
		sort(fixed2.begin(),fixed2.end(),cmp);
		solve(query2, fixed2);
	}
	for(int i=0;i<answer.size();i++) answer[i]=ans[i];
	return answer;
}

Compilation message

collapse.cpp: In function 'void solve(std::vector<std::pair<int, std::pair<int, std::shared_ptr<std::vector<std::pair<int, int> > > > > >, std::vector<std::pair<int, int> >)':
collapse.cpp:80:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr_fixed<fixed.size()&&fixed[ptr_fixed].se<=pos)
         ~~~~~~~~~^~~~~~~~~~~~~
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:114:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T.size();i++)
              ~^~~~~~~~~
collapse.cpp:118:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<W.size();i++)
              ~^~~~~~~~~
collapse.cpp:124:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int l=0;l<T.size();l+=C) //O(sqrt(N))
              ~^~~~~~~~~
collapse.cpp:156:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(curptr<queries.size()&&queries[curptr].fi<=i)
          ~~~~~~^~~~~~~~~~~~~~~
collapse.cpp:173:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<answer.size();i++) answer[i]=ans[i];
              ~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 724 KB Output is correct
2 Correct 4 ms 1248 KB Output is correct
3 Correct 7 ms 1484 KB Output is correct
4 Correct 7 ms 1484 KB Output is correct
5 Correct 16 ms 1484 KB Output is correct
6 Correct 100 ms 6344 KB Output is correct
7 Correct 8 ms 6344 KB Output is correct
8 Correct 10 ms 6344 KB Output is correct
9 Correct 31 ms 6344 KB Output is correct
10 Correct 88 ms 6344 KB Output is correct
11 Correct 131 ms 6924 KB Output is correct
12 Correct 124 ms 7104 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 15404 KB Output is correct
2 Correct 110 ms 15420 KB Output is correct
3 Correct 328 ms 15420 KB Output is correct
4 Correct 119 ms 15980 KB Output is correct
5 Correct 995 ms 15980 KB Output is correct
6 Correct 616 ms 15980 KB Output is correct
7 Correct 7604 ms 28968 KB Output is correct
8 Correct 1063 ms 28968 KB Output is correct
9 Correct 78 ms 28968 KB Output is correct
10 Correct 123 ms 28968 KB Output is correct
11 Correct 449 ms 28968 KB Output is correct
12 Correct 1730 ms 28968 KB Output is correct
13 Correct 5317 ms 34360 KB Output is correct
14 Correct 8026 ms 43580 KB Output is correct
15 Correct 7421 ms 46348 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 46348 KB Output is correct
2 Correct 123 ms 46348 KB Output is correct
3 Correct 130 ms 46348 KB Output is correct
4 Correct 130 ms 46348 KB Output is correct
5 Correct 520 ms 46348 KB Output is correct
6 Correct 604 ms 46348 KB Output is correct
7 Correct 4698 ms 46348 KB Output is correct
8 Correct 7104 ms 46348 KB Output is correct
9 Correct 86 ms 46348 KB Output is correct
10 Correct 888 ms 46348 KB Output is correct
11 Correct 8565 ms 52632 KB Output is correct
12 Correct 9743 ms 55192 KB Output is correct
13 Correct 9029 ms 57792 KB Output is correct
14 Correct 9451 ms 60148 KB Output is correct
15 Correct 8744 ms 62380 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 724 KB Output is correct
2 Correct 4 ms 1248 KB Output is correct
3 Correct 7 ms 1484 KB Output is correct
4 Correct 7 ms 1484 KB Output is correct
5 Correct 16 ms 1484 KB Output is correct
6 Correct 100 ms 6344 KB Output is correct
7 Correct 8 ms 6344 KB Output is correct
8 Correct 10 ms 6344 KB Output is correct
9 Correct 31 ms 6344 KB Output is correct
10 Correct 88 ms 6344 KB Output is correct
11 Correct 131 ms 6924 KB Output is correct
12 Correct 124 ms 7104 KB Output is correct
13 Correct 93 ms 15404 KB Output is correct
14 Correct 110 ms 15420 KB Output is correct
15 Correct 328 ms 15420 KB Output is correct
16 Correct 119 ms 15980 KB Output is correct
17 Correct 995 ms 15980 KB Output is correct
18 Correct 616 ms 15980 KB Output is correct
19 Correct 7604 ms 28968 KB Output is correct
20 Correct 1063 ms 28968 KB Output is correct
21 Correct 78 ms 28968 KB Output is correct
22 Correct 123 ms 28968 KB Output is correct
23 Correct 449 ms 28968 KB Output is correct
24 Correct 1730 ms 28968 KB Output is correct
25 Correct 5317 ms 34360 KB Output is correct
26 Correct 8026 ms 43580 KB Output is correct
27 Correct 7421 ms 46348 KB Output is correct
28 Correct 69 ms 46348 KB Output is correct
29 Correct 123 ms 46348 KB Output is correct
30 Correct 130 ms 46348 KB Output is correct
31 Correct 130 ms 46348 KB Output is correct
32 Correct 520 ms 46348 KB Output is correct
33 Correct 604 ms 46348 KB Output is correct
34 Correct 4698 ms 46348 KB Output is correct
35 Correct 7104 ms 46348 KB Output is correct
36 Correct 86 ms 46348 KB Output is correct
37 Correct 888 ms 46348 KB Output is correct
38 Correct 8565 ms 52632 KB Output is correct
39 Correct 9743 ms 55192 KB Output is correct
40 Correct 9029 ms 57792 KB Output is correct
41 Correct 9451 ms 60148 KB Output is correct
42 Correct 8744 ms 62380 KB Output is correct
43 Correct 540 ms 62380 KB Output is correct
44 Correct 6990 ms 62984 KB Output is correct
45 Correct 1032 ms 62984 KB Output is correct
46 Correct 7019 ms 68000 KB Output is correct
47 Correct 85 ms 68000 KB Output is correct
48 Correct 122 ms 68000 KB Output is correct
49 Correct 573 ms 68000 KB Output is correct
50 Correct 1262 ms 68000 KB Output is correct
51 Correct 1601 ms 68000 KB Output is correct
52 Correct 3938 ms 69456 KB Output is correct
53 Correct 3740 ms 71936 KB Output is correct
54 Correct 5922 ms 77092 KB Output is correct
55 Correct 5400 ms 79860 KB Output is correct
56 Correct 6037 ms 84664 KB Output is correct
57 Correct 7155 ms 89416 KB Output is correct
58 Correct 8259 ms 92716 KB Output is correct
59 Correct 8489 ms 97244 KB Output is correct
60 Correct 9315 ms 99964 KB Output is correct