QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#846761#8236. Snake MoveRed0TL 1ms3688kbC++2018.9kb2025-01-07 13:36:292025-01-07 13:36:30

Judging History

你现在查看的是最新测评结果

  • [2025-01-07 13:36:30]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3688kb
  • [2025-01-07 13:36:29]
  • 提交

answer

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

//Debug Template:
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long

//Random Number Generator:
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x^(x>>30))*0xbf58476d1ce4e5b9;
        x = (x^(x>>27))*0x94d049bb133111eb;
        return x^(x>>31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = rng();
        return splitmix64(x+FIXED_RANDOM);
    }
};

//Custom Data Structures:
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using safe_set = unordered_set<T, custom_hash>;
template<typename T, typename V> using safe_map = unordered_map<T, V, custom_hash>;
template<typename T> using vc = vector<T>; template<typename T> using vvc = vc<vc<T>>; template<typename T> using vvvc = vc<vvc<T>>;
template<typename T, int V> using ar = array<T, V>;
template<typename T, typename V> using pr = pair<T, V>;
using vi = vc<int>; using vvi = vvc<int>; using vvvi = vvvc<int>;
using pii = pr<int, int>;

//Macros:
#define repl(i, a, b) for(int i = a; i < b; ++i)
#define repe(i, a, b) for(int i = a; i <= b; ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pow(b, p) (int)pow(b, p)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define lsb(x) (int)__builtin_ctzll(x)
#define msb(x) (int)(63-__builtin_clzll(x))
#define yes cout << "YES\n"
#define no cout << "NO\n"

#define readall(x) trav(it, x) cin >> it;
#define printall(x) trav(it, x) cout << it << " ";
#define getmin(x) *min_element(all(x))
#define getmax(x) *max_element(all(x))

//c Problem Info:
const int MAX_N = 200005;
const int MAX_M = 200005;
const int INF = (int)1000000000000000000;
const int MOD = pow(2, 64);

//ModInt:
struct mint {
    int v;
    mint() :v(0) {}
    mint(int x) { v = x >= 0 ? x % MOD : x + (-x + MOD - 1) / MOD * MOD; }
    friend ostream& operator<<(ostream& stream, const mint& x) { stream << x.v; return stream; }
    friend istream& operator>>(istream& stream, mint& val) { int x; stream >> x; val.v = x >= 0 ? x % MOD : x + (-x + MOD - 1) / MOD * MOD; return stream; }
    operator int()const { return v; }
    mint& operator++() { if (++v >= MOD)v -= MOD; return *this; }
    mint& operator--() { if (--v < 0)v += MOD; return *this; }
    mint& operator+=(const mint& y) { v = v + y.v - ((v + y.v) >= MOD ? MOD : 0); return *this; }mint operator+(const mint& y)const { mint x = *this; return x += y; }
    mint& operator-=(const mint& y) { v = v - y.v + (v - y.v < 0 ? MOD : 0); return *this; }mint operator-(const mint& y)const { mint x = *this; return x -= y; }
    mint& operator*=(const mint& y) { v = ((long long)v * y.v) % MOD; return *this; }mint operator*(const mint& y)const { mint x = *this; return x *= y; }
    mint& operator%=(const mint& y) { if (y.v)v %= y.v; return *this; }mint operator%(const mint& y)const { mint x = *this; return x %= y; }
    mint& operator/=(const mint& y) { return *this *= ModInverse(y.v); }mint operator/(const mint& y)const { return *this * ModInverse(y.v); }
    mint& operator^=(const mint& y) { *this = this->Pow(y); return *this; }mint Pow(int y)const { mint r = 1, x = v; for (y <<= 1; y >>= 1; x = x * x)if (y & 1)r = r * x; return r; }
    mint ModInverse(int a)const { return mint(a) ^ (MOD - 2); }
    friend mint operator+(const mint& a, long long b) { return a + mint(b); }friend mint operator+(long long a, const mint& b) { return mint(a) + b; }friend mint operator+(const mint& a, int32_t b) { return a + mint(b); }friend mint operator+(int32_t a, const mint& b) { return mint(a) + b; }
    friend mint operator-(const mint& a, long long b) { return a - mint(b); }friend mint operator-(long long a, const mint& b) { return mint(a) - b; }friend mint operator-(const mint& a, int32_t b) { return a - mint(b); }friend mint operator-(int32_t a, const mint& b) { return mint(a) - b; }
    friend mint operator*(const mint& a, long long b) { return a * mint(b); }friend mint operator*(long long a, const mint& b) { return mint(a) * b; }friend mint operator*(const mint& a, int32_t b) { return a * mint(b); }friend mint operator*(int32_t a, const mint& b) { return mint(a) * b; }
    friend mint operator/(const mint& a, int32_t b) { return a / mint(b); }friend mint operator/(int32_t a, const mint& b) { return mint(a) / b; }friend mint operator/(const mint& a, long long b) { return a / mint(b); }friend mint operator/(long long a, const mint& b) { return mint(a) / b; }
    friend mint operator^(const mint& a, long long b) { return a.Pow(b); }friend mint operator^(long long a, const mint& b) { return mint(a).Pow(b); }friend mint operator^(const mint& a, int32_t b) { return a.Pow(b); }friend mint operator^(int32_t a, const mint& b) { return mint(a).Pow(b); }friend mint operator^(const mint& a, const mint& b) { return a.Pow(b); }
    bool operator==(const mint& y)const { return v == y.v; }bool operator==(int32_t y)const { return v == y; }bool operator==(long long y)const { return v == y; }
    bool operator!=(const mint& y)const { return v != y.v; }bool operator!=(int32_t y)const { return v != y; }bool operator!=(long long y)const { return v != y; }
    bool operator>(const mint& y)const { return v > y.v; }bool operator>(int32_t y)const { return v > y; }bool operator>(long long y)const { return v > y; }
    bool operator>=(const mint& y)const { return v >= y.v; }bool operator>=(int32_t y)const { return v >= y; }bool operator>=(long long y)const { return v >= y; }
    bool operator<(const mint& y)const { return v < y.v; }bool operator<(int32_t y)const { return v < y; }bool operator<(long long y)const { return v < y; }
    bool operator<=(const mint& y)const { return v <= y.v; }bool operator<=(int32_t y)const { return v <= y; }bool operator<=(long long y)const { return v <= y; }
};

//Special Output:
//Interactive
struct Interactive {
    int query(int x, int y) {
        cout << "? " << x << " " << y << "\n";
        cout.flush();

        int res;
        cin >> res;

        return res;
    }

    void answer(int a) {
        cout << "! " << a << "\n";
        cout.flush();
    }

    void answer(vi a) {
        cout << "! ";
        trav(it, a) cout << it << " ";
        cout.flush();
    }
} interactive;

//Output
void output(int a, int b, char op) {
    cout << a << " " << op << " " << b << "\n";
}

//Math:
//Number Theory
//Modular Powers
int modpow(int b, int p, int mod = MOD) {
    int res = 1;
    while(p) {
        if(p&1) res = (res*b)%mod;
        b = (b*b)%mod;
        p >>= 1;
    }
    return res;
}

//Fermat's Little Thoerem for Modular Inverse
int fermats_little_thoerem(int b, int mod = MOD) {
    return modpow(b, mod-2);
}

//Extended Euclidean
int extended_euclidean(int a, int b, int &inv, int &rem) {
    if(b == 0) {
        inv = 1;
        rem = 0;
        return a;
    }

    int x1, y1;
    int d = extended_euclidean(b, a%b, x1, y1);
    inv = y1;
    rem = x1-y1*(a/b);
    return d;
}

//Bezout's Theorem for Relatively Prime Numbers
int bezouts_theorem_rp(int a, int b) {
    int inv, rem;
    int cgcd = extended_euclidean(a, b, inv, rem);
    if(cgcd != 1) {
        return -1;
    } else {
        inv = (inv%b+b)%b;
        return inv;
    }
}

//Binomial Coefficients
int nCr(int n, int r, vi &facts, int mod = MOD) {
    return (facts[n]*fermats_little_thoerem((facts[r]*facts[n-r])%mod))%mod;
}

//Binary Multiplication
int binmul(int a, int b) {
    int l = ceil(log2(b));

    vi table(++l, 0);
    table[0] = a;
    repl(i, 1, l) {
        table[i] = table[i-1]*2;
    }

    //Most significant bit 0-indexed
    int msb = msb(b);
    int res = table[msb];
    for(int i = msb-1; ~i; --i) {
        if((b>>i)&1) {
            res = res+table[i];
        }
    }

    return res;
}

vi prime_factors(int n) {
    vi res;
    while(!(n%2)) {
        res.pb(2);
        n /= 2;
    }

    for(int i = 3; i <= sqrt(n); i += 2) {
        while(!(n%i)) {
            res.pb(i);
            n /= i;
        }
        if(n == 1) break;
    }

    if(n > 2) res.pb(n);

    return res;
}

//Geometry
//Distance Formula
double distanceab(double x1, double y1, double x2, double y2) {
    return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}

//String Operations:
//Knuth-Morris-Pratt
struct Knuth_Morris_Pratt {
    int n;
    string s;
    vi pi;

    Knuth_Morris_Pratt(string _s) : s(_s) {
        init();
    }

    void init() {
        n = sz(s);
        pi.resize(n);
    }

    void compute() {
        int n = (int)s.length();
        repl(i, 1, n) {
            int j = pi[i-1];
            while(j > 0 && s[i] != s[j]) j = pi[j-1];
            if(s[i] == s[j]) ++j;
            pi[i] = j;
        }
    }
};

//Trees:
//Least Common Ancestor
struct LCA {
    int n, l, timer;
    vi tin, tout, visited, depth;
    vvc<int> up, qans;

    LCA(int _n) {
        init(n);
    }

    void init(int n) {
        this->n = n;
        tin.resize(n+1);
        tout.resize(n+1);
        l = ceil(log2(n));
        up.assign(n+1, vi(l+1));
        //qans.assign(n+1, vi(l+1, INF));
        visited.assign(n+1, 0);
        depth.resize(n+1);
    }

    void dfs_normal(int c, int p, vvi &adj) {
        tin[c] = ++timer;
        up[c][0] = p;

        repe(i, 1, l) {
            up[c][i] = up[up[c][i-1]][i-1];
        }

        trav(u, adj[c]) {
            if(u != p) {
                depth[u] = depth[c]+1;
                visited[u] = 1;
                dfs_normal(u, c, adj);
            }
        }

        tout[c] = ++timer;
    }

    void dfs_query(int c, int p, int w, vvc<pr<int, int>> &adj) {
        tin[c] = ++timer;
        up[c][0] = p;
        qans[c][0] = w;

        repe(i, 1, l) {
            up[c][i] = up[up[c][i-1]][i-1];
            qans[c][i] = min(qans[c][i-1], qans[up[c][i-1]][i-1]);
        }

        trav(u, adj[c]) {
            if(u.fir != p) {
                depth[u.fir] = depth[c]+1;
                visited[u.fir] = 1;
                dfs_query(u.fir, c, u.sec, adj);
            }
        }

        tout[c] = ++timer;
    }

    //is u ancestor of v?
    int isancestor(int u, int v) {
        return tin[u] <= tin[v] && tout[u] >= tout[v];
    }

    int lca_normal(int u, int v) {
        if(isancestor(u, v)) return u;
        if(isancestor(v, u)) return v;
        for (int i = l; ~i; --i) {
            if (!isancestor(up[u][i], v)) u = up[u][i];
        }
        return up[u][0];
    }

    int lca_query(int u, int v) {
        if(isancestor(u, v)) {
            int aans = INF;
            for(int i = l; i >= 0; --i) {
                if(depth[up[v][i]] >= depth[u]) {
                    aans = min(aans, qans[v][i]);
                    v = up[v][i];
                }
            }
            return aans;
        } else if(isancestor(v, u)) {
            int aans = INF;
            for(int i = l; i >= 0; --i) {
                if(depth[up[u][i]] >= depth[v]) {
                    aans = min(aans, qans[u][i]);
                    u = up[u][i];
                }
            }
            return aans;
        }
        int temp = u, aans = INF, bans = INF;
        for(int i = l; i >= 0; --i) {
            if(!isancestor(up[temp][i], v)) {
                aans = min(aans, qans[temp][i]);
                temp = up[temp][i];
            }
        }
        aans = min(aans, qans[temp][0]);
        for(int i = l; i >= 0; --i) {
            if(!isancestor(up[v][i], u)) {
                bans = min(bans, qans[v][i]);
                v = up[v][i];
            }
        }
        bans = min(bans, qans[v][0]);
        return min(aans, bans);
    }
};

//Important Data Structures
//Segment Tree
struct Segment_Tree {
    struct Node {
        int l, r;
        long long ans, lazy = 0;

        void leaf(long long val) {
            ans = val;
        }

        void pull(const Node &a, const Node &b) {
            ans = a.ans+b.ans;
        }

        void push(long long val) {
            lazy += val;
        }

        void apply() {
            ans += lazy;
            lazy = 0;
        }
    };

    int n;
    vector<int> a;
    vector<Node> st;

    Segment_Tree(int _n) : n(_n), a(n, INF), st(4*n) {
        build(1, 0, n-1);
    }

    Segment_Tree(const vector<int> &_a) : n((int) _a.size()), a(_a), st(4*n) {
        build(1, 0, n-1);
    }

    void build(int p, int l, int r) {
        st[p].l = l;
        st[p].r = r;
        if(l == r) {
            st[p].leaf(a[l]);
            return;
        }
        int m = (l+r)/2;
        build(2*p, l, m);
        build(2*p+1, m+1, r);
        st[p].pull(st[2*p], st[2*p+1]);
    }

    void push(int p) {
        if(st[p].lazy) {
            if(st[p].l != st[p].r) {
                st[2*p].push(st[p].lazy);
                st[2*p+1].push(st[p].lazy);
            }
            st[p].apply();
        }
    }

    Node query(int p, int i, int j) {
        push(p);
        if(st[p].l == i && st[p].r == j) return st[p];
        int m = (st[p].l+st[p].r)/2;
        if(j <= m) return query(2*p, i, j);
        else if (i > m) return query(2*p+1, i, j);
        Node ret, ls = query(2*p, i, m), rs = query(2*p+1, m+1, j);
        ret.pull(ls, rs);
        return ret;
    }

    long long query(int i, int j) {
        return query(1, i, j).ans;
    }

    void update(int p, int i, int j, long long val) {
        if(st[p].l == i && st[p].r == j) {
            st[p].push(val);
            push(p);
            return;
        }
        push(p);
        int m = (st[p].l + st[p].r) / 2;
        if(j <= m) {
            update(2*p, i, j, val);
            push(2*p+1);
        } else if(i > m) {
            push(2*p);
            update(2*p+1, i, j, val);
        } else {
            update(2*p, i, m, val);
            update(2*p+1, m+1, j, val);
        }
        st[p].pull(st[2*p], st[2*p+1]);
    }

    void update(int i, int j, long long val) {
        update(1, i, j, val);
    }

    void set(int p, int i, long long val) {
        if(st[p].l == st[p].r) {
            st[p].leaf(val);
            return;
        }
        push(2*p);
        push(2*p+1);
        int m = (st[p].l+st[p].r)/2;
        if(i <= m) set(2*p, i, val);
        else set(2*p+1, i, val);
        st[p].pull(st[2*p], st[2*p+1]);
    }

    void set(int i, long long val) {
        set(1, i, val);
    }
};

//Disjoint set Union
struct DSU {
    int n;
    vi parent, gsize;

    DSU(int _n) : n(_n) {
        init();
    }

    void init() {
        parent = vi(n+1);
        gsize = vi(n+1, 1);
        repe(i, 0, n) parent[i] = i;
    }

    int find(int u) {
        if(u != parent[u]) parent[u] = find(parent[u]);
        return parent[u];
    }

    int unite(int u, int v) {
        u = find(u);
        v = find(v);
        if(u != v) {
            if(gsize[u] < gsize[v]) swap(u, v);
            parent[v] = u;
            gsize[u] += gsize[v];
            return u;
        }
        return -1;
    }
};

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    //represents if some square is a snake and also represents distance+1 from head;
    map<pii, int> org_snake;
    int hx = 0, hy = 0, tx = 0, ty = 0;
    repe(i, 1, k) {
        int x, y;
        cin >> x >> y;

        if (i == 1) hx = x, hy = y;
        else if (i == k) tx = x, ty = y;
        org_snake[{x, y}] = i;
    }

    vvc<char> grid(n+1, vc<char>(m+1));
    repe(i, 1, n) {
        repe(j, 1, m) cin >> grid[i][j];
    }

    vvi dist(n+1, vi(m+1, INF));
    int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
    int mtime = n+m+k;
    vvc<ar<int, 3>> process(mtime+1);
    process[0].pb({0, hx, hy});
    repe(t, 0, mtime) {
        for (auto &[hasremoved, cx, cy] : process[t]) {
            if (dist[cx][cy] < t) continue;
            dist[cx][cy] = t;
            //transition to next locations, up, down, left, right;
            repl(i, 0, 4) {
                int nx = cx+dx[i], ny = cy+dy[i];

                if (nx < 1 || nx > n || ny < 1 || ny > m || dist[nx][ny] != INF || grid[nx][ny] == '#') continue;
                if (org_snake[{nx, ny}] != 0) {
                    //check to see if the head will hit the body;
                    int steps_needed = org_snake[{tx, ty}]-org_snake[{nx, ny}]-t;
                    if (steps_needed > 0) {
                        //if already removed, then we don't need to worry about this;
                        if (hasremoved) {
                            process[t+1].push_back({1, nx, ny});
                        } else {
                            //we will wait the necessary # of steps;
                            process[t+1+steps_needed].push_back({1, nx, ny});
                        }
                    } else {
                        process[t+1].push_back({hasremoved, nx, ny});
                    }
                } else {
                    process[t+1].push_back({hasremoved, nx, ny});
                }
            }
        }
    }

    __int128_t ans = 0;
    repe(i, 1, n) {
        repe(j, 1, m) {
            if (dist[i][j] != INF) {
                ans = ans+__int128_t(dist[i][j])*__int128_t(dist[i][j]);
            }
        }
    }
    
    cout << uint64_t(ans) << "\n";
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    //cin >> t;

    while(t--) {
        solve();
    }

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3684kb

input:

4 5 5
3 5
3 4
3 3
3 2
4 2
.....
.....
.....
.....

output:

293

result:

ok single line: '293'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

2 2 4
1 1
1 2
2 2
2 1
..
..

output:

14

result:

ok single line: '14'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

5 5 3
1 2
1 1
2 1
.....
.###.
.#.#.
.###.
.....

output:

407

result:

ok single line: '407'

Test #4:

score: -100
Time Limit Exceeded

input:

3000 2900 1
1882 526
........................................................................................................#................................................................................................................................................................#................

output:


result: