oj.uz

Submission #411650

# Submission time Handle Problem Language Result Execution time Memory
411650 2021-05-25T16:42:59 Z Jasiekstrz Flood (IOI07_flood) C++17
100 / 100
 285 ms 17664 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 ms 2696 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 4 ms 2764 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4164 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 9960 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 8704 KB Output is correct
2 Correct 285 ms 15256 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 11588 KB Output is correct
2 Correct 280 ms 15920 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 12740 KB Output is correct
2 Correct 205 ms 17664 KB Output is correct