oj.uz

Submission #456332

# Submission time Handle Problem Language Result Execution time Memory
456332 2021-08-06T13:08:16 Z dutch Flood (IOI07_flood) C++17
73 / 100
 250 ms 64920 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+1, M = N+N;

int n, m, x[N], y[N], a[M], b[M], up[N], dn[N], lf[N], rt[N], d[M*2];
bool vertical[M], vis[M*2];
vector<int> g[M*2], ans;

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i=1; i<=n; ++i)
		cin >> x[i] >> y[i];
	cin >> m;
	for(int i=1; i<=m; ++i){
		int &u = a[i], &v = b[i];
		cin >> u >> v;
		if((vertical[i] = (x[u] == x[v]))){
			if(y[u] > y[v]) swap(u, v);
			up[u] = dn[v] = i;
		}else{
			if(x[u] > x[v]) swap(u, v);
			rt[u] = lf[v] = i;
		}
	}
	vis[0] = 1;
	for(int i=1; i<=m+m; ++i){
		int u = i, v;
		while(!vis[u]){
			vis[u] = !(v = 0);
			int w = u;
			if(vertical[((u-1) % m) + 1]){
				if(u > m){ // right
					u -= m;
					if(rt[a[u]] && !v) v = rt[a[u]] + m;
					if(dn[a[u]] && !v) v = dn[a[u]] + m;
					if(lf[a[u]] && !v) v = lf[a[u]];
					if(up[a[u]] && !v) v = up[a[u]];
				}else{
					if(lf[b[u]] && !v) v = lf[b[u]];
					if(up[b[u]] && !v) v = up[b[u]];
					if(rt[b[u]] && !v) v = rt[b[u]] + m;
					if(dn[b[u]] && !v) v = dn[b[u]] + m;
				}
			}else{
				if(u > m){ // up
					u -= m;
					if(up[b[u]] && !v) v = up[b[u]];
					if(rt[b[u]] && !v) v = rt[b[u]] + m;
					if(dn[b[u]] && !v) v = dn[b[u]] + m;
					if(lf[b[u]] && !v) v = lf[b[u]];
				}else{
					if(dn[a[u]] && !v) v = dn[a[u]] + m;
					if(lf[a[u]] && !v) v = lf[a[u]];
					if(up[a[u]] && !v) v = up[a[u]];
					if(rt[a[u]] && !v) v = rt[a[u]] + m;
				}
			}
			if(v){
				g[w].push_back(v);
				g[v].push_back(w);
			}
			u = v;
		}
	}
	deque<int> q;
	set<array<int, 2>> todo;
	for(int i=1; i<=m; ++i)
		todo.insert({vertical[i] ? x[a[i]] : y[a[i]], i});
	fill(d, d+m+m+1, 2e9);
	while(!todo.empty()){
		q.push_back((*todo.begin())[1]);
		d[(*todo.begin())[1]] = 0;
		while(!q.empty()){
			int u = q.front(); q.pop_front();
			array<int, 2> f = {vertical[u] ? x[a[u]] : y[a[u]], u};
			if(todo.find(f) != todo.end()) todo.erase(f);
			for(int v : g[u]) if(d[v] > d[u]){
				d[v] = d[u];
				q.push_front(v);
			}
			int v = u > m ? u-m : u+m;
			if(d[v] > d[u] + 1){
				d[v] = d[u] + 1;
				q.push_back(v); 
			}
			if(d[u] == d[v]) ans.push_back(min(u, v));
		}
	}
	sort(begin(ans), end(ans));
	ans.resize(unique(begin(ans), end(ans)) - begin(ans));
	cout << size(ans) << '\n';
	for(int i : ans) cout << i << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9720 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9804 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9804 KB Output is correct
2 Correct 7 ms 9808 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9804 KB Output is correct
2 Correct 8 ms 9804 KB Output is correct

Subtask #10
9.0 / 9.0

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

Subtask #11
9.0 / 9.0

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

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 23484 KB Output is correct
2 Runtime error 250 ms 64920 KB Execution killed with signal 11

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 224 ms 56288 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 228 ms 61728 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -