oj.uz

Submission #456356

# Submission time Handle Problem Language Result Execution time Memory
456356 2021-08-06T13:59:43 Z dutch Flood (IOI07_flood) C++17
100 / 100
 241 ms 26052 KB 
#include <bits/stdc++.h>
using namespace std;

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

int n, m, c[2][N], e[2][M], d[M*2], h[4][N], p;
bool vert[M], vis[M*2];
vector<int> g[M*2];

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i=1; i<=n; ++i)
		cin >> c[0][i] >> c[1][i];
	cin >> m;
	for(int i=1; i<=m; ++i){
		int &u = e[0][i], &v = e[1][i];
		cin >> u >> v;
		vert[i] = (c[0][u] == c[0][v]);
		if(c[vert[i]][u] > c[vert[i]][v]) swap(u, v);
		h[2+!vert[i]][u] = h[!vert[i]][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; u = u > m ? u - m : u;
			int s = e[vert[u] ^ (w > m)][u];
			array<int, 4> add = {vert[u] == (w > m), w > m};

			for(int j=0; j<4; ++j){
				int k = (j + vert[u] + (w > m) * 2) % 4;
				if(h[k][s] && !v) v = h[k][s] + m * (add[j & 1] ^ (j > 1));
			}
			if(v){
				g[w].push_back(v);
				g[v].push_back(w);
			}
			u = v;
		}
	}
	deque<int> q;
	array<int, 2> todo[m];
	for(int i=1; i<=m; ++i)
		todo[i-1] = {c[!vert[i]][e[0][i]], i};
	sort(todo, todo+m);
	fill(d, d+m+m+1, INF);
	while(p < m){
		q.push_back(todo[p][1]);
		d[todo[p][1]] = 0;
		while(!q.empty()){
			int u = q.front(); q.pop_front();
			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]) vis[min(u, v)] = 0;
		}
		while(p < m && d[todo[p][1]] < INF) ++p;
	}
	cout << m-accumulate(vis+1, vis+1+m, 0) << '\n';
	for(int i=1; i<=m; ++i) if(!vis[i]) cout << i << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 9716 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 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 6 ms 9676 KB Output is correct

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9804 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 6 ms 9804 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 6 ms 9724 KB Output is correct

Subtask #10
9.0 / 9.0

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

Subtask #11
9.0 / 9.0

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

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 20112 KB Output is correct
2 Correct 241 ms 25608 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 23488 KB Output is correct
2 Correct 231 ms 26052 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 25412 KB Output is correct
2 Correct 159 ms 21360 KB Output is correct