#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 + 10;
int x[maxn], y[maxn], a[2 * maxn], b[2 * maxn];
int dis[4 * maxn];
vector <pii> vec[maxn];
vector <pii> adj[4 * maxn];
int inf = 1e9 + 5;
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});
}
//alone:(
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();
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 ++){
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 + 3; i ++)
dis[i] = inf;
vector <pii> v;
for(int i = 1; i <= m; i ++){
if(x[a[i]] == x[b[i]])
v.pb({min(y[a[i]], y[b[i]]), i});
}
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 << endl;
for(int i = 1; i <= m; i ++){
if(dis[2 * i] == dis[2 * i + 1])
cout << i << endl;
}
return 0;
}
Compilation message
flood.cpp: In function 'int main()':
flood.cpp:147:24: warning: logical not is only applied to the left hand side of comparison [-Wlogical-not-parentheses]
147 | if(!dis[2 * u.S + 1] == inf){
| ^~
flood.cpp:147:6: note: add parentheses around left hand side expression to silence this warning
147 | if(!dis[2 * u.S + 1] == inf){
| ^~~~~~~~~~~~~~~~~
| ( )
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
12140 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
22 ms |
24300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
23 ms |
24300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
22 ms |
24300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
22 ms |
24300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
27 ms |
24300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
22 ms |
24428 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
23 ms |
24364 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
25 ms |
24300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
34 ms |
26476 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
66 ms |
32232 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
137 ms |
61420 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
120 ms |
36716 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
122 ms |
37740 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
