Submission #906030

#	Time	Username	Problem	Language	Result	Execution time	Memory
906030		JakobZorz	Flood (IOI07_flood)	C++17	38 / 100	132 ms	9056 KiB

flood

#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][2];
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][2]=wl;
        }else{
            //cout<<"pw["<<p1<<"][0]="<<p2<<"\n";
            pw[p1][0]=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,int o){
    int di=(o+1)/2;
    cd++;
    int cw=sw;
    int cp=0;
    
    if(o==1){
        cp=wall1[cw];
        if(py[wall2[cw]]<py[cp])
            cp=wall2[cw];
        if(px[wall2[cw]]<px[cp])
            cp=wall2[cw];
    }else{
        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+o+4)%4;
        way=(way+o+4)%4;;
        while(pw[cp][way]==-1||(dead[pw[cp][way]][di]!=0&&dead[pw[cp][way]][di]!=cd))
            way=(way+o+4)%4;
        //cout<<"way: "<<way<<"\n";
        dead[pw[cp][way]][di]=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][1]==0)
            walk(wall,1);
        if(dead[wall][0]==0)
            walk(wall,-1);
    }
    
    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
5
1 2
2 3
3 4
3 5
5 6
 
 
*/

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 3 / 3
• Subtask 5: 0 / 10
• Subtask 6: 3 / 3
• Subtask 7: 3 / 3
• Subtask 8: 0 / 3
• Subtask 9: 0 / 3
• Subtask 10: 0 / 9
• Subtask 11: 9 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9