답안 #73135 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
73135	2018-08-28T00:20:24 Z	Benq	Wall (CEOI14_wall)	C++14	100 / 100	578 ms	84472 KB

wall

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
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 pqg = priority_queue<T,vector<T>,greater<T>>;
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 = 401;

template<class T> T poll(pqg<T>& x) {
    T y = x.top(); x.pop();
    return y;
}

pi operator+(const pi& l, const pi& r) { return {l.f+r.f,l.s+r.s}; }

// we want to generate a border for the villages 
int N,M, h[MX][MX], v[MX][MX],g[MX][MX];
ll dist[MX][MX];
pi pre[MX][MX];
set<array<int,3>> banEdge;

void input() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    F0R(i,N) F0R(j,M) cin >> g[i][j];
    F0R(i,N) F0R(j,M+1) cin >> v[i][j];
    F0R(i,N+1) F0R(j,M) cin >> h[i][j];
}

pi dir[4] = {{1,0},{0,1},{-1,0},{0,-1}};

bool valid(pi x) {
    return 0 <= x.f && x.f <= N && 0 <= x.s && x.s <= M;
}

int getWei(pi x, int d) {
    if (d == 0) return v[x.f][x.s];
    if (d == 1) return h[x.f][x.s];
    if (d == 2) return v[x.f-1][x.s];
    return h[x.f][x.s-1];
}

bool done[MX][MX];

void insBan(pi a, pi b) {
    if (a > b) swap(a,b);
    if (a.f+1 == b.f) banEdge.insert({0,a.f,a.s});
    else banEdge.insert({1,a.f,a.s});
}

void tri(int i, int j) {
    if (done[i][j]) return;
    done[i][j] = 1;
    pi x = pre[i][j];
    insBan(x,{i,j});
    tri(x.f,x.s);
}

void genShortest() {
    F0R(i,N+1) F0R(j,M+1) dist[i][j] = INF;
    dist[0][0] = 0; 
    pqg<pair<ll,pi>> p; p.push({0,{0,0}});
    while (sz(p)) {
        auto a = poll(p); if (a.f > dist[a.s.f][a.s.s]) continue;
        F0R(i,4) {
            pi A = a.s+dir[i];
            if (!valid(A)) continue;
            ll d = a.f+getWei(a.s,i);
            if (d < dist[A.f][A.s]) {
                pre[A.f][A.s] = a.s;
                p.push({dist[A.f][A.s] = d,A});
            }
        }
    }
    F0R(i,N) F0R(j,M) if (g[i][j]) {
        insBan({i,j},{i,j+1});
        insBan({i,j+1},{i+1,j+1});
        insBan({i+1,j},{i+1,j+1});
        insBan({i,j},{i+1,j});
        tri(i,j);
    }
    banEdge.insert({0,-1,0});
    banEdge.insert({1,0,-1});
}

ll ans[MX*MX*4];
vpi adj[MX*MX*4];

int hsh(int a, int b, int c) {
    return 4*((M+1)*a+b)+c;
}

void addEdge(int a, int b, int c) {
    adj[a].pb({b,c}), adj[b].pb({a,c});
}

void genAdj() {
    /*for (auto a: banEdge) {
        cout << a[0] << " " << a[1] << " " << a[2] << "\n";
    }*/
    F0R(i,N) F0R(j,M+1) {
        addEdge(hsh(i,j,2),hsh(i+1,j,1),v[i][j]);
        addEdge(hsh(i,j,3),hsh(i+1,j,0),v[i][j]);
    }
    F0R(i,N+1) F0R(j,M) {
        addEdge(hsh(i,j,0),hsh(i,j+1,1),h[i][j]);
        addEdge(hsh(i,j,3),hsh(i,j+1,2),h[i][j]);
    }
    F0R(i,N+1) F0R(j,M+1) {
        if (!banEdge.count({0,i,j})) addEdge(hsh(i,j,2),hsh(i,j,3),0);
        if (!banEdge.count({0,i-1,j})) addEdge(hsh(i,j,0),hsh(i,j,1),0);
        if (!banEdge.count({1,i,j})) addEdge(hsh(i,j,0),hsh(i,j,3),0);
        if (!banEdge.count({1,i,j-1})) addEdge(hsh(i,j,1),hsh(i,j,2),0);
    }
}

void solve() {
    genAdj();
    F0R(i,MX*MX*4) ans[i] = INF;
    pqg<pl> p; p.push({ans[2] = 0,2});
    while (sz(p)) {
        auto a = poll(p); if (a.f > ans[a.s]) continue;
        for (auto b: adj[a.s]) if (a.f+b.s < ans[b.f]) 
            p.push({ans[b.f] = a.f+b.s,b.f});
    }
}

int main() {
    input();
    genShortest();
    solve();
    cout << ans[0];
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
* if you have no idea just guess the appropriate well-known algo instead of doing nothing :/
*/

Subtask #1
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	20600 KB	Output is correct
2	Correct	22 ms	20720 KB	Output is correct
3	Correct	23 ms	20808 KB	Output is correct
4	Correct	23 ms	20864 KB	Output is correct
5	Correct	22 ms	20872 KB	Output is correct
6	Correct	25 ms	21312 KB	Output is correct
7	Correct	24 ms	21384 KB	Output is correct
8	Correct	28 ms	21452 KB	Output is correct
9	Correct	21 ms	21592 KB	Output is correct
10	Correct	24 ms	21592 KB	Output is correct
11	Correct	26 ms	21592 KB	Output is correct
12	Correct	28 ms	21712 KB	Output is correct
13	Correct	27 ms	21752 KB	Output is correct
14	Correct	27 ms	21768 KB	Output is correct
15	Correct	22 ms	21768 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	21788 KB	Output is correct
2	Correct	22 ms	21932 KB	Output is correct
3	Correct	26 ms	21964 KB	Output is correct
4	Correct	23 ms	22004 KB	Output is correct
5	Correct	23 ms	22024 KB	Output is correct
6	Correct	22 ms	22044 KB	Output is correct
7	Correct	25 ms	22064 KB	Output is correct
8	Correct	24 ms	22064 KB	Output is correct
9	Correct	26 ms	22064 KB	Output is correct
10	Correct	23 ms	22244 KB	Output is correct
11	Correct	23 ms	22244 KB	Output is correct
12	Correct	26 ms	22244 KB	Output is correct
13	Correct	28 ms	22244 KB	Output is correct
14	Correct	23 ms	22244 KB	Output is correct
15	Correct	22 ms	22244 KB	Output is correct
16	Correct	27 ms	22244 KB	Output is correct
17	Correct	27 ms	22260 KB	Output is correct
18	Correct	27 ms	22280 KB	Output is correct

Subtask #3
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	164 ms	32436 KB	Output is correct
2	Correct	131 ms	32436 KB	Output is correct
3	Correct	123 ms	32436 KB	Output is correct
4	Correct	143 ms	33384 KB	Output is correct
5	Correct	239 ms	47252 KB	Output is correct
6	Correct	145 ms	47252 KB	Output is correct
7	Correct	313 ms	48880 KB	Output is correct
8	Correct	274 ms	48880 KB	Output is correct
9	Correct	264 ms	48880 KB	Output is correct
10	Correct	353 ms	51928 KB	Output is correct
11	Correct	354 ms	55792 KB	Output is correct
12	Correct	113 ms	55792 KB	Output is correct
13	Correct	311 ms	55792 KB	Output is correct
14	Correct	456 ms	70804 KB	Output is correct
15	Correct	473 ms	70804 KB	Output is correct
16	Correct	526 ms	71920 KB	Output is correct
17	Correct	530 ms	77588 KB	Output is correct
18	Correct	578 ms	84472 KB	Output is correct
19	Correct	570 ms	84472 KB	Output is correct
20	Correct	496 ms	84472 KB	Output is correct

답안 #73135

Compilation message

Subtask #1 30.0 / 30.0

Subtask #2 30.0 / 30.0

Subtask #3 40.0 / 40.0

Subtask #1
30.0 / 30.0

Subtask #2
30.0 / 30.0

Subtask #3
40.0 / 40.0