QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#846861 | #8236. Snake Move | Red0 | TL | 0ms | 3840kb | C++20 | 19.3kb | 2025-01-07 15:18:46 | 2025-01-07 15:18:47 |
Judging History
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;
}
};
struct hash_pair {
template <class T1, class T2>
size_t operator()(const pair<T1, T2>& p) const
{
// Hash the first element
size_t hash1 = hash<T1>{}(p.first);
// Hash the second element
size_t hash2 = hash<T2>{}(p.second);
// Combine the two hash values
return hash1
^ (hash2 + 0x9e3779b9 + (hash1 << 6)
+ (hash1 >> 2));
}
};
void solve() {
int n, m, k;
cin >> n >> m >> k;
//represents if some square is a snake and also represents distance+1 from head;
vvi org_snake(n+1, vi(m+1, 0));
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 || 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: 0ms
memory: 3536kb
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: 3708kb
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: 3840kb
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 ........................................................................................................#................................................................................................................................................................#................