#include <bits/stdc++.h>
using namespace std;
int uf[400000];
int siz[400000];
bool vis[400000],pres[400000];
int tim[400000];
bool sos[400000];
void in(int &n) {
n = 0;
int c = getc_unlocked(stdin), m = 0;
for (; c < '0' || c > '9'; c = getc_unlocked(stdin))
if (c == '-') m = 1;
for (; c >= '0' && c <= '9'; c = getc_unlocked(stdin))
n = (n << 1) + (n << 3) + c - '0';
if (m) n = -n;
}
void out(int n) {
if (!n) putc_unlocked('0', stdout);
int c[11], i = 0;
if (n < 0) { putc_unlocked('-', stdout); n = -n; }
for (; n; n /= 10, i++) c[i] = n % 10 + '0';
for (i--; i >= 0; putc_unlocked(c[i], stdout), i--);
putc_unlocked('\n', stdout);
}
vector<pair<int,int>> adjj[400000];
int find(int a){
if(uf[a]!=a)uf[a]=find(uf[a]);
return uf[a];
}
void uni(int a,int b){
a = find(a); b = find(b);
if(siz[a]>siz[b])swap(a,b);
uf[a]=b;
siz[b]+=siz[a];
}
int main(){
int N,K,a,b;
for(int i = 0; i < 400000; i++){siz[i]=1;uf[i]=i;}
in(N);
int cx[N];
int cy[N];
int curr = N-1;
vector<pair<int,int>> adj[N];
for(int i = 0; i < N; i++){in(cx[i]);in(cy[i]);}
in(K);
vector<pair<int,int>> pts;
for(int i = 0; i < N; i++)pts.push_back({cy[i],i});
sort(pts.begin(),pts.end());
int walls[K][2],arcs[K][2];
for(int i = 0; i < K; i++){
in(a); in(b);
adj[a-1].push_back({b-1,i});
adj[b-1].push_back({a-1,i});
arcs[i][1]=a-1; arcs[i][0]=b-1;
}
int sas[4];
int x,y;
for(int i = 0; i < N; i++){
sas[0]=-1;sas[1]=-1;sas[2]=-1;sas[3]=-1;
for(auto k: adj[i]){
x=k.first; y=k.second;
if(cx[x]==cx[i]){
if(cy[x]>cy[i]){sas[0]=x;walls[y][0]=i;walls[y][1]=i+100000;}
else sas[2]=x;
}else{
if(cx[x]>cx[i]){sas[1]=x;walls[y][0]=i+100000;walls[y][1]=i+200000;}
else sas[3]=x;
}
}
if(sas[0]==-1){uni(i,i+100000);}
else{uni(i,sas[0]+300000); uni (i+100000,sas[0]+200000);}
if(sas[1]==-1){uni(i+100000,i+200000);}
else{uni(i+100000,sas[1]);uni(i+200000, sas[1]+300000);}
if(sas[2]==-1){uni(i+200000,i+300000);}
else{uni(i+300000,sas[2]);uni(i+200000,sas[2]+100000);}
if(sas[3]==-1){uni(i,i+300000);}
else{uni(i,100000+sas[3]);uni(i+300000,sas[3]+200000);}
}
//for(int i = 0; i < 4; ,res=K;i++){cout << find(i*100000+1) << " " << find(i*100000) << "\n";}
for(int i = 0;i < K;i++){
a=find(walls[i][0]); b=find(walls[i][1]);
adjj[a].push_back({b,i});
adjj[b].push_back({a,i});
}
for(int i = 0; i < 400000; i++){vis[i]=0; pres[i]=0;tim[i]=-1;sos[i]=0;}
queue <pair<int,int>> q;
int t,node;
bool sus = true;
do{
if(q.empty()){
while(sos[pts[curr].second] && curr >= 0)curr--;
if(curr < 0){sus=false;break;}
tim[find(pts[curr].second)]=t;
q.push({find(pts[curr--].second),t});
}
node = q.front().first;
t = q.front().second;
q.pop();
//cout << node<< "\n";
vis[node]=1;
//cout<< "node " << node << "\n";
for(auto x: adjj[node]){
sos[arcs[x.second][0]]=1;
sos[arcs[x.second][1]]=1;
if(tim[x.first]==-1){
q.push({x.first,t+1});
tim[x.first]=t+1;
//cout<<x.second<<endl;
}
}
}while(sus);
vector <int> res;
for(int i = 0; i < K; i++){
if(tim[find(walls[i][0])]==tim[find(walls[i][1])])res.push_back(i+1);
}
out(res.size());
for(auto x: res)out(x);
return 0;
}
Compilation message
flood.cpp: In function 'int main()':
flood.cpp:95:40: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
95 | tim[find(pts[curr].second)]=t;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
15616 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
15616 KB |
Output is correct |
| 2 |
Correct |
10 ms |
15616 KB |
Output is correct |
| 3 |
Correct |
10 ms |
15616 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
15616 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
15616 KB |
Output is correct |
| 2 |
Correct |
12 ms |
15616 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
15616 KB |
Output is correct |
| 2 |
Correct |
11 ms |
15616 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
15616 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
15524 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
15616 KB |
Output is correct |
| 2 |
Correct |
11 ms |
15616 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
15616 KB |
Output is correct |
| 2 |
Correct |
11 ms |
15616 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
24 ms |
18300 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
50 ms |
24824 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
52 ms |
25452 KB |
Output is correct |
| 2 |
Correct |
213 ms |
30956 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
166 ms |
29544 KB |
Output is correct |
| 2 |
Correct |
225 ms |
32488 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
195 ms |
30828 KB |
Output is correct |
| 2 |
Correct |
91 ms |
29668 KB |
Output is correct |
