oj.uz

Submission #1020318

# Submission time Handle Problem Language Result Execution time Memory
1020318 2024-07-11T23:13:24 Z vjudge1 Flood (IOI07_flood) C++17
36 / 100
 52 ms 28948 KB 
#include<bits/stdc++.h>
using namespace std;
map<int,int>mpx,mpy;
int X[200100],Y[200100],CCx,CCy,reg[550][550],wal[550][550][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+2||y>CCy+2) 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+2;i++)
        for(int j=0;j<CCy+2;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.0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
0 / 3.0

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

Subtask #9
0 / 3.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 17504 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 28948 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 14284 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 14164 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -