oj.uz

Submission #114295

# Submission time Handle Problem Language Result Execution time Memory
114295 2019-05-31T18:15:31 Z dorijanlendvaj Land of the Rainbow Gold (APIO17_rainbow) C++14
24 / 100
 3000 ms 103332 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define pbds tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>

using namespace std;
using namespace __gnu_pbds;
using ll=long long;

pbds seg1[200010],seg2[200010];

int dx[]={0,1,0,-1,1,1,-1,-1};
int dy[]={1,0,-1,0,1,-1,1,-1};
int n,m;
set<pii> s;
vector<pii> ou,prr;
const int SZ=32987;
vector<pair<ll,int>> ht[SZ],ht1[SZ];
vector<int> sv,sv1,aaa[200010],bbb[200010];
vector<pii> out;
vector<pii> in[100010];

void change(ll i,int x,bool t)
{
	if (t==0)
	{
		ll i1=i;
		i+=1872432922ll;
		i^=0x95872901;
		i%=SZ;
		//cout<<i<<' '<<i1<<endl;
		for (auto &a: ht[i]) if (a.x==i1)
		{
			a.y=x;
		//	cout<<"found"<<endl;
			return;
		}
		//cout<<"made"<<endl;
		ht[i].pb({i1,x});
		sv.pb(i);
	}
	else
	{
		ll i1=i;
		i+=1872432922ll;
		i^=0x95872901;
		i%=SZ;
		for (auto &a: ht1[i]) if (a.x==i1)
		{
			a.y=x;
			return;
		}
		ht1[i].pb({i1,x});
		sv1.pb(i);
	}
}

int get(ll i,bool t)
{
	if (t==0)
	{
		ll i1=i;
		i+=1872432922ll;
		i^=0x95872901;
		i%=SZ;
		//cout<<i<<endl;
		for (auto a: ht[i]) if (a.x==i1) return a.y;
		return 0;
	}
	else
	{
		ll i1=i;
		i+=1872432922ll;
		i^=0x95872901;
		i%=SZ;
		for (auto a: ht1[i]) if (a.x==i1) return a.y;
		return 0;
	}
}

void clearHT(bool t)
{
	if (t==0)
	{
		for (auto a: sv) ht[a].clear();
		sv.clear();
	}
	else
	{
		for (auto a: sv1) ht1[a].clear();
		sv1.clear();
	}
}

bool ok(int i,int j)
{
	if (get(i*200000ll+j,1)) return 0;
	for (int k=0;k<8;++k) if (get((i+dx[k])*200000ll+(j+dy[k]),1)==1) return 1;
	return 0;
}

void dfs(int i,int j)
{
	if (!ok(i,j)) return;
	change(i*200000ll+j,2,1);
	//cout<<i<<' '<<j<<endl;
	for (int k=0;k<4;++k)
	{
		int i1=i+dx[k],j1=j+dy[k];
		//cout<<i<<' '<<j<<' '<<i1<<' '<<j1<<endl;
		dfs(i1,j1);
	}
	//cout<<"end "<<i<<' '<<j<<endl;
}

void dfs2(int i,int j,int c)
{
	if (!ok(i,j)) return;
	change(i*200000ll+j,1000+c,1);
	in[c].pb({i,j});
	for (int k=0;k<4;++k)
	{
		int i1=i+dx[k],j1=j+dy[k];
		dfs2(i1,j1,c);
	}
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	set<pii> pros;
	--sr;
	--sc;
	for (int i=0;i<M;++i)
	{
		//if (s.find({sr,sc})!=s.end()) s.erase({sr,sc});
		pros.insert({sr,sc});
		for (int k=0;k<8;++k) s.insert({sr+dx[k],sc+dy[k]});
		if (S[i]=='W') --sc;
		if (S[i]=='E') ++sc;
		if (S[i]=='N') --sr;
		if (S[i]=='S') ++sr;
	}
	pros.insert({sr,sc});
	for (auto a: pros) prr.pb(a);
	for (auto a: prr) change(a.x*200000ll+a.y,1,1),seg1[a.x+1].insert(a.y+1),seg2[a.y+1].insert(a.x+1);
	for (int k=0;k<8;++k) s.insert({sr+dx[k],sc+dy[k]});
	for (auto a: pros) if (s.find(a)!=s.end()) s.erase(a);
	for (auto a: s) ou.pb(a);
	dfs(ou[0].x,ou[0].y);
	int cc=0;
	for (auto a: ou) if (ok(a.x,a.y)) dfs2(a.x,a.y,cc++);
	for (auto a: ou) aaa[a.x+1].pb(a.y+1),bbb[a.y+1].pb(a.x+1);
}

int cnt,par[1000050];
bool bio[100050];
vector<int> sss;
bool pos[1000050];
vector<int> nap;
//gp_hash_table<ll,int> nodes;

void add(int i)
{
	nap.pb(i);
	par[i]=i;
	pos[i]=1;
	++cnt;
}

int find(int i)
{
	if (!pos[i]) return -1;
	if (i==par[i]) return i;
	return par[i]=find(par[i]);
}

void merge(int a,int b)
{
	a=find(a);
	b=find(b);
	if (a==-1 || b==-1) return;
	if (a==b) return;
	par[a]=b;
	--cnt;
}

void clear()
{
	for (auto x: nap)
	{
		par[x]=-1;
		pos[x]=0;
	}
	nap.clear();
	cnt=0;
}

int colour(int ar, int ac, int br, int bc) {
    int x1=ar-1,x2=br-1,y1=ac-1,y2=bc-1;
    int cn=1;
    clearHT(0);
    int px=-100,py=-1;
    for (auto a: ou) if (a.x>=x1 && a.x<=x2 && a.y>=y1 && a.y<=y2)
    {
    	change(a.x*200000ll+a.y,cn,0);
    	add(cn++);
    	for (int k=0;k<4;++k)
    	{
    		merge(get((a.x+dx[k])*200000ll+(a.y+dy[k]),0),cn-1);
    		//cout<<a.x+dx[k]<<' '<<a.y+dy[k]<<' '<<get((a.x+dx[k])*200000ll+(a.y+dy[k]),0)<<' '<<(a.x+dx[k])*200000ll+(a.y+dy[k])<<endl;
		}
		//cout<<a.x<<' '<<a.y<<endl;
	}
	for (int i=x1+1;i<=x2+1;++i)
	{
		for (int j=1;j<aaa[i].size();++j) if (aaa[i][j-1]-1>=y1 && aaa[i][j]-1<=y2 && seg1[i].order_of_key(aaa[i][j-1])==seg1[i].order_of_key(aaa[i][j]))
		{
			ll x=(i-1)*200000ll+aaa[i][j-1]-1;
			ll y=(i-1)*200000ll+aaa[i][j]-1;
			//cout<<"red "<<i<<' '<<j<<' '<<x<<' '<<y<<endl;
			merge(get(x,0),get(y,0));
		}
	}
	for (int i=y1+1;i<=y2+1;++i)
	{
		for (int j=1;j<bbb[i].size();++j) if (bbb[i][j-1]-1>=x1 && bbb[i][j]-1<=x2 && seg2[i].order_of_key(bbb[i][j-1])==seg2[i].order_of_key(bbb[i][j]))
		{
			ll x=(i-1)+(bbb[i][j-1]-1)*200000ll;
			ll y=(i-1)+(bbb[i][j]-1)*200000ll;
			//cout<<"stupac "<<i<<' '<<j<<' '<<x<<' '<<y<<endl;
			merge(get(x,0),get(y,0));
		}
	}
	/*for (auto a: ou) if (a.x>=x1 && a.x<=x2 && a.y>=y1 && a.y<=y2)
	{
		int val=get(a.x*200000ll+a.y,1);
		//cout<<a.x<<' '<<a.y<<' '<<val<<endl;
		if (val>=1000 && !bio[val])
		{
			int no=get(a.x*200000ll+a.y,0);
			bio[val]=1;
			for (auto b: in[val-1000]) merge(get(b.x*200000ll+b.y,0),no);
		}
	}*/
	ll z=(y2-y1+1)*1ll*(x2-x1+1);
	if (cnt==0)
	{
		for (auto a: prr) if (a.x>=x1 && a.x<=x2 && a.y>=y1 && a.y<=y2) --z;
		if (z==0) return 0;
		return 1;
	}
	int ans=cnt;
	clear();
	return ans;
}

Compilation message

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:220:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=1;j<aaa[i].size();++j) if (aaa[i][j-1]-1>=y1 && aaa[i][j]-1<=y2 && seg1[i].order_of_key(aaa[i][j-1])==seg1[i].order_of_key(aaa[i][j]))
                ~^~~~~~~~~~~~~~
rainbow.cpp:230:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=1;j<bbb[i].size();++j) if (bbb[i][j-1]-1>=x1 && bbb[i][j]-1<=x2 && seg2[i].order_of_key(bbb[i][j-1])==seg2[i].order_of_key(bbb[i][j]))
                ~^~~~~~~~~~~~~~
rainbow.cpp:206:9: warning: unused variable 'px' [-Wunused-variable]
     int px=-100,py=-1;
         ^~
rainbow.cpp:206:17: warning: unused variable 'py' [-Wunused-variable]
     int px=-100,py=-1;
                 ^~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 45048 KB Output is correct
2 Correct 75 ms 45304 KB Output is correct
3 Correct 57 ms 45064 KB Output is correct
4 Correct 61 ms 45148 KB Output is correct
5 Correct 74 ms 45432 KB Output is correct
6 Correct 51 ms 44920 KB Output is correct
7 Correct 53 ms 44920 KB Output is correct
8 Correct 50 ms 44908 KB Output is correct
9 Correct 49 ms 44920 KB Output is correct
10 Correct 50 ms 44928 KB Output is correct
11 Correct 66 ms 45100 KB Output is correct
12 Incorrect 67 ms 45176 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 44920 KB Output is correct
2 Correct 55 ms 44960 KB Output is correct
3 Execution timed out 3030 ms 75432 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 44976 KB Output is correct
2 Correct 600 ms 98016 KB Output is correct
3 Correct 702 ms 94944 KB Output is correct
4 Correct 766 ms 99760 KB Output is correct
5 Correct 537 ms 83552 KB Output is correct
6 Correct 143 ms 51572 KB Output is correct
7 Correct 234 ms 58236 KB Output is correct
8 Correct 429 ms 86928 KB Output is correct
9 Correct 436 ms 81300 KB Output is correct
10 Correct 149 ms 52440 KB Output is correct
11 Correct 370 ms 68852 KB Output is correct
12 Correct 508 ms 96544 KB Output is correct
13 Correct 586 ms 93796 KB Output is correct
14 Correct 648 ms 92412 KB Output is correct
15 Correct 566 ms 81972 KB Output is correct
16 Correct 133 ms 50296 KB Output is correct
17 Correct 224 ms 58140 KB Output is correct
18 Correct 391 ms 81380 KB Output is correct
19 Correct 634 ms 95824 KB Output is correct
20 Correct 688 ms 97716 KB Output is correct
21 Correct 509 ms 88544 KB Output is correct
22 Correct 530 ms 83040 KB Output is correct
23 Correct 155 ms 52408 KB Output is correct
24 Correct 428 ms 70812 KB Output is correct
25 Correct 556 ms 103332 KB Output is correct
26 Correct 765 ms 99324 KB Output is correct
27 Correct 821 ms 99868 KB Output is correct
28 Correct 553 ms 86680 KB Output is correct
29 Correct 142 ms 50508 KB Output is correct
30 Correct 240 ms 58480 KB Output is correct
31 Correct 462 ms 83848 KB Output is correct
32 Correct 674 ms 97764 KB Output is correct
33 Correct 672 ms 97844 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 45048 KB Output is correct
2 Correct 75 ms 45304 KB Output is correct
3 Correct 57 ms 45064 KB Output is correct
4 Correct 61 ms 45148 KB Output is correct
5 Correct 74 ms 45432 KB Output is correct
6 Correct 51 ms 44920 KB Output is correct
7 Correct 53 ms 44920 KB Output is correct
8 Correct 50 ms 44908 KB Output is correct
9 Correct 49 ms 44920 KB Output is correct
10 Correct 50 ms 44928 KB Output is correct
11 Correct 66 ms 45100 KB Output is correct
12 Incorrect 67 ms 45176 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 45048 KB Output is correct
2 Correct 75 ms 45304 KB Output is correct
3 Correct 57 ms 45064 KB Output is correct
4 Correct 61 ms 45148 KB Output is correct
5 Correct 74 ms 45432 KB Output is correct
6 Correct 51 ms 44920 KB Output is correct
7 Correct 53 ms 44920 KB Output is correct
8 Correct 50 ms 44908 KB Output is correct
9 Correct 49 ms 44920 KB Output is correct
10 Correct 50 ms 44928 KB Output is correct
11 Correct 66 ms 45100 KB Output is correct
12 Incorrect 67 ms 45176 KB Output isn't correct
13 Halted 0 ms 0 KB -