oj.uz

답안 #120310

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
120310 2019-06-24T07:16:58 Z baluteshih Flood (IOI07_flood) C++14
73 / 100
 176 ms 19060 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,dwn=-1,rit=-1;
	bool operator<(const mode &a)const{
		if(x==a.x) return y<a.y;
		return x<a.x;
	}
}dots[100005];

int boss[400005];
vector<int> G[400005],ans;
queue<int> q;
int dis[400005];
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;
		else
			dots[a].rit=i;
	}
	for(int i=0;i<=2*w+1;++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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11392 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11392 KB Output is correct
2 Correct 12 ms 11392 KB Output is correct
3 Correct 12 ms 11264 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 11264 KB Output is correct

Subtask #4
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11392 KB Output is correct
2 Correct 12 ms 11392 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11392 KB Output is correct
2 Correct 10 ms 11264 KB Output is correct

Subtask #6
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11392 KB Output is correct

Subtask #7
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11264 KB Output is correct

Subtask #8
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 11392 KB Output is correct
2 Correct 12 ms 11388 KB Output is correct

Subtask #9
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 11264 KB Output is correct
2 Correct 11 ms 11392 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 12408 KB Output is correct

Subtask #11
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 15612 KB Output is correct

Subtask #12
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 17056 KB Output is correct
2 Incorrect 176 ms 19060 KB Output isn't correct

Subtask #13
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 148 ms 17928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 165 ms 18948 KB Output isn't correct
2 Halted 0 ms 0 KB -