제출 #258691

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
258691		super_j6	Flood (IOI07_flood)	C++14	54 / 100	81 ms	5496 KiB

flood

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int mxn = 100000, k = 4;
int n, m;
int a[mxn][2];
int u[mxn], v[mxn], it[mxn], vis[mxn], f[mxn];
int g[mxn][k];

bool dfs(int c, int p){
	vis[c] = 1;
	for(int i = (p + 1) % k; i != p; i = (i + 1) % k){
		int x = g[c][i];
		if(!~x) continue;
		int y = c ^ u[x] ^ v[x];
		if(!vis[y]){
			if(dfs(y, (i + 2) % k)){
				f[x] = 1;
				if(~vis[c]){
					vis[c] = 2;
					return 1;
				}else{
					vis[c] = 1;
				} 
			}
		}else if(!~-vis[y]){
			f[x] = 1;
			vis[c] = 2, vis[y] = -1;
			return 1;
		}
	}
	vis[c] = 2;
	return 0;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < 2; j++) cin >> a[i][j];
		it[i] = i;
	} 
	
	cin >> m;
	
	memset(g, -1, sizeof(g));
	for(int i = 0; i < m; i++){
		cin >> u[i] >> v[i];
		u[i]--, v[i]--;
		for(int j = 0; j < 2; j++){
			if(a[u[i]][!j] == a[v[i]][!j]){
				int x = (a[u[i]][j] < a[v[i]][j]) << 1 | j;
				g[u[i]][x] = i, g[v[i]][(x + 2) % k] = i;
			}
		}
	}
	
	sort(it, it + n, [&](int x, int y){
		return a[x][0] < a[y][0];
	});
	
	for(int i = 0; i < n; i++) if(!vis[it[i]]) dfs(it[i], 0);
	
	int ret = 0;
	for(int i = 0; i < m; i++) ret += !f[i];
	
	cout << ret << endl;
	for(int i = 0; i < m; i++) if(!f[i]) cout << i + 1 << endl;

	return 0;
}

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