oj.uz

Submission #140677

# Submission time Handle Problem Language Result Execution time Memory
140677 2019-08-04T12:26:37 Z khrbuddy03 None (KOI17_civilization) C++14
54 / 100
 1000 ms 70168 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], rank[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;
        if (rank[u] > rank[v]) swap(u, v);
        par[u] = v;
        siz[v] += siz[u];
        siz[u] = 0;
        if (rank[u] == rank[v]) rank[v]++;
    }
} 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;
    fill(&cul.rank[0], &cul.rank[n * n - 1], 0);
    fill(&vis[0][0], &vis[n - 1][n - 1], -1);
    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 3 ms 1244 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 3 ms 1272 KB Output is correct
4 Correct 3 ms 1272 KB Output is correct
5 Correct 3 ms 1272 KB Output is correct
6 Correct 3 ms 1272 KB Output is correct
7 Correct 4 ms 1272 KB Output is correct
8 Correct 4 ms 1272 KB Output is correct
9 Correct 4 ms 1272 KB Output is correct
10 Correct 15 ms 1272 KB Output is correct
11 Correct 3 ms 1272 KB Output is correct
12 Correct 3 ms 1272 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1244 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 3 ms 1272 KB Output is correct
4 Correct 3 ms 1272 KB Output is correct
5 Correct 3 ms 1272 KB Output is correct
6 Correct 3 ms 1272 KB Output is correct
7 Correct 4 ms 1272 KB Output is correct
8 Correct 4 ms 1272 KB Output is correct
9 Correct 4 ms 1272 KB Output is correct
10 Correct 15 ms 1272 KB Output is correct
11 Correct 3 ms 1272 KB Output is correct
12 Correct 122 ms 19964 KB Output is correct
13 Correct 102 ms 20048 KB Output is correct
14 Correct 136 ms 19960 KB Output is correct
15 Correct 88 ms 19988 KB Output is correct
16 Correct 32 ms 18424 KB Output is correct
17 Correct 359 ms 25080 KB Output is correct
18 Correct 274 ms 24952 KB Output is correct
19 Correct 302 ms 24952 KB Output is correct
20 Correct 287 ms 25080 KB Output is correct
21 Correct 308 ms 24952 KB Output is correct
22 Correct 19 ms 20088 KB Output is correct
23 Correct 149 ms 20088 KB Output is correct
24 Correct 3 ms 1272 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1244 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 3 ms 1272 KB Output is correct
4 Correct 3 ms 1272 KB Output is correct
5 Correct 3 ms 1272 KB Output is correct
6 Correct 3 ms 1272 KB Output is correct
7 Correct 4 ms 1272 KB Output is correct
8 Correct 4 ms 1272 KB Output is correct
9 Correct 4 ms 1272 KB Output is correct
10 Correct 15 ms 1272 KB Output is correct
11 Correct 3 ms 1272 KB Output is correct
12 Correct 122 ms 19964 KB Output is correct
13 Correct 102 ms 20048 KB Output is correct
14 Correct 136 ms 19960 KB Output is correct
15 Correct 88 ms 19988 KB Output is correct
16 Correct 32 ms 18424 KB Output is correct
17 Correct 359 ms 25080 KB Output is correct
18 Correct 274 ms 24952 KB Output is correct
19 Correct 302 ms 24952 KB Output is correct
20 Correct 287 ms 25080 KB Output is correct
21 Correct 308 ms 24952 KB Output is correct
22 Correct 19 ms 20088 KB Output is correct
23 Correct 149 ms 20088 KB Output is correct
24 Correct 364 ms 60860 KB Output is correct
25 Correct 481 ms 63216 KB Output is correct
26 Correct 309 ms 62200 KB Output is correct
27 Correct 360 ms 61200 KB Output is correct
28 Correct 255 ms 61084 KB Output is correct
29 Execution timed out 1080 ms 70168 KB Time limit exceeded
30 Halted 0 ms 0 KB -