oj.uz

Submission #204387

# Submission time Handle Problem Language Result Execution time Memory
204387 2020-02-25T15:04:49 Z mahmoudbadawy Flood (IOI07_flood) C++17
100 / 100
 313 ms 16528 KB 
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int N=1e5+5;

int n,m;
pair<int,int> arr[N];
int sorted[N],vis[N];
pair<int,int> adj[N][4];
vector<int> ans;

bool cmp(int x,int y)
{
	return arr[x]<arr[y];
}

int go(int x,int d)
{
	if(vis[x]) return x;
	vis[x]=1;
	for(int i=0;i<4;i++)
	{
		int tod=(d-i+1+4)%4;
		int to=adj[x][tod].F;
		if(to==-1) continue;
		int ed=adj[x][tod].S;
		adj[x][tod]={-1,-1};
		adj[to][(tod+2)%4]={-1,-1};
		int y=go(to,tod);
		if(y==-1)
		{
			ans.push_back(ed);
			continue;
		}
		if(y!=x)
		{
			vis[x]=0;
			return y;
		}
	}
	vis[x]=0;
	return -1;
}

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		sorted[i]=i;
		scanf("%d %d",&arr[i].F,&arr[i].S);
		for(int j=0;j<4;j++)
			adj[i][j]={-1,-1};
	}
	sort(sorted,sorted+n,cmp);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y); x--; y--;
		if(arr[x].F==arr[y].F)
		{
			if(arr[x].S>arr[y].S) swap(x,y);
			adj[x][0]={y,i};
			adj[y][2]={x,i};
		}
		else
		{
			if(arr[x].F>arr[y].F) swap(x,y);
			adj[x][1]={y,i};
			adj[y][3]={x,i};
		}
	}
	for(int i=0;i<n;i++)
	{
		go(sorted[i],0);
	}
	cout << ans.size() << endl;
	for(int i:ans)
		cout << i << endl;
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
flood.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&arr[i].F,&arr[i].S);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
  ~~~~~^~~~~~~~~
flood.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y); x--; y--;
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 6 ms 376 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 6 ms 376 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2168 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 8440 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 6776 KB Output is correct
2 Correct 214 ms 8820 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 8560 KB Output is correct
2 Correct 227 ms 8820 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 8692 KB Output is correct
2 Correct 313 ms 16528 KB Output is correct