QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#846874#8236. Snake MoveRed0TL 0ms3856kbC++205.2kb2025-01-07 15:28:012025-01-07 15:28:02

Judging History

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

  • [2025-01-07 15:28:02]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3856kb
  • [2025-01-07 15:28:01]
  • 提交

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 = 1000000000;
const int MOD = pow(2, 64);

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<pii> process(mtime+1);
    process[0].pb({hx, hy});
    repe(t, 0, mtime) {
        for (auto &[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) {
                        process[t+1+steps_needed].push_back({nx, ny});
                    } else {
                        process[t+1].push_back({nx, ny});
                    }
                } else {
                    process[t+1].push_back({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";
}

int 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: 3820kb

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: 3856kb

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: 3820kb

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: