oj.uz

Submission #114296

# Submission time Handle Problem Language Result Execution time Memory
114296 2019-05-31T18:21:41 Z dorijanlendvaj Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 3000 ms 47796 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back

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

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;
bool re[SZ/30][SZ/30];
vector<pair<ll,int>> ht[SZ],ht1[SZ];
vector<int> sv,sv1;
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<8;++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<8;++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;
	n=R;
	m=C;
	--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) re[a.x][a.y]=1;
	for (auto a: prr) change(a.x*200000ll+a.y,1,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) cout<<a.x<<' '<<a.y<<endl;
}

int cnt,z[61][61],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;
}

bool rok(int i,int j,int x1,int y1,int x2,int y2)
{
	return (i>=x1 && j>=y1 && i<=x2 && j<=y2 && !re[i][j]);
}

int colour(int ar, int ac, int br, int bc) {
    int x1=ar-1,x2=br-1,y1=ac-1,y2=bc-1;
    for (int i=x1;i<=x2;++i) for (int j=y1;j<=y2;++j)
    {
    	if (re[i][j]) continue;
    	add(i*60+j);
    	for (int k=0;k<4;++k)
    	{
    		int i1=i+dx[k],j1=j+dy[k];
    		if (rok(i1,j1,x1,y1,x2,y2))
    		{
    			merge(i*60+j,i1*60+j1);
			}
		}
	}
    int ans=cnt;
    clear();
	return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4352 KB Output is correct
2 Correct 14 ms 4608 KB Output is correct
3 Correct 30 ms 4480 KB Output is correct
4 Correct 29 ms 4352 KB Output is correct
5 Correct 13 ms 4608 KB Output is correct
6 Correct 5 ms 4224 KB Output is correct
7 Correct 5 ms 4224 KB Output is correct
8 Correct 5 ms 4224 KB Output is correct
9 Correct 5 ms 4224 KB Output is correct
10 Correct 5 ms 4224 KB Output is correct
11 Correct 23 ms 4480 KB Output is correct
12 Correct 20 ms 4480 KB Output is correct
13 Correct 15 ms 4736 KB Output is correct
14 Correct 12 ms 4736 KB Output is correct
15 Correct 5 ms 4224 KB Output is correct
16 Correct 4 ms 4224 KB Output is correct
17 Correct 4 ms 4224 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4224 KB Output is correct
2 Correct 4 ms 4224 KB Output is correct
3 Execution timed out 3020 ms 28428 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4224 KB Output is correct
2 Runtime error 216 ms 47796 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4352 KB Output is correct
2 Correct 14 ms 4608 KB Output is correct
3 Correct 30 ms 4480 KB Output is correct
4 Correct 29 ms 4352 KB Output is correct
5 Correct 13 ms 4608 KB Output is correct
6 Correct 5 ms 4224 KB Output is correct
7 Correct 5 ms 4224 KB Output is correct
8 Correct 5 ms 4224 KB Output is correct
9 Correct 5 ms 4224 KB Output is correct
10 Correct 5 ms 4224 KB Output is correct
11 Correct 23 ms 4480 KB Output is correct
12 Correct 20 ms 4480 KB Output is correct
13 Correct 15 ms 4736 KB Output is correct
14 Correct 12 ms 4736 KB Output is correct
15 Correct 5 ms 4224 KB Output is correct
16 Correct 4 ms 4224 KB Output is correct
17 Correct 4 ms 4224 KB Output is correct
18 Execution timed out 3020 ms 29056 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4352 KB Output is correct
2 Correct 14 ms 4608 KB Output is correct
3 Correct 30 ms 4480 KB Output is correct
4 Correct 29 ms 4352 KB Output is correct
5 Correct 13 ms 4608 KB Output is correct
6 Correct 5 ms 4224 KB Output is correct
7 Correct 5 ms 4224 KB Output is correct
8 Correct 5 ms 4224 KB Output is correct
9 Correct 5 ms 4224 KB Output is correct
10 Correct 5 ms 4224 KB Output is correct
11 Correct 23 ms 4480 KB Output is correct
12 Correct 20 ms 4480 KB Output is correct
13 Correct 15 ms 4736 KB Output is correct
14 Correct 12 ms 4736 KB Output is correct
15 Correct 5 ms 4224 KB Output is correct
16 Correct 4 ms 4224 KB Output is correct
17 Correct 4 ms 4224 KB Output is correct
18 Execution timed out 3020 ms 29056 KB Time limit exceeded
19 Halted 0 ms 0 KB -