Submission #94969

#	Time	Username	Problem	Language	Result	Execution time	Memory
94969		Retro3014	Flood (IOI07_flood)	C++17	100 / 100	123 ms	13408 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][2];
};
vector<P> point;
struct S{
	int x, y;
	int type;
};
vector<S> line;
vector<int> idx;
bool ans1[MAX_N*2+1], ans2[MAX_N*2+1];

void rotate(int x, int y){
	//printf("0\n");
	while(1){
		//printf("%d %d\n", point[x].x, point[x].y);
		for(int i=1; i<=4; i++){
			if(point[x].c[(y+i)%4][0]!=-1){
				if(point[x].c[(y+i)%4][1]==-1){
					while(!idx.empty()){
						S now = line[idx.back()]; idx.pop_back();
						if(now.type==1){
							point[now.x].c[0][0] = -1;
							point[now.y].c[2][0] = -1;
						}else{
							point[now.x].c[1][0] = -1;
							point[now.y].c[3][0] = -1;
						}
					}
					return;
				}
				int xx = x, yy = y;
				y = (y+i+2)%4;
				x = point[x].c[(yy+i)%4][0];
				if(ans1[point[xx].c[(yy+i)%4][1]]){
					ans1[point[xx].c[(yy+i)%4][1]]=false;
					idx.push_back(point[xx].c[(yy+i)%4][1]);
				}else{
					ans2[point[xx].c[(yy+i)%4][1]]=true;
				}
				point[xx].c[(yy+i)%4][1] = -1;
				break;
			}
		}
	}
}

struct S2{
	int idx, data;
	bool operator <(const S2 &a)const{
		return data<a.data;
	}
};
vector<S2> v2;

int main(){
	scanf("%d", &N);
	P sc;
	for(int i=0; i<4; i++){
		for(int j=0; j<2; j++){
			sc.c[i][j] = -1;
		}
	}
	for(int i=0; i<N; i++){
		scanf("%d%d", &sc.x, &sc.y);
		point.push_back(sc);
	}
	scanf("%d", &W);
	for(int i=0; i<W; i++){
		ans1[i] = true;
	}
	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][0] = b; point[a].c[0][1] = line.size();
			point[b].c[2][0] = a; point[b].c[2][1] = line.size();
			v2.push_back({line.size(), point[a].x});
			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][0] = b; point[a].c[1][1] = line.size();
			point[b].c[3][0] = a; point[b].c[3][1] = line.size();
			line.push_back({a, b, 2});
		}
	}
	sort(v2.begin(), v2.end());
	for(int i=0; i<v2.size(); i++){
		if(!ans1[v2[i].idx])	continue;
		S now = line[v2[i].idx];
		rotate(now.y, 2);
	}
	for(int i=0; i<W; i++){
		if(ans1[i]){
			ans2[i] = true;
		}
	}
	int ans = 0;
	for(int i=0; i<W; i++){
		ans+=(ans2[i]);
	}
	printf("%d\n", ans);
	for(int i=0; i<W; i++){
		if(ans2[i]){
			printf("%d\n", i+1);
		}
	}
	return 0;
}

Compilation message (stderr)

flood.cpp: In function 'int main()':
flood.cpp:91:27: warning: narrowing conversion of 'line.std::vector<S>::size()' from 'std::vector<S>::size_type {aka long unsigned int}' to 'int' inside { } [-Wnarrowing]
    v2.push_back({line.size(), point[a].x});
                  ~~~~~~~~~^~
flood.cpp:101:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v2.size(); i++){
               ~^~~~~~~~~~
flood.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
flood.cpp:76: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:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &W);
  ~~~~~^~~~~~~~~~
flood.cpp:85: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: 3 / 3
• Subtask 5: 10 / 10
• Subtask 6: 3 / 3
• Subtask 7: 3 / 3
• Subtask 8: 3 / 3
• Subtask 9: 3 / 3
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9
• Subtask 13: 9 / 9
• Subtask 14: 9 / 9