제출 #1291034

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291034		BlockOG	Flood (IOI07_flood)	C++20	82 / 100	466 ms	32848 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];

map<int, pair<int, int>> comps;
int dsudsu[400000];

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

int get_dsu(int i) {
    if (dsudsu[i] == i) return i;
    return dsudsu[i] = get_dsu(dsudsu[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;
}

void merge_dsu(int i, int j) {
    i = get_dsu(i), j = get_dsu(j);
    if (i == j) return;
    
    if (comps[j].s < comps[i].s) comps[i] = comps[j];
    comps.erase(j);
    dsudsu[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 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].f > p[b].f) swap(a, b);
            pe[a][2] = {i*2+1, i*2  };
            pe[b][0] = {i*2  , i*2+1};
            comps[i*2] = {i*2+1, p[a].s};
        } else {
            if (p[a].s > p[b].s) swap(a, b);
            pe[a][3] = {i*2  , i*2+1};
            pe[b][1] = {i*2+1, i*2  };
            comps[i*2] = {i*2+1, 2000000};
        }

        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  );

        dsudsu[i*2] = dsudsu[i*2+1] = 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);
                        merge_dsu(j, pe[i][(k + l) % 4].f);
                        j = pe[i][(k + l) % 4].s;
                    }
                
                break;
            }
    }

    set<int> res;

    for (auto [_, mimy] : comps) {
        auto [mi, my] = mimy;
        
        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: 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: 0 / 9
• Subtask 14: 0 / 9