제출 #120385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
120385		baluteshih	Flood (IOI07_flood)	C++14	73 / 100	213 ms	24472 KiB

flood

#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define int long long
#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,dwn=-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;
}
 
int32_t 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;
		else
			dots[a].rit=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&&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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 3 / 3
• Subtask 5: 10 / 10
• Subtask 6: 3 / 3
• Subtask 7: 3 / 3
• Subtask 8: 3 / 3
• Subtask 9: 3 / 3
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9