oj.uz

Submission #120394

# Submission time Handle Problem Language Result Execution time Memory
120394 2019-06-24T10:41:16 Z baluteshih Flood (IOI07_flood) C++14
100 / 100
 202 ms 20580 KB 
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

struct mode
{
	int x,y,up=-1,dwn=-1,lft=-1,rit=-1;
	bool operator<(const mode &a)const{
		if(x==a.x) return y<a.y;
		return x<a.x;
	}
}dots[100105];

int boss[400105];
vector<int> G[400105],ans;
queue<int> q;
int dis[400105];
map<int,int> mp;

bool yee(mode a,mode b)
{
	if(a.y==b.y) return a.x>b.x;
	return a.y>b.y;
}

int finds(int x)
{
	if(x==boss[x]) return x;
	return boss[x]=finds(boss[x]);
}

void Union(int x,int y)
{
	x=finds(x),y=finds(y);
	boss[x]=y;
}
 
int main()
{jizz
	int n,w,a,b;
	cin >> n;
	for(int i=1;i<=n;++i)
		cin >> dots[i].x >> dots[i].y;
	cin >> w;
	for(int i=1;i<=w;++i)
	{
		cin >> a >> b;
		if(dots[b]<dots[a]) swap(a,b);
		if(dots[a].x==dots[b].x)
			dots[b].dwn=i,dots[a].up=i;
		else
			dots[a].rit=i,dots[b].lft=i;
	}
	for(int i=0;i<=2*w+50;++i) boss[i]=i;
	
	sort(dots+1,dots+n+1);
	for(int i=1,j=1;i<=n;)
	{
		for(;j<=n&&dots[i].x==dots[j].x;++j)
			if(~dots[j].dwn)
			{
				auto p=mp.lower_bound(dots[j].y);
				if(p!=mp.end()) Union(dots[j].dwn*2,p->S*2+1);
				else Union(dots[j].dwn*2,0);
				if(p!=mp.begin()) --p,Union(dots[j].dwn*2,p->S*2);
				else Union(dots[j].dwn*2,0);
			}
		for(int k=i;k<j;++k)
		{
			mp.erase(dots[k].y);
			if(~dots[k].rit) mp[dots[k].y]=dots[k].rit;
		}
		for(;i<j;++i)
			if(~dots[i].dwn)
			{
				auto p=mp.lower_bound(dots[i].y);
				if(p!=mp.end()) Union(dots[i].dwn*2+1,p->S*2+1);
				else Union(dots[i].dwn*2+1,0);
				if(p!=mp.begin()) --p,Union(dots[i].dwn*2+1,p->S*2);
				else Union(dots[i].dwn*2+1,0);
			}
	}
	mp.clear();
	
	sort(dots+1,dots+n+1,yee);
	for(int i=1,j=1;i<=n;)
	{
		for(;j<=n&&dots[i].y==dots[j].y;++j)
			if(~dots[j].rit)
			{
				auto p=mp.upper_bound(dots[j].x);
				if(p!=mp.end()) Union(dots[j].rit*2,p->S*2);
				else Union(dots[j].rit*2,0);
				if(p!=mp.begin()) --p,Union(dots[j].rit*2,p->S*2+1);
				else Union(dots[j].rit*2,0);
			}
		for(int k=i;k<j;++k)
		{
			mp.erase(dots[k].x);
			if(~dots[k].dwn) mp[dots[k].x]=dots[k].dwn;
		}
		for(;i<j;++i)
			if(~dots[i].rit)
			{
				auto p=mp.upper_bound(dots[i].x);
				if(p!=mp.end()) Union(dots[i].rit*2+1,p->S*2);
				else Union(dots[i].rit*2+1,0);
				if(p!=mp.begin()) --p,Union(dots[i].rit*2+1,p->S*2+1);
				else Union(dots[i].rit*2+1,0);
			}
	}
	mp.clear();
	
	for(int i=1;i<=n;++i)
	{
		if(!~dots[i].dwn&&!~dots[i].rit&&!~dots[i].lft&&~dots[i].up)
			Union(dots[i].up*2,dots[i].up*2+1);
		if(!~dots[i].dwn&&!~dots[i].rit&&~dots[i].lft&&!~dots[i].up)
			Union(dots[i].lft*2,dots[i].lft*2+1);
		if(!~dots[i].dwn&&~dots[i].rit&&!~dots[i].lft&&!~dots[i].up)
			Union(dots[i].rit*2,dots[i].rit*2+1);
		if(~dots[i].dwn&&!~dots[i].rit&&!~dots[i].lft&&!~dots[i].up)
			Union(dots[i].dwn*2,dots[i].dwn*2+1);
			
		if(!~dots[i].dwn&&!~dots[i].rit&&~dots[i].lft&&~dots[i].up)
			Union(dots[i].lft*2+1,dots[i].up*2+1);
		if(!~dots[i].dwn&&~dots[i].rit&&!~dots[i].lft&&~dots[i].up)
			Union(dots[i].rit*2+1,dots[i].up*2);
		if(~dots[i].dwn&&!~dots[i].rit&&~dots[i].lft&&!~dots[i].up)
			Union(dots[i].lft*2,dots[i].dwn*2+1);
		if(~dots[i].dwn&&~dots[i].rit&&!~dots[i].lft&&!~dots[i].up)
			Union(dots[i].rit*2,dots[i].dwn*2);
			
		if(~dots[i].dwn&&~dots[i].up)
		{
			if(!~dots[i].lft) Union(dots[i].dwn*2,dots[i].up*2);
			if(!~dots[i].rit) Union(dots[i].dwn*2+1,dots[i].up*2+1);
		}
		if(~dots[i].lft&&~dots[i].rit)
		{
			if(!~dots[i].dwn) Union(dots[i].lft*2+1,dots[i].rit*2+1);
			if(!~dots[i].up) Union(dots[i].lft*2,dots[i].rit*2);
		}
	}
		
	for(int i=1;i<=n;++i)
	{
		if(~dots[i].dwn&&finds(dots[i].dwn*2)!=finds(dots[i].dwn*2+1))
			G[boss[dots[i].dwn*2]].pb(boss[dots[i].dwn*2+1]),G[boss[dots[i].dwn*2+1]].pb(boss[dots[i].dwn*2]);
		if(~dots[i].rit&&finds(dots[i].rit*2)!=finds(dots[i].rit*2+1))
			G[boss[dots[i].rit*2]].pb(boss[dots[i].rit*2+1]),G[boss[dots[i].rit*2+1]].pb(boss[dots[i].rit*2]);
	}
	
	dis[finds(0)]=1,q.push(boss[0]);
	while(!q.empty())
	{
		auto u=q.front();
		q.pop();
		for(int i:G[u])
			if(!dis[i])	
				dis[i]=dis[u]+1,q.push(i);
	}
	for(int i=1;i<=n;++i)
	{
		if(~dots[i].dwn&&dis[boss[dots[i].dwn*2]]==dis[boss[dots[i].dwn*2+1]])
			ans.pb(dots[i].dwn);
		if(~dots[i].rit&&dis[boss[dots[i].rit*2]]==dis[boss[dots[i].rit*2+1]])
			ans.pb(dots[i].rit);
	}
	
	cout << ans.size() << "\n";
	for(int i:ans)
		cout << i << "\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12160 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12100 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 11 ms 12032 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12032 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12160 KB Output is correct
2 Correct 12 ms 12160 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12036 KB Output is correct
2 Correct 11 ms 12032 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12160 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 12800 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 14344 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 15608 KB Output is correct
2 Correct 180 ms 17012 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 16084 KB Output is correct
2 Correct 202 ms 20580 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 16884 KB Output is correct
2 Correct 89 ms 16372 KB Output is correct