oj.uz

Submission #906034

# Submission time Handle Problem Language Result Execution time Memory
906034 2024-01-13T10:54:10 Z JakobZorz Flood (IOI07_flood) C++17
20 / 100
 120 ms 8288 KB 
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
//const int MOD=1e9+7;
//typedef pair<ll,ll>Point;
//typedef pair<ll,ll>Line;
//#define x first
//#define y second
 
int n,w;
int px[100000];
int py[100000];
int pw[100000][4]; // up, right, down, left
int wall1[200000];
int wall2[200000];
int cd;
int dead[200000];
unordered_set<int>sol;
 
void add(int p1,int p2,int wl){
    if(px[p1]==px[p2]){
        if(py[p2]<py[p1]){
            //cout<<"pw["<<p1<<"][2]="<<p2<<"\n";
            pw[p1][0]=wl;
        }else{
            //cout<<"pw["<<p1<<"][0]="<<p2<<"\n";
            pw[p1][2]=wl;
        }
    }else{
        if(px[p2]<px[p1]){
            //cout<<"pw["<<p1<<"][3]="<<p2<<"\n";
            pw[p1][3]=wl;
        }else{
            //cout<<"pw["<<p1<<"][1]="<<p2<<"\n";
            pw[p1][1]=wl;
        }
    }
}
 
int get_min_x(int a){
    return min(px[wall1[a]],px[wall2[a]]);
}

int get_min_y(int a){
    return min(py[wall1[a]],py[wall2[a]]);
}

bool cmp(int a,int b){
    if(get_min_x(a)==get_min_x(b))
        return get_min_y(a)<get_min_y(b);
    return get_min_x(a)<get_min_x(b);
}
 
void walk(int sw){
    cd++;
    int cw=sw;

    int cp=wall1[cw];
    if(py[wall2[cw]]<py[cp])
        cp=wall2[cw];
    if(px[wall2[cw]]<px[cp])
        cp=wall2[cw];
    
    int sp=cp;
    unordered_set<int>vis;
    //cout<<"WALK\n";
    while(true){
        //cout<<cp+1<<"\n";
        int way=0;
        while(pw[cp][way]!=cw)
            way=(way+1)%4;
        way=(way+1)%4;
        while(pw[cp][way]==-1||(dead[pw[cp][way]]!=0&&dead[pw[cp][way]]!=cd))
            way=(way+1)%4;
        //cout<<"way: "<<way<<"\n";
        dead[pw[cp][way]]=cd;
        cw=pw[cp][way];
        if(vis.count(cw))
            sol.insert(cw);
        else
            vis.insert(cw);
        if(cp==wall1[cw])
            cp=wall2[cw];
        else
            cp=wall1[cw];
        if(cp==sp)
            break;
    }
}
 
void solve(){
    for(int i=0;i<100000;i++)
        for(int j=0;j<4;j++)
            pw[i][j]=-1;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>px[i]>>py[i];
    cin>>w;
    for(int i=0;i<w;i++){
        cin>>wall1[i]>>wall2[i];
        wall1[i]--;
        wall2[i]--;
        add(wall1[i],wall2[i],i);
        add(wall2[i],wall1[i],i);
    }
    
    vector<int>walls(w);
    for(int i=0;i<w;i++)
        walls[i]=i;
    sort(walls.begin(),walls.end(),cmp);
    
    for(int wall:walls)
        if(dead[wall]==0)
            walk(wall);
    
    cout<<sol.size()<<"\n";
    for(int i:sol)
        cout<<i+1<<"\n";
}
 
int main(){
    ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
    //freopen("bank.in","r",stdin);freopen("bank.out","w",stdout);
    int t=1;//cin>>t;
    while(t--)solve();
    return 0;
}
 
/*
 
15
1 1
8 1
4 2
7 2
2 3
4 3
6 3
2 5
4 5
6 5
4 6
7 6
1 8
4 8
8 8
17
1 2
2 15
15 14
14 13
13 1
14 11
11 12
12 4
4 3
3 6
6 5
5 8
8 9
9 11
9 10
10 7
7 6
 
6
1 2
1 1
2 1
2 2
3 1
3 2
7
1 2
2 3
3 5
5 6
6 4
1 4
3 4
 
 
*/

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 5468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 7292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 5212 KB Output is correct
2 Incorrect 120 ms 8084 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 91 ms 8172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 8288 KB Output isn't correct
2 Halted 0 ms 0 KB -