Submission #95398

#	Time	Username	Problem	Language	Result	Execution time	Memory
95398		easrui	Flood (IOI07_flood)	C++14	100 / 100	124 ms	8608 KiB

flood

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 3 / 3
• Subtask 5: 10 / 10
• Subtask 6: 3 / 3
• Subtask 7: 3 / 3
• Subtask 8: 3 / 3
• Subtask 9: 3 / 3
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9
• Subtask 13: 9 / 9
• Subtask 14: 9 / 9