oj.uz

Submission #895741

# Submission time Handle Problem Language Result Execution time Memory
895741 2023-12-30T18:01:07 Z abcvuitunggio Flood (IOI07_flood) C++17
0 / 100
 42 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;
int n,w,x[100001],y[100001],a[400001],b[400001],d[400001],nxt[100001][4],dx[4]={1,0,-1,0},dy[4]={0,1,0,-1},p[400001],l[100001];
vector <int> safe,ve[100001];
queue <int> q[200002];
int f(int i){
    return (l[i]==i?i:l[i]=f(l[i]));
}
int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n;
    iota(l,l+n+1,0);
    for (int i=1;i<=n;i++)
        cin >> x[i] >> y[i];
    cin >> w;
    for (int i=1;i<=w;i++){
        cin >> a[i] >> b[i];
        l[f(a[i])]=f(b[i]);
        a[i+w]=b[i];
        b[i+w]=a[i];
        for (int j=0;j<4;j++)
            if (abs(dx[j])+abs(x[a[i]]+dx[j]-x[b[i]])==abs(x[a[i]]-x[b[i]])&&abs(dy[j])+abs(y[a[i]]+dy[j]-y[b[i]])==abs(y[a[i]]-y[b[i]])){
                d[i]=j;
                d[i+w]=(j+2)&3;
                nxt[a[i]][j]=i;
                nxt[b[i]][d[i+w]]=i+w;
            }
    }
    for (int i=1;i<=n;i++)
        ve[f(i)].push_back(i);
    for (int i=1;i<=n;i++){
        if (ve[i].empty())
            continue;
        int mx=0;
        for (int j:ve[i])
            if (!mx||x[mx]>x[j]||(x[mx]==x[j]&&y[mx]<y[j]))
                mx=j;
        if (!nxt[mx][3])
            continue;
        q[1].push(nxt[mx][3]);
    }
    for (int i=1;i<=n*2;i++)
        while (!q[i].empty()){
            int u=q[i].front();
            q[i].pop();
            if (p[u])
                continue;
            p[u]=i;
            q[i+1].push((u>w?u-w:u+w));
            for (int j=0;j<4;j++)
                if (nxt[b[u]][(d[u]+j+3)%4]){
                    int v=nxt[b[u]][(d[u]+j+3)%4];
                    q[i].push(v);
                    break;
                }
        }
    for (int i=1;i<=w;i++)
        if (p[i]==p[i+w])
            safe.push_back(i);
    cout << safe.size() << '\n';
    for (int i:safe)
        cout << i << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -