oj.uz

Submission #95398

# Submission time Handle Problem Language Result Execution time Memory
95398 2019-01-31T12:50:01 Z easrui Flood (IOI07_flood) C++14
100 / 100
 124 ms 8608 KB 
#include <bits/stdc++.h>
using namespace std;
const int MN = 2e5+5;
vector<int> wall;
int N,W,X[MN],Y[MN],A[MN],B[MN],C[4][MN],cnt[MN],wpos[MN],pos,cur,dir,ans;
bool v[MN];
bool cmp(int a, int b)
{
    if(Y[A[a]]==Y[A[b]])
        return X[A[a]]<X[A[b]];
    return Y[A[a]]<Y[A[b]];
}

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> N;
    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];
        if(X[A[i]]==X[B[i]]) {
            if(Y[A[i]]>Y[B[i]])
                swap(A[i],B[i]);
            C[2][A[i]] = i;
            C[0][B[i]] = i;
        } else {
            if(X[A[i]]>X[B[i]])
                swap(A[i],B[i]);
            C[3][A[i]] = i;
            C[1][B[i]] = i;
        }
    }
    for(int i=0; i<W; i++)
        wpos[i] = i+1;
    sort(wpos,wpos+W,cmp);

    while(1) {
        while(v[wpos[pos]] && pos<W) pos++;
        if(pos==W) break;
        cur = A[wpos[pos]];
        if(X[cur]==X[B[wpos[pos]]]) dir = 2;
        else dir = 3;
        while(1) {
            for(int i=0; i<4; i++) {
                int wnum = C[(dir+3+i)%4][cur];
                if(wnum && !v[wnum]) {
                    wall.push_back(wnum);
                    cnt[wnum]++;
                    if(cnt[wnum]==2) ans++;
                    cur = A[wnum] + B[wnum] - cur;
                    dir = (dir+3+i)%4;
                    break;
                }
            }
            if(cur==A[wpos[pos]]) break;
        }
        while(wall.size()) {
            v[wall[wall.size()-1]] = true;
            wall.pop_back();
        }
    }
    cout << ans << '\n';
    for(int i=1; i<=W; i++) if(cnt[i]==2) cout << i << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1900 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 6264 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 6264 KB Output is correct
2 Correct 124 ms 8464 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 7672 KB Output is correct
2 Correct 114 ms 8608 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 8312 KB Output is correct
2 Correct 83 ms 7484 KB Output is correct