oj.uz

Submission #59162

# Submission time Handle Problem Language Result Execution time Memory
59162 2018-07-20T21:31:13 Z Benq Tracks in the Snow (BOI13_tracks) C++14
95.625 / 100
 2000 ms 828132 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 4000*4000;


template<int SZ> struct DSU {
    int par[SZ], sz[SZ];
    DSU() {
        F0R(i,SZ) par[i] = i, sz[i] = 1;
    }
    
    int get(int x) { // path compression
    	if (par[x] != x) par[x] = get(par[x]);
    	return par[x];
    }
    
    bool unite(int x, int y) { // union-by-rank
    	x = get(x), y = get(y);
    	if (x == y) return 0;
    	if (sz[x] < sz[y]) swap(x,y);
    	sz[x] += sz[y], par[y] = x;
    	return 1;
    }
};

DSU<MX> D;
int H,W, dist[MX];
string g[4000];
vi adj[MX];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> H >> W;
    F0R(i,H) cin >> g[i];
    F0R(i,H) F0R(j,W-1) if (g[i][j] == g[i][j+1]) D.unite(W*i+j,W*i+j+1);
    F0R(i,H-1) F0R(j,W) if (g[i][j] == g[i+1][j]) D.unite(W*i+j,W*(i+1)+j);
    F0R(i,H) F0R(j,W-1) if (g[i][j] != g[i][j+1]) {
        if (g[i][j] == '.' || g[i][j+1] == '.') continue;
        int a = D.get(W*i+j), b = D.get(W*i+j+1);
        adj[a].pb(b), adj[b].pb(a);
    }
    
    F0R(i,H-1) F0R(j,W) if (g[i][j] != g[i+1][j]) {
        if (g[i][j] == '.' || g[i+1][j] == '.') continue;
        int a = D.get(W*i+j), b = D.get(W*(i+1)+j);
        adj[a].pb(b), adj[b].pb(a);
    }
    
    F0R(i,MX) dist[i] = MOD;
    int x = D.get(0); dist[x] = 0;
    queue<int> q; q.push(x);
    
    int ans = 0;
    while (sz(q)) {
        int x = q.front(); q.pop();
        for (int i: adj[x]) if (dist[i] == MOD) {
            dist[i] = dist[x]+1;
            ans = max(ans,dist[i]);
            q.push(i);
        }
    }
    cout << ans+1;
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 969 ms 567552 KB Output is correct
2 Correct 488 ms 567552 KB Output is correct
3 Correct 535 ms 567552 KB Output is correct
4 Correct 516 ms 567552 KB Output is correct
5 Correct 561 ms 567552 KB Output is correct
6 Correct 479 ms 567552 KB Output is correct
7 Correct 543 ms 567552 KB Output is correct
8 Correct 489 ms 567552 KB Output is correct
9 Correct 515 ms 567552 KB Output is correct
10 Correct 513 ms 567552 KB Output is correct
11 Correct 521 ms 567552 KB Output is correct
12 Correct 537 ms 567552 KB Output is correct
13 Correct 545 ms 567552 KB Output is correct
14 Correct 536 ms 567552 KB Output is correct
15 Correct 499 ms 568232 KB Output is correct
16 Correct 498 ms 569220 KB Output is correct
17 Correct 602 ms 569220 KB Output is correct
18 Correct 567 ms 569220 KB Output is correct

Subtask #2
65.625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 569220 KB Output is correct
2 Correct 678 ms 578708 KB Output is correct
3 Correct 1421 ms 656120 KB Output is correct
4 Correct 757 ms 656120 KB Output is correct
5 Correct 1456 ms 742456 KB Output is correct
6 Correct 1804 ms 742456 KB Output is correct
7 Correct 519 ms 742456 KB Output is correct
8 Correct 532 ms 742456 KB Output is correct
9 Correct 523 ms 742456 KB Output is correct
10 Correct 512 ms 742456 KB Output is correct
11 Correct 477 ms 742456 KB Output is correct
12 Correct 499 ms 742456 KB Output is correct
13 Correct 723 ms 742456 KB Output is correct
14 Correct 661 ms 742456 KB Output is correct
15 Correct 611 ms 742456 KB Output is correct
16 Correct 611 ms 742456 KB Output is correct
17 Correct 1008 ms 742456 KB Output is correct
18 Correct 933 ms 742456 KB Output is correct
19 Correct 752 ms 742456 KB Output is correct
20 Correct 670 ms 742456 KB Output is correct
21 Correct 1002 ms 742456 KB Output is correct
22 Correct 1563 ms 789108 KB Output is correct
23 Correct 1291 ms 789108 KB Output is correct
24 Correct 940 ms 789108 KB Output is correct
25 Execution timed out 2076 ms 789108 KB Time limit exceeded
26 Correct 811 ms 789108 KB Output is correct
27 Correct 948 ms 789108 KB Output is correct
28 Correct 1601 ms 789108 KB Output is correct
29 Correct 1482 ms 792912 KB Output is correct
30 Correct 1205 ms 793868 KB Output is correct
31 Execution timed out 2100 ms 828132 KB Time limit exceeded
32 Correct 959 ms 828132 KB Output is correct