oj.uz

Submission #411633

# Submission time Handle Problem Language Result Execution time Memory
411633 2021-05-25T16:26:50 Z Jasiekstrz Flood (IOI07_flood) C++17
33 / 100
 111 ms 10884 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];
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;
}
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;
	int leftmost=-1;
	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});
		if(pos[a].x==pos[b].x && (leftmost==-1 || pos[a].x<pos[edge[leftmost].fi].x))
			leftmost=i;
	}
	if(leftmost==-1)
	{
		for(int i=1;i<=m;i++)
			cout<<i<<"\n";
		return 0;
	}
	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);
	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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
3.0 / 3.0

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

Subtask #7
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 4004 KB Output isn't correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 7452 KB Output isn't correct

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 7888 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 10144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 106 ms 10884 KB Output isn't correct
2 Halted 0 ms 0 KB -