oj.uz

Submission #1020321

# Submission time Handle Problem Language Result Execution time Memory
1020321 2024-07-11T23:30:32 Z vjudge1 Flood (IOI07_flood) C++17
55 / 100
 63 ms 34272 KB 
#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],R,vis[200100],fall[200100],lev[100100];
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;
    lev[1]=1;
    while(Q.size()){
        int x=Q.front();Q.pop();
        for(auto[i,j]:adj[x])if(!lev[i])
            Q.push(i),lev[i]=lev[x]+1;
    }
    set<int>v;
    for(int i=1;i<=R;i++)
        for(auto[x,j]:adj[i])
            if(lev[x]==lev[i])
                v.insert(j);
    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 5208 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8028 KB Output is correct
2 Correct 3 ms 5948 KB Output is correct

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 10588 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 36 ms 17576 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 63 ms 34272 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 44 ms 14176 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 14116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -