oj.uz

Submission #258710

# Submission time Handle Problem Language Result Execution time Memory
258710 2020-08-06T12:05:47 Z super_j6 Flood (IOI07_flood) C++14
0 / 100
 310 ms 5752 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] = 0;
					return 1;
				}else{
					vis[c] = 1;
				} 
			}
		}else if(!~-vis[y]){
			f[x] = 1;
			vis[c] = 0, 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
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
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 #5
0 / 10.0

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

Subtask #6
0 / 3.0

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

Subtask #7
0 / 3.0

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

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 2816 KB Output isn't correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 5752 KB Output isn't correct

Subtask #12
0 / 9.0

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

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 310 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 259 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -