oj.uz

Submission #906040

# Submission time Handle Problem Language Result Execution time Memory
906040 2024-01-13T11:13:08 Z JakobZorz Flood (IOI07_flood) C++17
100 / 100
 89 ms 9536 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];
vector<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;
    //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";
        if(dead[pw[cp][way]]==cd)
            sol.push_back(pw[cp][way]);
        dead[pw[cp][way]]=cd;
        cw=pw[cp][way];
        if(cp==wall1[cw])
            cp=wall2[cw];
        else
            cp=wall1[cw];
        if(cp==sp&&cw==sw)
            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
 
8
1 2
1 1
2 1
2 2
3 1
3 2
4 1
4 2
10
1 2
2 3
3 5
5 6
6 4
1 4
3 4
5 7
6 8
7 8
 
 
4
1 2
1 1
2 1
2 2
3
4 1
3 4
2 3
 
*/

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

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

Subtask #11
9.0 / 9.0

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

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 5436 KB Output is correct
2 Correct 80 ms 6356 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 6088 KB Output is correct
2 Correct 89 ms 9536 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 6156 KB Output is correct
2 Correct 54 ms 8916 KB Output is correct