제출 #1291005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291005		BlockOG	Flood (IOI07_flood)	C++20	33 / 100	118 ms	24624 KiB

flood

#include <bits/stdc++.h>

// meeeooowwwww mrrowwww :3
// go play vivid/stasis!! now!!!! https://vividstasis.gay

#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;

int ____init = []{
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    return 0;
}();

pair<int, int> p[100000];
pair<int, int> pe[100000][4];
int dsu[400000];
vector<int> dsd[400000];

int get(int i) {
    if (i < 0 || dsu[i] == i) return i;
    return dsu[i] = get(dsu[i]);
}

void merge(int i, int j) {
    i = get(i), j = get(j);
    if (i == j) return;

    if (dsd[i].size() < dsd[j].size()) swap(i, j);
    for (int k : dsd[j]) dsd[i].pb(k);
    dsd[j].clear();
    dsu[j] = i;
}

int main() {
    int n; cin >> n;
    fo(i, 0, n) cin >> p[i].f >> p[i].s, pe[i][0] = {-1, -1}, pe[i][1] = {-1, -1}, pe[i][2] = {-1, -1}, pe[i][3] = {-1, -1};

    int mi = 0, my = 2000000;
    
    int w; cin >> w;
    fo(i, 0, w) {
        int a, b; cin >> a >> b; a--, b--;
        if (p[a].s == p[b].s) {
            if (p[a].s < my) mi = i*2+1, my = p[a].s;

            if (p[a].f > p[b].f) swap(a, b);
            pe[a][2] = {i*2+1, i*2  };
            pe[b][0] = {i*2  , i*2+1};
        } else {
            if (p[a].s > p[b].s) swap(a, b);
            pe[a][3] = {i*2+1, i*2  };
            pe[b][1] = {i*2  , i*2+1};
        }

        dsu[i*2  ] = i*2  ;
        dsu[i*2+1] = i*2+1;
        dsd[i*2  ].pb(i*2+1);
        dsd[i*2+1].pb(i*2  );
    }

    fo(i, 0, n) {
        fo(k, 0, 4) 
            if (pe[i][k].f != -1) {
                int j = pe[i][k].s;
                fo(l, 1, 5)
                    if (pe[i][(k + l) % 4].f != -1) {
                        merge(j, pe[i][(k + l) % 4].f);
                        j = pe[i][(k + l) % 4].s;
                    }
                
                break;
            }
    }

    set<int> res;

    queue<int> q; q.push(get(mi)); dsu[get(mi)] = -1;
    while (q.size()) {
        int i = q.front(); q.pop();

        for (int j : dsd[i]) {
            int k = get(j);
            if (k < 0) {
                if (k == dsu[i]) res.insert(j / 2);
                continue;
            }

            dsu[k] = dsu[i] - 1;
            q.push(k);
        }
    }

    cout << res.size() << endl;
    for (int i : res) cout << i + 1 << endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 3
• Subtask 5: 0 / 10
• Subtask 6: 3 / 3
• Subtask 7: 0 / 3
• Subtask 8: 0 / 3
• Subtask 9: 0 / 3
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9