oj.uz

Submission #678359

# Submission time Handle Problem Language Result Execution time Memory
678359 2023-01-05T15:04:13 Z omikron123 Tracks in the Snow (BOI13_tracks) C++14
84.6875 / 100
 2000 ms 1048576 KB 
// https://oj.uz/problem/view/BOI13_tracks

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;

// n,m <= 4000
int h, w;
char s[4005][4005];
int c[4005][4005];
set<int> adj[16000005];
queue<pair<int,int>> q;

void floodfill(int i, int j, char t, int co) {
    q.push({i,j});
    while (!q.empty()) {
        tie(i, j) = q.front();
        q.pop();
        if (i < 0 || i >= h || j < 0 || j >= w || c[i][j]) continue;
        if (s[i][j] != t) continue;
        c[i][j] = co;
        q.push({i+1,j});
        q.push({i-1,j});
        q.push({i,j+1});
        q.push({i,j-1});
    }
}

void link(int i, int j, int p, int q) {
    if (p < 0 || p >= h || q < 0 || q >= w) return;
    if (s[i][j] == '.' || s[p][q] == '.') return;
    int c1 = c[i][j], c2 = c[p][q];
    if (c1 == c2) return;
    adj[c1].insert(c2);
    adj[c2].insert(c1);
}

queue<pair<int,int>> Q;
vector<int> d;

int main() {
    scanf("%d %d", &h, &w);
    for (int i = 0; i < h; i++)
        scanf("%s", s[i]);
    int co = 1;
    // floodfill
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++) {
            if (s[i][j] != '.' && c[i][j] == 0) {
                floodfill(i, j, s[i][j], co++);
            }
        }
    // link the nodes
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++) {
            link(i,j,i+1,j);
            link(i,j,i-1,j);
            link(i,j,i,j+1);
            link(i,j,i,j-1);
        }
    // bfs to find depth from (1,1)
    Q.push({c[0][0],1});
    d.resize(co);
    for (int i = 0; i < co; i++)
        d[i] = 0;
    int ans = 0;
    while (!Q.empty()) {
        int u = Q.front().first;
        int dep = Q.front().second;
        Q.pop();
        if (d[u]) continue;
        d[u] = dep;
        ans = max(ans, dep);
        for (int v: adj[u]) {
            Q.push({v, dep+1});
        }
    }
    printf("%d", ans);

    return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d %d", &h, &w);
      |     ~~~~~^~~~~~~~~~~~~~~~~
tracks.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         scanf("%s", s[i]);
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 762168 KB Output is correct
2 Correct 348 ms 751872 KB Output is correct
3 Correct 329 ms 752092 KB Output is correct
4 Correct 332 ms 756680 KB Output is correct
5 Correct 325 ms 755448 KB Output is correct
6 Correct 316 ms 751892 KB Output is correct
7 Correct 320 ms 752292 KB Output is correct
8 Correct 316 ms 752276 KB Output is correct
9 Correct 320 ms 752756 KB Output is correct
10 Correct 329 ms 754800 KB Output is correct
11 Correct 326 ms 753628 KB Output is correct
12 Correct 337 ms 756392 KB Output is correct
13 Correct 321 ms 755184 KB Output is correct
14 Correct 328 ms 755264 KB Output is correct
15 Correct 354 ms 761488 KB Output is correct
16 Correct 369 ms 762128 KB Output is correct
17 Correct 343 ms 760996 KB Output is correct
18 Correct 363 ms 756816 KB Output is correct

Subtask #2
54.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 782768 KB Output is correct
2 Correct 473 ms 789156 KB Output is correct
3 Correct 1276 ms 973348 KB Output is correct
4 Correct 524 ms 811448 KB Output is correct
5 Runtime error 942 ms 1048576 KB Execution killed with signal 9
6 Execution timed out 2137 ms 880476 KB Time limit exceeded
7 Correct 391 ms 784036 KB Output is correct
8 Correct 403 ms 782740 KB Output is correct
9 Correct 370 ms 752776 KB Output is correct
10 Correct 381 ms 752124 KB Output is correct
11 Correct 350 ms 783308 KB Output is correct
12 Correct 373 ms 754060 KB Output is correct
13 Correct 501 ms 789216 KB Output is correct
14 Correct 423 ms 775016 KB Output is correct
15 Correct 425 ms 778500 KB Output is correct
16 Correct 403 ms 768028 KB Output is correct
17 Correct 701 ms 839196 KB Output is correct
18 Correct 618 ms 841036 KB Output is correct
19 Correct 532 ms 811468 KB Output is correct
20 Correct 527 ms 812416 KB Output is correct
21 Correct 836 ms 896432 KB Output is correct
22 Runtime error 936 ms 1048576 KB Execution killed with signal 9
23 Correct 1068 ms 909364 KB Output is correct
24 Correct 901 ms 947768 KB Output is correct
25 Runtime error 1187 ms 1048576 KB Execution killed with signal 9
26 Correct 1234 ms 832372 KB Output is correct
27 Correct 1443 ms 847484 KB Output is correct
28 Execution timed out 2086 ms 890740 KB Time limit exceeded
29 Execution timed out 2139 ms 880400 KB Time limit exceeded
30 Correct 1964 ms 868284 KB Output is correct
31 Execution timed out 2071 ms 994496 KB Time limit exceeded
32 Correct 1349 ms 859724 KB Output is correct