oj.uz

Submission #258691

# Submission time Handle Problem Language Result Execution time Memory
258691 2020-08-06T11:31:50 Z super_j6 Flood (IOI07_flood) C++14
54 / 100
 81 ms 5496 KB 
#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.0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Incorrect 1 ms 1920 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Incorrect 1 ms 1920 KB Output isn't correct

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
9.0 / 9.0

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

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 5496 KB Output is correct

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 4344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 4984 KB Output isn't correct
2 Halted 0 ms 0 KB -