oj.uz

답안 #349884

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
349884 2021-01-18T15:41:20 Z negar_a Flood (IOI07_flood) C++14
10 / 100
 144 ms 33504 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 = 2e5 + 10;
int x[maxn], y[maxn], a[maxn], b[maxn];
ll dis[maxn];
vector <pii> vec[maxn];
vector <pii> adj[maxn];
bool mark[maxn];
ll inf = 1e10;
 
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 d1, int d2, int a, int b){
//	cout << a << " " << b << " | " << d1 << " " << d2 << endl;
	
	// if two lines are : |_ 
	if(d1 == 0 && d2 == 1){
		adj[2 * a + 1].pb({2 * b + 1, 0});
		adj[2 * b + 1].pb({2 * a + 1, 0});
	}
	else if(d1 == 1 && d2 == 2){
		adj[2 * a].pb({2 * b + 1, 0});
		adj[2 * b + 1].pb({2 * a, 0});
	}
	else if(d1 == 2 && d2 == 3){
		adj[2 * a].pb({2 * b, 0});
		adj[2 * b].pb({2 * a, 0});
	}
	else if(d1 == 3 && d2 == 0){
		adj[2 * a + 1].pb({2 * b, 0});
		adj[2 * b].pb({2 * a + 1, 0});
	}
	// if they are _ _
	else if((d1 == 3 && d2 == 1) || (d1 == 0 && d2 == 2)){
		adj[2 * a + 1].pb({2 * b + 1, 0});
		adj[2 * b + 1].pb({2 * a + 1, 0});
	}
	else if((d1 == 1 && d2 == 3) || (d1 == 2 && d2 == 0)){
		adj[2 * a].pb({2 * b, 0});
		adj[2 * b].pb({2 * a, 0});
	}
	//
	else if(d1 == 0 && d2 == 3){
		adj[2 * a + 1].pb({2 * b, 0});
		adj[2 * b].pb({2 * a + 1, 0});
	}
	else if(d1 == 1 && d2 == 0){
		adj[2 * a].pb({2 * b, 0});
		adj[2 * b].pb({2 * a, 0});
	}
	else if(d1 == 2 && d2 == 1){
		adj[2 * a].pb({2 * b + 1, 0});
		adj[2 * b + 1].pb({2 * a, 0});
	}
	else if(d1 == 3 && d2 == 2){
		adj[2 * a + 1].pb({2 * b + 1, 0});
		adj[2 * b + 1].pb({2 * a + 1, 0});
	}
	
	else{
		adj[2 * a].pb({2 * a + 1, 0});
	}
	
	adj[2 * a].pb({2 * a + 1, 1});
	adj[2 * a + 1].pb({2 * a, 1});
	adj[2 * b].pb({2 * b + 1, 1});
	adj[2 * b + 1].pb({2 * b, 1});
	return;
}

void bfs(int v){
	deque <int> q;
	dis[v] = 0;
	q.pb(v);
	while(q.size()){
		int x = q.front();
		mark[x] = true;
//		cout << "x : " << x << endl;
		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 <= m; i ++){
		cin >> a[i] >> b[i];
		vec[a[i]].pb({dir(a[i], b[i]), i});
		vec[b[i]].pb({dir(b[i], a[i]), i});
	}
	//put edges of the graph!
	for(int i = 1; i <= n; i ++){
//		cout << i << " : ";
		
		sort(vec[i].begin(), vec[i].end());
		for(int j = 0; j < (int)vec[i].size() - 1; j ++){
			add_edge(vec[i][j].F, vec[i][j + 1].F, vec[i][j].S, vec[i][j + 1].S);
		}
		if((int)vec[i].size() > 1)
			add_edge(vec[i].back().F, vec[i][0].F, vec[i].back().S, vec[i][0].S);
		else if((int)vec[i].size() == 1){
			add_edge(-1, -1, vec[i][0].S, -1);
		}
	}
	
	for(int i = 0; i <= 2 * m + 1; i ++)
		dis[i] = inf;
		
	vector <pii> v;
	for(int i = 1; i <= m; i ++){
		v.pb({min(y[a[i]], y[b[i]]), i});
	}
	sort(v.begin(), v.end());
	for(auto u : v){
		if(!mark[2 * u.S]){
			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 << endl;
	for(int i = 1; i <= m; i ++){
		if(dis[2 * i] == dis[2 * i + 1])
			cout << i << endl;
	}
	
	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9708 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9708 KB Output isn't correct

Subtask #4
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 9836 KB Output isn't correct

Subtask #7
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9836 KB Output isn't correct

Subtask #8
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 9836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 54 ms 14956 KB Output isn't correct

Subtask #11
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 144 ms 28780 KB Output isn't correct

Subtask #12
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 113 ms 30700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 121 ms 31824 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 120 ms 33504 KB Execution killed with signal 6 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -