제출 #653722

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
653722		grt	Flood (IOI07_flood)	C++17	91 / 100	233 ms	33428 KiB

flood

//GRT_2018
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

struct Point {
        int x, y;
};

const int nax = 100 * 1000 + 10;
int n, w;
Point pts[nax];
pi walls[nax * 2];
vi events[nax];
int p[400 * 1000 + 10], siz[400 * 1000 + 10];
pi G[nax][4];

int Fund(int x) {
        if(p[x] != x) {
                p[x] = Fund(p[x]);
        }
        return p[x];
}

void Onion(int a, int b) {
        a = Fund(a), b = Fund(b);
        if(a == b) return;
        if(siz[a] < siz[b]) swap(a, b);
        p[b] = a;
        siz[a] += siz[b];
}

struct Node {
        int mi, mx, g;
        bool act;
};

Node T[(1 << 18)];
map<int,int>sc;
int roz;

void putTag(int v, int x) {
        T[v].act = true;
        T[v].mi = T[v].mx = T[v].g = x;
}

void push(int v) {
        if(!T[v].act) return;
        putTag(v << 1, T[v].g);
        putTag(v << 1 | 1, T[v].g);
        T[v].act = 0;
}

void pull(int v) {
        T[v].mi = min(T[v << 1].mi, T[v << 1 | 1].mi);
        T[v].mx = max(T[v << 1].mx, T[v << 1 | 1].mx);
}

void upd(int a, int b, int x, bool modify = 1, int l = 0, int r = roz - 1, int v = 1) {
        if(a <= l && r <= b && T[v].mx == T[v].mi) {
                // merge (x << 1, T[v].mx)
                if(!modify) {
//                      cerr << "merging: " << (x << 1) << " with " << T[v].mx << "\n";
                        Onion(x << 1, T[v].mx);
                } else {
                        if(modify) putTag(v, x << 1 | 1);
                }
                return;
        }
        int mid = (l + r) >> 1;
        push(v);
        if(a <= mid) upd(a, b, x, modify, l, mid, v << 1);
        if(mid < b) upd(a, b, x, modify, mid + 1, r, v << 1 | 1);
        pull(v);
}

bool vis[(1 << 19)];

void walk(int x, int dir) {
        int id = G[x][dir].ND;
        vis[G[x][dir].ND] = true;
        x = G[x][dir].ST;
        dir = (dir + 1) % 4;
        while(G[x][dir].ST == 0) {
                dir = (dir + 3) % 4;
        }
        if(!vis[G[x][dir].ND]) {
                Onion(id, G[x][dir].ND);
//              cerr << "polygon : " << id << " with " << G[x][dir].ND << " " << dir << "\n";
                walk(x, dir);
        }
}

vi V[(1 << 19)];
int dist[(1 << 19)];

void bfs(int x) {
        for(int i = 0; i <= 2 * w + 1; ++i) {
                vis[i] = false;
        }
        queue<int>Q;
        Q.push(x);
        vis[x] = true;
        while(!Q.empty()) {
                x = Q.front();
                Q.pop();
//              cerr << "DIST: " << x << " " << dist[x] << "\n";
                for(int y : V[x]) {
                        if(!vis[y]) {
                                dist[y] = dist[x] + 1;
                                vis[y] = true;
                                Q.push(y);
                        }
                }
        }
}

int main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cin >> n;
        for(int x, y, i = 1; i <= n; ++i) {
                cin >> x >> y;
                pts[i] = {x, y};
                sc[y];
        }
        for(auto &it : sc) it.ND = roz++;
        int num = 0;
        for(int i = 1; i <= n; ++i) pts[i].y = sc[pts[i].y];
        sc.clear();
        for(int i = 1; i <= n; ++i) sc[pts[i].x];
        for(auto &it : sc) it.ND = num++;
        for(int i = 1; i <= n; ++i) pts[i].x = sc[pts[i].x];
        cin >> w;
        siz[0] = 1;
        for(int a, b, i = 1; i <= w; ++i) {
                cin >> a >> b;
                if(pts[a].x == pts[b].x) {
                        events[pts[a].x].PB(i);
                        if(pts[a].y > pts[b].y) swap(a, b);
                        G[a][0] = {b, i << 1 | 1};
                        G[b][2] = {a, i << 1};
                } else {
                        if(pts[a].x > pts[b].x) {
                                swap(a, b);
                        }
                        G[a][1] = {b, i << 1 | 1};
                        G[b][3] = {a, i << 1};
                }
                walls[i] = {a, b};
                p[i << 1] = (i << 1);
                p[i << 1 | 1] = (i << 1 | 1);
                siz[i << 1] = siz[i << 1 | 1] = 1;
        }
//      cerr << "SHOW GRAPH\n";
//      for(int i = 1; i <= n; ++i) {
//              for(int d = 0; d < 4; ++d) {
//                      if(G[i][d].ST != 0) {
//                              cerr << i << " " << d << ": " << G[i][d].ST << " " << G[i][d].ND << "\n";
//                      }
//              }
//      }
        for(int i = 0; i < num ; ++i) {
                for(auto &id : events[i]) {
                        upd(pts[walls[id].ST].y, pts[walls[id].ND].y - 1, id, 0);
                }
                for(auto &id : events[i]) {
                        upd(pts[walls[id].ST].y, pts[walls[id].ND].y - 1, id, 1);
                }

        }
        for(int i = 1; i <= n; ++i) {
                for(int d = 0; d < 4; ++d) {
                        if(G[i][d].ST != 0 && !vis[G[i][d].ND]) {
                                walk(i, d);
                        }
                }
        }
        for(int i = 1; i <= w; ++i) {
                V[Fund(i << 1)].PB(Fund(i << 1 | 1));
                V[Fund(i << 1 | 1)].PB(Fund(i << 1));
        }
        bfs(Fund(0));
        vi ans = {};
        for(int i = 1; i <= w; ++i) {
                if(dist[Fund(i << 1)] == dist[Fund(i << 1 | 1)]) {
                        ans.PB(i);
                }
        }
        cout << (int)ans.size() << "\n";
        for(int x : ans) {
                cout << x << "\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: 0 / 9
• Subtask 14: 9 / 9