oj.uz

Submission #519751

# Submission time Handle Problem Language Result Execution time Memory
519751 2022-01-27T09:13:56 Z sofapuden Flood (IOI07_flood) C++14
100 / 100
 215 ms 24416 KB 
#include<bits/stdc++.h>

using namespace std;

int n, m;

vector<array<int,3>> v, v2;
vector<vector<array<int,2>>> gr;
vector<int> us;
vector<int> vis;

const int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};

bool go(int dir, int a, int b){
	auto x = v[a];
	auto y = v[b];
	int am = 0;
	am+=((y[0]-x[0] == dx[dir]) || (y[0]-x[0])*dx[dir] > 0);
	am+=((y[1]-x[1] == dy[dir]) || (y[1]-x[1])*dy[dir] > 0);
	return am == 2;
}

int dfs(int x, int dir, set<int> &path){
	if(path.count(x))return x;
	path.insert(x);
	for(int i = 0; i < 3; ++i){
		for(auto &y : gr[x]){
			if(go((dir+i)%4,x,y[0])){
				if(vis[y[1]])continue;
				vis[y[1]] = 1;
				int z = dfs(y[0],(dir+i+3)%4,path);
				if(z != -1){
					us[y[1]] = 1;
					if(z == x)break;
					path.erase(x);
					return z;
				}
			}
		}
	}
	path.erase(x);
	return -1;
}

bool cmp(array<int,3> &a, array<int,3> &b){
	if(a[0] == b[0] && a[1] == b[1])return a[2] < b[2];
	if(a[1] == b[1])return a[0] < b[0];
	return a[1] < b[1];

}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	v.resize(n);
	gr.resize(n);
	for(int i = 0; i < n; ++i){
		cin >> v[i][0] >> v[i][1];
		v[i][2] = i;
	}
	v2 = v;
	sort(v2.begin(),v2.end(),cmp);
	cin >> m;
	us.resize(m);
	vis.resize(m);
	for(int i = 0; i < m; ++i){
		int a, b; cin >> a >> b;
		a--, b--;
		gr[a].push_back({b,i});
		gr[b].push_back({a,i});
	}
	for(int i = 0; i < n; ++i){
		set<int> S;
		dfs(v2[i][2],0,S);
	}
	vector<int> rem;
	for(int i = 0; i < m; ++i){
		if(!us[i])rem.push_back(i+1);
	}
	cout << rem.size() << '\n';
	for(auto x : rem)cout << x << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

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

Subtask #11
9.0 / 9.0

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

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 10300 KB Output is correct
2 Correct 170 ms 14744 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 13732 KB Output is correct
2 Correct 169 ms 15312 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 14604 KB Output is correct
2 Correct 214 ms 24416 KB Output is correct