oj.uz

답안 #653720

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
653720 2022-10-27T19:31:04 Z grt Flood (IOI07_flood) C++17
0 / 100
 160 ms 65536 KB 
//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];
pi connect[nax * 2];
vi events[1000 * 1000 + 10];
int p[(1 << 19)], siz[(1 << 19)];
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 << 21)];

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 = 1, int r = 1000 * 1000, 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};
        }
        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 = 1; i <= 1000 * 1000; ++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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 19 ms 36180 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 21 ms 36200 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 19 ms 36180 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 21 ms 36180 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 20 ms 36196 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 20 ms 36256 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 21 ms 36412 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 22 ms 36308 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 25 ms 36368 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 45 ms 44872 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 100 ms 46752 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 116 ms 62232 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 144 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 160 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -