Submission #1020320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020320		vjudge1	Flood (IOI07_flood)	C++17	36 / 100	61 ms	34392 KiB

flood

#include<bits/stdc++.h>
using namespace std;
map<int,int>mpx,mpy;
int X[200100],Y[200100],CCx,CCy,reg[1010][1010],wal[1010][1010][2],lev,R,vis[200100],fall[200100];
vector<pair<int,int>> Wx,Wy,adj[200100];
void flod(int x,int y,int c){
    if(x<0||y<0||x>CCx+10||y>CCy+10) return;
    if(reg[x][y]) return;
    reg[x][y]=c;
    if(!wal[x][y][0])
        flod(x,y-1,c);
    if(!wal[x][y+1][0])
        flod(x,y+1,c);
    if(!wal[x][y][1])
        flod(x-1,y,c);
    if(!wal[x+1][y][1])
        flod(x+1,y,c);
}
void AE(int a,int b,int c){
    adj[a].push_back({b,c});
    adj[b].push_back({a,c});
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,w;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>X[i]>>Y[i];
        mpx[X[i]];
        mpy[Y[i]];
    }
    for(auto&[i,j]:mpx)
        j=++CCx;
    for(auto&[i,j]:mpy)
        j=++CCy;
    cin>>w;
    for(int i=1;i<=n;i++)
        X[i]=mpx[X[i]],
        Y[i]=mpy[Y[i]];
    for(int i=1;i<=w;i++){
        int a,b;
        cin>>a>>b;
        if(X[a]==X[b]){
            if(Y[a]>Y[b])
                swap(a,b);
            for(int j=Y[a];j<Y[b];j++)
                wal[X[a]][j][1]=i;
            Wx.push_back({X[a],Y[a]});
        } else {
            if(X[a]>X[b])swap(a,b);
            for(int j=X[a];j<X[b];j++)
                wal[j][Y[b]][0]=i;
            Wy.push_back({X[a],Y[a]});
        }
    }
    for(int i=0;i<CCx+10;i++)
        for(int j=0;j<CCy+10;j++)
            if(!reg[i][j])flod(i,j,++R);
    for(auto [i,j]:Wx)
        AE(reg[i-1][j],reg[i][j],wal[i][j][1]);
    for(auto [i,j]:Wy)
        AE(reg[i][j-1],reg[i][j],wal[i][j][0]);
    queue<int>Q;
    Q.push(1);
    vis[1]=1;
    while(Q.size()){
        int x=Q.front();
        Q.pop();
        for(auto[i,j]:adj[x])
            if(!vis[i])
                Q.push(i),
                fall[j]=1;
        for(auto[i,j]:adj[x])
            vis[i]=1;
    }
    vector<int>v;
    for(int i=1;i<=w;i++)
        if(!fall[i])
            v.push_back(i);
    cout<<v.size()<<'\n';
    for(auto i:v)
        cout<<i<<'\n';
}

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