oj.uz

Submission #349996

# Submission time Handle Problem Language Result Execution time Memory
349996 2021-01-18T19:55:41 Z negar_a Flood (IOI07_flood) C++14
91 / 100
 264 ms 33256 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second

const int maxn = 1e5 + 2;
int x[maxn], y[maxn];
int dis[maxn * 4], ty[maxn * 2][5];
vector <pii> adj[maxn * 4];
int inf = 1e8;
 
int dir(int u, int v){
//	left = 0, down = 1, right = 2, up = 3;
	if(x[u] == x[v]){
		if(y[u] < y[v]){
			return 3;
		}
		return 1;
	}
	if(x[u] < x[v])
		return 2;
	return 0;
}

void add_edge(int x, int y){
	adj[x].pb({y, 0});
	adj[y].pb({x, 0});
	return;
}

void bfs(int v){
	deque <int> q;
	dis[v] = 0;
	q.pb(v);
	while(q.size()){
		int x = q.front();
		q.pop_front();
		for(auto u : adj[x]){
			if(dis[u.F] > dis[x] + u.S){
				dis[u.F] = dis[x] + u.S;
				if(u.S){
					q.pb(u.F);
				}else
					q.push_front(u.F);
			}	
		}
	}
}

int main(){
	fast_io;
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++){
		cin >> x[i] >> y[i];
	}
	int m;
	cin >> m;
	//find lines for each point
	for(int i = 1; i <= n; i ++)
		ty[i][0] = ty[i][1] = ty[i][2] = ty[i][3] = -1;	
		
	vector <pii> v;
	for(int i = 1; i <= m; i ++){
		int a, b;
		cin >> a>> b;
		if(y[a] == y[b])
			v.pb({y[a], i});
		ty[a][dir(a, b)] = i;
		ty[b][dir(b, a)] = i;
	}
	//put edges of the graph!
	for(int i = 1; i <= n; i ++){
		for(int j = 0; j < 4; j ++){
			if(ty[i][j] != -1){
				int k = (j + 1) % 4;
				while(ty[i][k] == -1){
					k = (k + 1) % 4;
				}
				int x = 2 * ty[i][j] + ((j == 0) | (j == 3));
				int y = 2 * ty[i][k] + ((k == 1) | (k == 2));
				
				if(j != k){
					adj[ty[i][j] * 2].pb({ty[i][j] * 2 + 1, 1});
					adj[ty[i][j] * 2 + 1].pb({ty[i][j] * 2, 1});
				}
				
				add_edge(x, y);
			}
		}
	}
	
	for(int i = 0; i <= 2 * m + 3; i ++)
		dis[i] = inf;
		
	sort(v.begin(), v.end());
	for(auto u : v){
		if(dis[2 * u.S + 1] >= inf){
			bfs(2 * u.S + 1);
		}
	}
	int cnt = 0;
	for(int i = 1; i <= m; i ++){
		if(dis[2 * i] == dis[2 * i + 1])
			cnt ++;
	}	
	cout << cnt << '\n';
	for(int i = 1; i <= m; i ++){
		if(dis[2 * i] == dis[2 * i + 1])
			cout << i << '\n';
	}
	
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

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

Subtask #11
9.0 / 9.0

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

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 21740 KB Output is correct
2 Correct 255 ms 29640 KB Output is correct

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 26932 KB Output is correct
2 Runtime error 258 ms 33256 KB Memory limit exceeded

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 29376 KB Output is correct
2 Correct 206 ms 27880 KB Output is correct