oj.uz

Submission #895770

# Submission time Handle Problem Language Result Execution time Memory
895770 2023-12-30T19:08:03 Z abcvuitunggio Flood (IOI07_flood) C++17
100 / 100
 57 ms 12648 KB 
#include <bits/stdc++.h>
using namespace std;
int n,w,x[100001],y[100001],a[200001],b[200001],nxt[100001][4],dx[4]={1,0,-1,0},dy[4]={0,1,0,-1},p[400001],l[100001],mx[100001],cnt;
vector <pair <int, int>> q[100005];
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]);
        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]])){
                nxt[a[i]][j]=i;
                nxt[b[i]][(j+2)%4]=i+w;
                break;
            }
    }
    for (int i=1;i<=n;i++){
        int j=f(i);
        if (!mx[j]||x[mx[j]]>x[i]||(x[mx[j]]==x[i]&&y[mx[j]]<y[i]))
            mx[j]=i;
    }
    for (int i=1;i<=n;i++)
        if (i==f(i))
            for (int j=0;j<4;j++)
                if (nxt[mx[i]][(j+3)%4]){
                    q[1].push_back({nxt[mx[i]][(j+3)%4],(j+3)%4});
                    break;
                }
    for (int i=1;i<n+5;i++)
        while (!q[i].empty()){
            auto [u,d]=q[i].back();
            q[i].pop_back();
            if (p[u])
                continue;
            p[u]=i;
            q[i+1].push_back({(u>w?u-w:u+w),(d+2)%4});
            int cur=(u>w?a[u-w]:b[u]);
            for (int j=0;j<4;j++)
                if (nxt[cur][(d+j+3)%4]){
                    int v=nxt[cur][(d+j+3)%4];
                    q[i].push_back({v,(d+j+3)%4});
                    break;
                }
        }
    for (int i=1;i<=w;i++)
        if (p[i]==p[i+w])
            cnt++;
    cout << cnt << '\n';
    for (int i=1;i<=w;i++)
        if (p[i]==p[i+w])
            cout << i << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9444 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11016 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11348 KB Output is correct
2 Correct 57 ms 11732 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 11424 KB Output is correct
2 Correct 56 ms 12648 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 11632 KB Output is correct
2 Correct 45 ms 11224 KB Output is correct