oj.uz

Submission #94969

# Submission time Handle Problem Language Result Execution time Memory
94969 2019-01-26T06:37:25 Z Retro3014 Flood (IOI07_flood) C++17
100 / 100
 123 ms 13408 KB 
#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

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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2156 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6564 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 6576 KB Output is correct
2 Correct 123 ms 12484 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 7768 KB Output is correct
2 Correct 123 ms 13408 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 9564 KB Output is correct
2 Correct 77 ms 10128 KB Output is correct