oj.uz

Submission #369573

# Submission time Handle Problem Language Result Execution time Memory
369573 2021-02-21T22:31:10 Z ijxjdjd Tracks in the Snow (BOI13_tracks) C++14
89.0625 / 100
 2000 ms 530860 KB 
#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(pair<uint64_t, uint64_t> x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x.first + FIXED_RANDOM) + splitmix64(x.second+FIXED_RANDOM);
    }
};
const int MAXN = 4000 + 5;
int par[MAXN*MAXN];
int board[MAXN*MAXN];
int seen[MAXN*MAXN];
int rk[MAXN*MAXN];
int sz = 0;
int dist[MAXN*MAXN];
unordered_set<pair<int, int>, custom_hash> already;
vector<int> adj[int(4e6)];
int find(int x) {
    if (par[x] == x) {
        return x;
    }
    return par[x] = find(par[x]);
}
void merge(int x, int y) {
    if (board[x] == board[y]) {
        int pX = find(x);
        int pY = find(y);
        if (rk[pX] < rk[pY]) {
            swap(pX, pY);
        }
        par[pY] = pX;
    }
}
void addEdge(int x, int y) {
    if (board[x] != board[y] && board[x] >= 0 && board[y] >= 0) {
        pair<int, int> pos = {board[x], board[y]};
        if (board[x] > board[y]) {
            swap(pos.first, pos.second);
        }
        if (!already.count(pos)) {
            already.insert(pos);
            adj[board[x]].push_back(board[y]);
            adj[board[y]].push_back(board[x]);
        }
    }
}
int H, W;
int conv(int i, int j) {
    return i*W + j;
}
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	cin >> H >> W;
	W += 2;
	H += 2;
	FR(i, MAXN*MAXN) {
        par[i] = i;
        rk[i] = 1;
        board[i] = '.';
	}
	FR(i, H-2) {
        FR(j, W-2) {
            char c;
            cin >> c;
            board[conv(i+1, j+1)] = c;
        }
	}
	for (int i = 1; i < H-1; i++) {
        for (int j = 1; j < W-1; j++) {
            merge(conv(i, j), conv(i+1, j));
//            merge(conv(i, j), conv(i-1, j));
            merge(conv(i, j), conv(i, j+1));
//            merge(conv(i, j), conv(i, j-1));
        }
	}
	fill(all(seen), -1);
	FR(i, MAXN*MAXN) {
        if (board[i] != '.' && par[i] == i) {
            seen[i] = sz++;
        }
	}
	FR(i, MAXN*MAXN) {
        board[i] = seen[find(i)];
	}
	for (int i = 1; i < H-1; i++) {
        for (int j = 1; j < W-1; j++) {
            addEdge(conv(i, j), conv(i+1, j));
//            addEdge(conv(i, j), conv(i-1, j));
            addEdge(conv(i, j), conv(i, j+1));
//            addEdge(conv(i, j), conv(i, j-1));
        }
	}
	fill(all(dist), MAXN*MAXN);
    deque<int> p;
    p.push_back(board[conv(1, 1)]);
    dist[board[conv(1, 1)]] = 0;
    int mx = 0;
    while (p.size() > 0) {
        int next = p.front();
        p.pop_front();
        for (int e : adj[next]) {
            if (dist[e] > dist[next] + 1) {
                dist[e] = dist[next]+1;
                p.push_back(e);
                mx = max(dist[e], mx);
            }
        }
    }
    cout << mx + 1 << '\n';
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 411640 KB Output is correct
2 Correct 295 ms 408220 KB Output is correct
3 Correct 304 ms 408172 KB Output is correct
4 Correct 308 ms 408428 KB Output is correct
5 Correct 325 ms 408812 KB Output is correct
6 Correct 298 ms 408172 KB Output is correct
7 Correct 296 ms 408172 KB Output is correct
8 Correct 331 ms 408300 KB Output is correct
9 Correct 295 ms 408300 KB Output is correct
10 Correct 320 ms 408916 KB Output is correct
11 Correct 300 ms 408428 KB Output is correct
12 Correct 330 ms 409452 KB Output is correct
13 Correct 305 ms 408812 KB Output is correct
14 Correct 306 ms 408940 KB Output is correct
15 Correct 344 ms 411512 KB Output is correct
16 Correct 346 ms 411640 KB Output is correct
17 Correct 346 ms 411256 KB Output is correct
18 Correct 308 ms 408428 KB Output is correct

Subtask #2
59.0625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 408520 KB Output is correct
2 Correct 558 ms 423808 KB Output is correct
3 Execution timed out 2116 ms 455812 KB Time limit exceeded
4 Correct 749 ms 428892 KB Output is correct
5 Execution timed out 2117 ms 530860 KB Time limit exceeded
6 Correct 1918 ms 454392 KB Output is correct
7 Correct 309 ms 408812 KB Output is correct
8 Correct 299 ms 408684 KB Output is correct
9 Correct 336 ms 408780 KB Output is correct
10 Correct 300 ms 408352 KB Output is correct
11 Correct 300 ms 408300 KB Output is correct
12 Correct 297 ms 409068 KB Output is correct
13 Correct 558 ms 423832 KB Output is correct
14 Correct 432 ms 418356 KB Output is correct
15 Correct 448 ms 419124 KB Output is correct
16 Correct 411 ms 415888 KB Output is correct
17 Correct 1041 ms 451952 KB Output is correct
18 Correct 1014 ms 451036 KB Output is correct
19 Correct 751 ms 429036 KB Output is correct
20 Correct 767 ms 434104 KB Output is correct
21 Correct 1519 ms 473524 KB Output is correct
22 Execution timed out 2081 ms 530776 KB Time limit exceeded
23 Correct 1848 ms 493456 KB Output is correct
24 Correct 1869 ms 518812 KB Output is correct
25 Execution timed out 2082 ms 452524 KB Time limit exceeded
26 Correct 904 ms 408164 KB Output is correct
27 Correct 1200 ms 409588 KB Output is correct
28 Correct 1963 ms 454484 KB Output is correct
29 Correct 1676 ms 434864 KB Output is correct
30 Correct 1491 ms 426360 KB Output is correct
31 Execution timed out 2110 ms 427604 KB Time limit exceeded
32 Correct 1271 ms 419124 KB Output is correct