oj.uz

Submission #158692

# Submission time Handle Problem Language Result Execution time Memory
158692 2019-10-18T12:45:03 Z solarmagic None (KOI17_civilization) C++17
0 / 100
 1000 ms 258488 KB 
#include <bits/stdc++.h>
using namespace std;

int N, M;
int p[100001];
int world[2001][2001];
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
int find(int u) {
    if (p[u] == u) return u;
    return p[u] = find(p[u]);
}
void merge(int u, int v) {
    u = find(u);
    v = find(v);
    p[u] = v;
}
bool isIn(int x, int y) { return x > 0 && x <= N && y > 0 && y <= N; }
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    queue<pair<int, int>> q;
    cin >> N >> M;
    for (int i = 1; i <= M; i++) {
        int x, y; cin >> x >> y;
        world[x][y] = i;
        q.push({x,y});
        p[i] = i;
    }

    int ans = 0;
    while (true) {
        vector<tuple<int,int,int>> v;
        while (!q.empty()) {
            auto [x,y] = q.front();
            q.pop();
            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                if (isIn(nx,ny)) {
                    if (world[nx][ny]) {
                        if (find(world[nx][ny]) != find(world[x][y])) {
                            merge(world[nx][ny], world[x][y]); 
                            M--;
                        }
                    } else {
                        v.push_back({nx,ny,world[x][y]});
                    }
                }
            }
        }
        if (M == 1) break;
        ++ans;
        for (auto [x, y, w] : v) {
            if (world[x][y] && find(world[x][y]) != find(w)) {
                merge(world[x][y], w);
                M--;
            }
            world[x][y] = find(w);
            q.push({x,y});
        }
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 258488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 258488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 258488 KB Time limit exceeded
2 Halted 0 ms 0 KB -