제출 #1339010

#제출 시각아이디문제언어결과실행 시간메모리
1339010po_rag526Flood (IOI07_flood)C++17
10 / 100
19 ms25108 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define all(c) (c).begin(), (c).end()
#define F first
#define S second

const int mxN = 2*510+5;
pair<int,int> p[mxN];
int grid[mxN][mxN][6];

void solve(){
	int n; cin>>n;
	for (int i=0;i<n;i++) {
		cin>>p[i].F>>p[i].S;
		p[i].F+=5; p[i].S+=5;
		p[i].F *= 2; p[i].S *= 2;
	}

	for(int i=0;i<n;i++) for(int j=0;j<n;j++) grid[i][j][0]=0;
	int W; cin>>W;
	vector<pair<int,int>> ed;
	for (int i=0;i<W;i++) {
		int a, b; cin>>a>>b; a--,b--;
		ed.push_back({a, b});
		if (p[a] > p[b]) swap(a, b);
		grid[p[a].F][p[a].S][0] = 1;
		grid[p[b].F][p[b].S][0] = 1;
		if (p[a].S == p[b].S) for (int x=p[a].F;x<=p[b].F;x++) grid[x][p[a].S][0]=1;
		else for (int y=p[a].S;y<=p[b].S;y++) grid[p[a].F][y][0]=1;
		
	}

	for (int i=0;i<mxN;i++){
		for (int j=0;j<mxN;j++){
			grid[i][j][1] = grid[i][j][0];
			grid[i][j][2] = grid[i][j][0];
			grid[i][j][3] = grid[i][j][0];
			grid[i][j][4] = grid[i][j][0];
		}
	}
	for (int i=0;i<mxN;i++){
		for (int j=0;j<mxN;j++){
			if (i) grid[i][j][1] += grid[i-1][j][1];
			if (j) grid[i][j][2] += grid[i][j-1][2];
		}
	}

	for (int i=mxN-1;i>=0;i--){
		for (int j=mxN-1;j>=0;j--){
			if (i+1<mxN) grid[i][j][3] += grid[i+1][j][3];
			if (j+1<mxN) grid[i][j][4] += grid[i][j+1][4];
		}
	}

	for (int i=0;i<mxN;i++){
		for (int j=0;j<mxN;j++){
			grid[i][j][5] = min({grid[i][j][1], grid[i][j][2], grid[i][j][3], grid[i][j][4]});
		}
	}

	set<int> good;
	for (int i=0;i<W;i++){
		auto [a, b] = ed[i];
		auto pa = p[a], pb = p[b];
		auto m = make_pair((pa.F+pb.F)/2, (pa.S+pb.S)/2);
		if (pa.F == pb.F){
			int val1 = grid[m.F-1][m.S][5];
			int val2 = grid[m.F+1][m.S][5];
			if (abs(val1-val2) != 1){good.insert(i); }
		} else {
			int val1 = grid[m.F][m.S+1][5];
			int val2 = grid[m.F][m.S-1][5];
			if (abs(val1-val2) != 1){good.insert(i); }
		}
	}

	cout << good.size() << endl;
	for (int x: good) cout << x+1 << endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...