Submission #94967

#	Time	Username	Problem	Language	Result	Execution time	Memory
94967		Retro3014	Flood (IOI07_flood)	C++17	33 / 100	170 ms	16308 KiB

flood

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <stdio.h>

using namespace std;
#define MAX_N 100000

int N, W;
struct P{
	int x, y;
	int c[4] = {-1, -1, -1, -1};
	int g[4] = {-1, -1, -1, -1};
	int cnt = 0;
};
vector<P> point;
vector<int> gp[MAX_N+1];
struct S{
	int x, y;
	int type;
};
vector<S> line;
int group = 0;

void rotate1(int x, int y){
	while(1){
		if(point[x].g[(y+3)%4]!=-1)	return;
		point[x].g[(y+3)%4] = group;
		int t = (y+3)%4;
		while(1){
			if(point[x].c[t]!=-1){
				y = (t+2)%4;
				x = point[x].c[t];
				break;
			}
			t = (t+3)%4;
			if(point[x].g[t]!=-1){
				return;
			}
			point[x].g[t] = group;
		}
	}
}

void rotate2(int x, int y){
	while(1){
		if(point[x].g[y]!=-1)	return;
		point[x].g[y] = group;
		int t = (y+1)%4;
		while(1){
			if(point[x].c[t]!=-1){
				y = (t+2)%4;
				x = point[x].c[t];
				break;
			}
			if(point[x].g[t]!=-1){
				return;
			}
			point[x].g[t] = group;
			t = (t+1)%4;
		}
	}
}
deque<int> dq;
int lv[MAX_N+1];

void bfs(int x){
	lv[x] = 1;
	dq.push_back(x);
	while(!dq.empty()){
		int now = dq.front(); dq.pop_front();
		for(int i=0; i<gp[now].size(); i++){
			if(lv[gp[now][i]]==0){
				lv[gp[now][i]] = lv[now]+1;
				dq.push_back(gp[now][i]);
			}
		}
	}
	return;
}

vector<int> ans;

int main(){
	scanf("%d", &N);
	P sc;
	for(int i=0; i<N; i++){
		scanf("%d%d", &sc.x, &sc.y);
		point.push_back(sc);
	}
	scanf("%d", &W);
	int a, b;
	for(int i=0; i<W; i++){
		scanf("%d%d", &a, &b);
		a--; b--;
		if(point[a].x==point[b].x){
			if(point[a].y>point[b].y)	{int t = a; a = b; b = t;}
			point[a].c[0] = b; point[b].c[2] = a;
			point[a].cnt++; point[b].cnt++;
			line.push_back({a, b, 1});
		}else{
			if(point[a].x>point[b].x)	{int t = a; a = b; b = t;}
			point[a].c[1] = b; point[b].c[3] = a;
			point[a].cnt++; point[b].cnt++;
			line.push_back({a, b, 2});
		}
	}
	for(int i=0; i<N; i++){
		if(point[i].cnt==1 || point[i].cnt==0)	continue;
		for(int j=0; j<4; j++){
			if(point[i].g[j]==-1){
				if(point[i].c[j]!=-1){
					rotate1(point[i].c[j], (j+2)%4);
					group++;
				}else if(point[i].c[(j+1)%4]!=-1){
					rotate2(point[i].c[(j+1)%4], (j+3)%4);
					group++;
				}
			}
		}
	}
	/*for(int i=0; i<N; i++){
		for(int j=0; j<4; j++){
			printf("%d %d %d\n", i, j, point[i].g[j]);
		}
	}*/
	int px=point[0].x, py=point[0].y, pg=point[0].g[0];
	for(int i=1; i<N; i++){
		if(point[i].x>px || (point[i].x==px && point[i].y>py)){
			px = point[i].x; py = point[i].y; pg = point[i].g[0];
		}
	}
	for(int i=0; i<line.size(); i++){
		S now = line[i];
		if(point[now.x].cnt==1 || point[now.y].cnt==1)	continue;
		if(now.type==1){
			gp[point[now.x].g[0]].push_back(point[now.x].g[3]);
			gp[point[now.x].g[3]].push_back(point[now.x].g[0]);
		}else{
			gp[point[now.x].g[0]].push_back(point[now.x].g[1]);
			gp[point[now.x].g[1]].push_back(point[now.x].g[0]);
		}
	}
	bfs(pg);
	for(int i=0; i<line.size(); i++){
		S now = line[i];
		if(point[now.x].cnt==1 || point[now.y].cnt==1){
			ans.push_back(i+1);
		}else{
			if(now.type==1){
				if(lv[point[now.x].g[0]]==lv[point[now.x].g[3]]){
					ans.push_back(i+1);
				}
			}else{
				if(lv[point[now.x].g[0]]==lv[point[now.x].g[1]]){
					ans.push_back(i+1);
				}
			}
		}
	}
	printf("%d\n", ans.size());
	for(int i=0; i<ans.size(); i++){
		printf("%d\n", ans[i]);
	}
	return 0;
}

Compilation message (stderr)

flood.cpp: In function 'void bfs(int)':
flood.cpp:73:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<gp[now].size(); i++){
                ~^~~~~~~~~~~~~~~
flood.cpp: In function 'int main()':
flood.cpp:134:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<line.size(); i++){
               ~^~~~~~~~~~~~
flood.cpp:146:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<line.size(); i++){
               ~^~~~~~~~~~~~
flood.cpp:162:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", ans.size());
                 ~~~~~~~~~~^
flood.cpp:163:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ans.size(); i++){
               ~^~~~~~~~~~~
flood.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
flood.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &sc.x, &sc.y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
flood.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &W);
  ~~~~~^~~~~~~~~~
flood.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 3
• Subtask 5: 0 / 10
• Subtask 6: 3 / 3
• Subtask 7: 0 / 3
• Subtask 8: 0 / 3
• Subtask 9: 0 / 3
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9