Submission #1211116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211116		rkgena	Mecho (IOI09_mecho)	C++20	84 / 100	255 ms	30732 KiB

mecho

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#define lli long long int
#define pb push_back
#define all(x) x.begin(),x.end()
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repp(i,a,b) for(int i=a;i>=b;i--)
#define vi vector<lli>
#define vvi vector<vi>
#define vpi vector<pair<lli,lli>>
#define pi pair<lli,lli>
#define msi multiset<lli>
#define mspi multiset<pair<lli,lli>>
#define mii map<lli,lli>
#define mpi map<pair<lli,lli>,lli>
#define si set<lli>
#define spi set<pair<lli,lli>>
#define qi queue<lli>
#define pqi priority_queue<lli>
#define pqimin priority_queue<lli,vi,greater<lli>>
#define geti(n) lli n; cin>>n;
#define get2i(n,m) lli n,m; cin>>n>>m;
#define get3i(n,m,k) lli n,m,k; cin>>n>>m>>k;
#define getvi(v,n) vi v(n); for(lli i=0;i<n;i++) cin>>v[i];
#define getvvi(v,n,m) vvi v(n,vi(m)); for(lli i=0;i<n;i++) for(lli j=0;j<m;j++) cin>>v[i][j];
#define getvpi(v,n) vpi v(n); for(lli i=0;i<n;i++) cin>>v[i].first>>v[i].second;
#define getpi (p) pi p; cin>>p.first>>p.second;
#define getmii(m,n) mii m; for(lli i=0;i<n;i++) { lli a,b; cin>>a>>b; m[a]=b; }
#define getstr(s) string s; cin>>s;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T1, class T2> using ordered_map = tree<T1, T2, less<T1>, rb_tree_tag, tree_order_statistics_node_update>;
void print(lli n) { cout << n << "\n"; }
void print(lli n, lli m) { cout << n << " " << m << "\n"; }
void print(lli n, lli m, lli k) { cout << n << " " << m << " " << k << "\n"; }
void print(vi v) { for (auto i : v) cout << i << " "; cout << "\n"; }
void print(vvi v) { for (auto i : v) { for (auto j : i) cout << ((j>=INT_MAX)?-1:j) << " "; cout << "\n"; } }
void print(string s) { cout << s << "\n"; }

const lli MOD = 1e9 + 7;

struct mi {
    int v;
    explicit operator int() const { return v; }
    mi() { v = 0; }
    mi(long long _v) : v(_v % MOD) { v += (v < 0) * MOD; }
};
mi &operator+=(mi &a, mi b) {
    if ((a.v += b.v) >= MOD) a.v -= MOD;
    return a;
}
mi &operator-=(mi &a, mi b) {
    if ((a.v -= b.v) < 0) a.v += MOD;
    return a;
}
mi operator+(mi a, mi b) { return a += b; }
mi operator-(mi a, mi b) { return a -= b; }
mi operator*(mi a, mi b) { return mi((long long)a.v * b.v); }
mi &operator*=(mi &a, mi b) { return a = a * b; }
mi pow(mi a, long long p) {
    assert(p >= 0);
    return p == 0 ? 1 : pow(a * a, p / 2) * (p & 1 ? a : 1);
}
mi inv(mi a) {
    assert(a.v != 0);
    return pow(a, MOD - 2);
}
mi operator/(mi a, mi b) { return a * inv(b); }

struct manacher{
    vector<int> p;

    void run_manacher(string s){
        int n = s.size();
        p.assign(n,1);
        int l = 1, r = 1;
        rep(i,1,n-1){
            p[i] = max(0, min(p[l+r-i], r-i));
            while(i+p[i] < n && i-p[i] >= 0 && s[i+p[i]] == s[i-p[i]]){
                p[i]++;
            }
            if(i+p[i]>r){
                l = i-p[i];
                r = i+p[i];
            }
        }
    }
    void build(string s){
        string t;
        for(auto v: s){
            t += "#";
            t += v;
        }
        run_manacher(t+"#");
    }

    int getlongest_palindrome(int centre, bool odd){
        int pos = 2*centre+1+(!odd);
        return p[pos]-1;
    }

    bool checkpalindrome(int l, int r){
        if((r-l+1) <= getlongest_palindrome((l+r)/2, (r-l+1)%2)){
            return true;
        }
        return false;
    }
};



vi complete_subset_graphs(vi adj){ 
    // adj[i] = 1 << j if i is connected to j
    // n<=20
    lli n = adj.size();
    vi dp(1ll<<n,0);
    rep(mask,0,(1<<n)-1){
        bool complete = true;
        rep(i,0,n-1){
            if((mask & (1ll<<i))){
                if(((adj[i] | (1ll<<i))&mask) != mask){
                    complete = false;
                    break;
                }
            }
        }
        if(complete) dp[mask] = 1;
    }
    return dp;
}

vi subsets_of_mask(lli mask){
    vi subsets;
    for(lli submask = mask; submask != 0; submask = (submask-1)&mask){
        //lli subset = mask^submask;
        // subset is a subset of mask
        // {submask} = {mask} - {subset}
        // tc 3^N
        subsets.pb(submask);
    }
    return subsets;
}

vpi prm_fact(lli a) {
    vpi res;
    for (lli i = 2; i * i <= a; ++i) {
        if (a % i == 0) {
            int cnt = 0;
            while (a % i == 0) {
                a /= i;
                cnt++;
            }
            res.pb({i, cnt});
        }
    }
    if (a > 1) res.pb({a, 1});
    return res;
}

void solve() {
    lli n,s;
    cin>>n>>s;

    vvi grid(n,vi(n,0));
    pi start, end;
    queue<pi> hives;
    queue<pi> q;
    vvi mdist(n,vi(n,INT_MAX));
    vvi hdist(n,vi(n,INT_MAX));
    vi dx = {0, 0, 1, -1};
    vi dy = {1, -1, 0, 0};

    rep(i,0,n-1) {
        rep(j,0,n-1) {
            char c;
            cin>>c;
            if(c=='T')grid[i][j] = 0;
            if(c=='G')grid[i][j] = 1;
            if(c=='M'){
                grid[i][j] = 1;
                start = {i,j};
                q.push(start);
                mdist[i][j] = 0;
            }
            if(c=='D'){
                grid[i][j] = -1;
                end = {i,j};
            }
            if(c=='H'){
                grid[i][j] = 0;
                hives.push({i,j});
                hdist[i][j] = 0;
            }
        }
    }

    while(!q.empty()){
        pi f = q.front();
        q.pop();
        lli x = f.first, y = f.second;
        rep(i,0,3){
            lli nx = x + dx[i], ny = y + dy[i];
            if(nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] != 0 && mdist[nx][ny] > mdist[x][y] + 1){
                mdist[nx][ny] = mdist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }

    while(!hives.empty()){
        pi f = hives.front();
        hives.pop();
        lli x = f.first, y = f.second;
        rep(i,0,3){
            lli nx = x + dx[i], ny = y + dy[i];
            if(nx >= 0 && nx < n && ny >= 0 && ny < n && (grid[nx][ny] == 1) && hdist[nx][ny] > hdist[x][y] + s){
                hdist[nx][ny] = hdist[x][y] + s;
                hives.push({nx, ny});
            }
        }
    }

    vector<vpi> ngrid(n, vpi(n, {0,INT_MAX}));
    rep(i,0,n-1){
        rep(j,0,n-1){
            if(grid[i][j] == 1){
                if(mdist[i][j] < (hdist[i][j])){
                    ngrid[i][j] = {1, hdist[i][j]-1};
                }
                else{
                    ngrid[i][j] = {0, INT_MAX};
                }
            }
        }
    }
    ngrid[end.first][end.second] = {1, INT_MAX};

    lli lo = 0;
    lli hi = INT_MAX;
    lli ans = -1;
    while(lo <= hi){
        lli mid = lo + (hi - lo) / 2;
        
        bool pos = false;
        queue<pi> q;
        vvi dist(n, vi(n, INT_MAX));
        q.push(start);
        dist[start.first][start.second] = mid*s;
        while(!q.empty()){
            pi f = q.front();
            q.pop();
            lli x = f.first, y = f.second;
            if(x == end.first && y == end.second){
                pos = true;
                break;
            }
            rep(i,0,3){
                lli nx = x + dx[i], ny = y + dy[i];
                if(nx >= 0 && nx < n && ny >= 0 && ny < n && ngrid[nx][ny].first == 1 && dist[nx][ny] > dist[x][y] + 1 && dist[x][y]+1 <= ngrid[nx][ny].second){
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
        if(pos){
            ans= max(ans,mid);
            lo = mid+1;
        }
        else{
            hi = mid-1;
        }
    }
    // rep(i,0,n-1){
    //     rep(j,0,n-1){
    //         cout<<ngrid[i][j].first<<" ";
    //     }
    //     cout<<"\n";
    // }
    // cout<<"\n\n";
    // rep(i,0,n-1){
    //     rep(j,0,n-1){
    //         cout<<(ngrid[i][j].second >= INT_MAX ? -1 : ngrid[i][j].second)<<" ";
    //     }
    //     cout<<"\n";
    // }
    // print("\n\n\n");
    // print(mdist);
    // print("\n\n\n");
    // print(hdist);
    // print("\n\n\n");
    cout<<ans<<"\n";
}
 
signed main() {
    IOS int t=1;
    //cin>>t;
    while(t--)
        solve();
    return 0;
}

• Subtask 1: 84 / 100