oj.uz

Submission #395612

# Submission time Handle Problem Language Result Execution time Memory
395612 2021-04-28T16:46:55 Z Berted Flood (IOI07_flood) C++14
100 / 100
 105 ms 17660 KB 
#include <iostream>
#include <vector>
#include <algorithm>
 
#define pii pair<int, int>
#define ppi pair<pii, int>
#define fst first
#define snd second
 
using namespace std;
 
const int INF = 1e9;
 
int N, M; ppi A[100001]; pii C[100001];
pii adj[100001][4];
 
vector<int> vis;
int H[100001];
 
bool rem[200001], ans[200001];
 
int DFS(int u, int pv)
{
	int ret = H[u] + 1; 
	vis.push_back(u);
 
	//cerr << "D: " << u << " " << C[u].fst << " " << C[u].snd << " " << pv << "\n";
	for (int k = -1; k < 2; k++)
	{
		int nx = adj[u][(pv + 4 + k) % 4].fst, id = adj[u][(pv + 4 + k) % 4].snd;
		if (nx == -1 || rem[id]) continue;
		if (H[nx] < H[u]) {ret = min(ret, H[nx]);}
		else {H[nx] = H[u] + 1; ret = min(ret, DFS(nx, (pv + 4 + k) % 4));}
		
		rem[id] = 1;
		if (ret < H[u]) {break;}
		else if (ret == H[u]) {ret = H[u] + 1; k++;}
		else {ans[id] = 1;}
	}
	//cerr << "RET: " << C[u].fst << " " << C[u].snd << " " << ret << " " << H[u] << "\n";
	return ret;
}
 
int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) 
	{
		cin >> A[i].fst.fst >> A[i].fst.snd; A[i].snd = i; H[i] = INF; 
		C[i] = A[i].fst;
		for (int j = 0; j < 4; j++) adj[i][j] = {-1, -1};
	}
 
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int u, v; cin >> u >> v; u--; v--;
		if (A[u].fst.fst == A[v].fst.fst)
		{
			if (A[u].fst.snd < A[v].fst.snd) {adj[u][0] = {v, i}; adj[v][2] = {u, i};}
			else {adj[u][2] = {v, i}; adj[v][0] = {u, i};}
		}
		else 
		{
			if (A[u].fst.fst < A[v].fst.fst) {adj[u][1] = {v, i}; adj[v][3] = {u, i};}
			else {adj[u][3] = {v, i}; adj[v][1] = {u, i};}
		}
	}
 
	sort(A, A + N);
	for (int i = 0; i < N; i++)
	{
		//cerr << "START: " << A[i].fst.fst << " " << A[i].fst.snd << " " << A[i].snd << "\n";
		H[A[i].snd] = 0; DFS(A[i].snd, 0);
		for (const int &x : vis) H[x] = INF;
		vis.clear();
	}
 
	vector<int> ret;
	for (int i = 0; i < M; i++)
		if (ans[i]) ret.push_back(i + 1); 
 
	cout << ret.size() << "\n";
	for (const int &x : ret) cout << x << "\n";
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

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

Subtask #11
9.0 / 9.0

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

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6056 KB Output is correct
2 Correct 105 ms 7972 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 7916 KB Output is correct
2 Correct 83 ms 9872 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 7916 KB Output is correct
2 Correct 81 ms 17660 KB Output is correct