Submission #411650

#	Time	Username	Problem	Language	Result	Execution time	Memory
411650		Jasiekstrz	Flood (IOI07_flood)	C++17	100 / 100	285 ms	17664 KiB

flood

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e5;
const int M=2e5;
struct Point
{
	int x,y;
};
struct State
{
	int x;
	bool side; // 0 - left fi->se, 1 - right fi->se
	int d;
};
Point pos[N+10];
vector<pair<int,int>> e[N+10];
pair<int,int> edge[M+10];
deque<State> dq;
bool vis[M+10][2];
int dac[M+10];
bool ans[M+10];
bool vis0[N+10];
void add_edge(int p,int ee,bool side,int d,bool fr) // side: false - counterclockwise
{
	/*
		 0
	   3 + 1
	     2
	*/
	vector<pair<int,int>> tmp;
	for(auto v:e[p])
	{
		int xd;
		if(pos[v.fi].x==pos[p].x)
		{
			if(pos[v.fi].y<pos[p].y)
				xd=0;
			else
				xd=2;
		}
		else
		{
			if(pos[v.fi].x<pos[p].x)
				xd=3;
			else
				xd=1;
		}
		tmp.emplace_back(xd,v.se);
	}
	sort(tmp.begin(),tmp.end());
	int bg;
	for(bg=0;tmp[bg].se!=ee;bg++);
	rotate(tmp.begin(),tmp.begin()+bg,tmp.end());
	State v;
	if(side)
	{
		v.x=tmp.back().se;
		v.side=(edge[v.x].fi!=p);
	}
	else
	{
		v.x=tmp[1%tmp.size()].se;
		v.side=(edge[v.x].fi==p);
	}
	v.d=d;
	if(!vis[v.x][v.side])
	{
		//cerr<<"add "<<v.x<<" "<<v.side<<" "<<v.d<<" by "<<ee<<" "<<p<<" "<<side<<" :\n";
		//for(auto vv:tmp)
		//	cerr<<"("<<vv.fi<<", "<<vv.se<<") ";
		//cerr<<"\n";
		if(fr)
			dq.push_front(v);
		else
			dq.push_back(v);
	}
	return;
}
void add_leftmost(int leftmost)
{
	if(leftmost==-1)
		return;
	if(pos[edge[leftmost].fi].y==pos[edge[leftmost].se].y) // downmost
	{
		dq.push_back({leftmost,0,1});
		return;
	}
	State bg={leftmost,0,1};
	if(pos[edge[leftmost].fi].y<pos[edge[leftmost].se].y)
		bg.side=0;
	else
		bg.side=1;
	dq.push_back(bg);
	return;
}
int dfs(int x)
{
	int leftmost=-1,downmost=-1;
	vis0[x]=true;
	for(auto v:e[x])
	{
		if(pos[x].x==pos[v.fi].x && (leftmost==-1 || pos[x].x<pos[edge[leftmost].fi].x))
			leftmost=v.se;
		if(pos[x].y==pos[v.fi].y && (downmost==-1 || pos[x].y<pos[edge[downmost].fi].y))
			downmost=v.se;
		if(!vis0[v.fi])
		{
			int tmp=dfs(v.fi);
			int a=edge[tmp].fi,b=edge[tmp].se;
			if(pos[a].x==pos[b].x && (leftmost==-1 || pos[a].x<pos[edge[leftmost].fi].x))
				leftmost=tmp;
			if(pos[a].y==pos[b].y && (downmost==-1 || pos[a].y<pos[edge[downmost].fi].y))
				downmost=v.se;
		}
	}
	if(leftmost==-1)
		return downmost;
	return leftmost;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>pos[i].x>>pos[i].y;
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		edge[i]={a,b};
		e[a].push_back({b,i});
		e[b].push_back({a,i});
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis0[i])
			add_leftmost(dfs(i));
	}
	while(!dq.empty())
	{
		auto x=dq.front();
		dq.pop_front();
		if(vis[x.x][x.side])
			continue;
		vis[x.x][x.side]=true;
		//cerr<<x.x<<" "<<x.side<<" "<<x.d<<"\n";
		if(dac[x.x]==0 || dac[x.x]==x.d)
		{
			dac[x.x]=x.d;
			ans[x.x]=!ans[x.x];
		}
		add_edge(edge[x.x].fi,x.x,x.side,x.d,true);
		add_edge(edge[x.x].se,x.x,!x.side,x.d,true);
		if(!vis[x.x][!x.side])
			dq.push_back({x.x,!x.side,x.d+1});
	}
	vector<int> out;
	for(int i=1;i<=m;i++)
	{
		if(!ans[i])
			out.push_back(i);
	}
	cout<<out.size()<<"\n";
	for(auto v:out)
		cout<<v<<"\n";
	return 0;
}

• 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: 9 / 9
• Subtask 13: 9 / 9
• Subtask 14: 9 / 9