oj.uz

Submission #140681

# Submission time Handle Problem Language Result Execution time Memory
140681 2019-08-04T12:36:10 Z khrbuddy03 None (KOI17_civilization) C++14
54 / 100
 1000 ms 54536 KB 
#include <bits/stdc++.h>

using namespace std;

const int inf = 2e3 + 9;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

struct ds {
    int par[inf * inf], siz[inf * inf];
    int find(int u) {
        if (u == par[u]) return u;
        return par[u] = find(par[u]);
    }
    void merge(int u, int v) {
        u = find(u); v = find(v);
        if (u == v) return;
        par[u] = v;
        siz[v] += siz[u];
        siz[u] = 0;
    }
} cul;

int n, m;
int vis[inf][inf];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n * n; ++i) cul.par[i] = i;
    memset(vis, -1, sizeof(vis));
    queue<pair<int, pair<int, int>>> q;
    for (int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;
        cul.siz[--y * n + --x] = 1;
        q.push(make_pair(0, make_pair(y, x)));
        vis[y][x] = y * n + x;
    }
    while (!q.empty()) {
        int dist = q.front().first;
        int y = q.front().second.first, x = q.front().second.second;
        int here = y * n + x;
        q.pop();
        cul.merge(here, vis[y][x]);
        for (int i = 0; i < 4; ++i) {
            int ny = y + dy[i], nx = x + dx[i];
            if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
            int there = ny * n + nx;
            if (cul.siz[cul.find(there)] && cul.siz[cul.find(here)]) cul.merge(there, here);
            if (vis[ny][nx] == -1) {
                q.push(make_pair(dist + 1, make_pair(ny, nx)));
                vis[ny][nx] = here;
            }
        }
        if (cul.siz[cul.find(here)] == m) {
            cout << dist << '\n';
            break;
        }
    }
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16248 KB Output is correct
2 Correct 15 ms 16248 KB Output is correct
3 Correct 16 ms 16248 KB Output is correct
4 Correct 15 ms 16248 KB Output is correct
5 Correct 16 ms 16248 KB Output is correct
6 Correct 19 ms 16248 KB Output is correct
7 Correct 16 ms 16248 KB Output is correct
8 Correct 16 ms 16252 KB Output is correct
9 Correct 16 ms 16248 KB Output is correct
10 Correct 15 ms 16248 KB Output is correct
11 Correct 16 ms 16248 KB Output is correct
12 Correct 16 ms 16248 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16248 KB Output is correct
2 Correct 15 ms 16248 KB Output is correct
3 Correct 16 ms 16248 KB Output is correct
4 Correct 15 ms 16248 KB Output is correct
5 Correct 16 ms 16248 KB Output is correct
6 Correct 19 ms 16248 KB Output is correct
7 Correct 16 ms 16248 KB Output is correct
8 Correct 16 ms 16252 KB Output is correct
9 Correct 16 ms 16248 KB Output is correct
10 Correct 15 ms 16248 KB Output is correct
11 Correct 16 ms 16248 KB Output is correct
12 Correct 118 ms 23980 KB Output is correct
13 Correct 89 ms 24004 KB Output is correct
14 Correct 109 ms 24060 KB Output is correct
15 Correct 83 ms 23928 KB Output is correct
16 Correct 30 ms 22392 KB Output is correct
17 Correct 293 ms 28960 KB Output is correct
18 Correct 303 ms 28920 KB Output is correct
19 Correct 306 ms 29048 KB Output is correct
20 Correct 297 ms 29048 KB Output is correct
21 Correct 287 ms 29036 KB Output is correct
22 Correct 22 ms 24056 KB Output is correct
23 Correct 128 ms 24172 KB Output is correct
24 Correct 16 ms 16248 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16248 KB Output is correct
2 Correct 15 ms 16248 KB Output is correct
3 Correct 16 ms 16248 KB Output is correct
4 Correct 15 ms 16248 KB Output is correct
5 Correct 16 ms 16248 KB Output is correct
6 Correct 19 ms 16248 KB Output is correct
7 Correct 16 ms 16248 KB Output is correct
8 Correct 16 ms 16252 KB Output is correct
9 Correct 16 ms 16248 KB Output is correct
10 Correct 15 ms 16248 KB Output is correct
11 Correct 16 ms 16248 KB Output is correct
12 Correct 118 ms 23980 KB Output is correct
13 Correct 89 ms 24004 KB Output is correct
14 Correct 109 ms 24060 KB Output is correct
15 Correct 83 ms 23928 KB Output is correct
16 Correct 30 ms 22392 KB Output is correct
17 Correct 293 ms 28960 KB Output is correct
18 Correct 303 ms 28920 KB Output is correct
19 Correct 306 ms 29048 KB Output is correct
20 Correct 297 ms 29048 KB Output is correct
21 Correct 287 ms 29036 KB Output is correct
22 Correct 22 ms 24056 KB Output is correct
23 Correct 128 ms 24172 KB Output is correct
24 Correct 319 ms 45432 KB Output is correct
25 Correct 421 ms 47588 KB Output is correct
26 Correct 277 ms 46584 KB Output is correct
27 Correct 352 ms 45560 KB Output is correct
28 Correct 232 ms 45548 KB Output is correct
29 Execution timed out 1075 ms 54536 KB Time limit exceeded
30 Halted 0 ms 0 KB -