結果
問題 | No.2826 Earthwork |
ユーザー |
👑 |
提出日時 | 2024-07-26 22:36:46 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,438 ms / 5,000 ms |
コード長 | 7,334 bytes |
コンパイル時間 | 2,316 ms |
コンパイル使用メモリ | 127,344 KB |
実行使用メモリ | 242,804 KB |
最終ジャッジ日時 | 2024-07-26 22:37:21 |
合計ジャッジ時間 | 32,684 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 29 ms
8,980 KB |
testcase_02 | AC | 1,438 ms
240,368 KB |
testcase_03 | AC | 157 ms
28,612 KB |
testcase_04 | AC | 1,119 ms
206,012 KB |
testcase_05 | AC | 200 ms
58,492 KB |
testcase_06 | AC | 642 ms
135,852 KB |
testcase_07 | AC | 814 ms
168,296 KB |
testcase_08 | AC | 1,331 ms
240,364 KB |
testcase_09 | AC | 1,279 ms
242,032 KB |
testcase_10 | AC | 1,168 ms
240,616 KB |
testcase_11 | AC | 841 ms
239,472 KB |
testcase_12 | AC | 22 ms
8,840 KB |
testcase_13 | AC | 341 ms
83,704 KB |
testcase_14 | AC | 1,283 ms
242,804 KB |
testcase_15 | AC | 311 ms
67,712 KB |
testcase_16 | AC | 462 ms
136,576 KB |
testcase_17 | AC | 162 ms
42,276 KB |
testcase_18 | AC | 415 ms
132,728 KB |
testcase_19 | AC | 176 ms
58,364 KB |
testcase_20 | AC | 981 ms
200,300 KB |
testcase_21 | AC | 19 ms
10,004 KB |
testcase_22 | AC | 757 ms
163,096 KB |
testcase_23 | AC | 702 ms
161,180 KB |
testcase_24 | AC | 1,226 ms
240,548 KB |
testcase_25 | AC | 383 ms
167,532 KB |
testcase_26 | AC | 758 ms
164,232 KB |
testcase_27 | AC | 10 ms
5,376 KB |
testcase_28 | AC | 1,321 ms
242,284 KB |
testcase_29 | AC | 171 ms
25,432 KB |
testcase_30 | AC | 49 ms
13,192 KB |
testcase_31 | AC | 103 ms
22,592 KB |
testcase_32 | AC | 17 ms
7,144 KB |
testcase_33 | AC | 706 ms
138,876 KB |
testcase_34 | AC | 1,421 ms
240,240 KB |
testcase_35 | AC | 318 ms
64,624 KB |
testcase_36 | AC | 1,436 ms
241,516 KB |
testcase_37 | AC | 1,369 ms
241,140 KB |
testcase_38 | AC | 712 ms
128,856 KB |
testcase_39 | AC | 39 ms
15,760 KB |
testcase_40 | AC | 33 ms
11,928 KB |
ソースコード
#include <cassert> #include <cmath> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <functional> #include <iostream> #include <limits> #include <map> #include <numeric> #include <queue> #include <random> #include <set> #include <sstream> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> using namespace std; // using Int = long long; template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; } template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } #define COLOR(s) ("\x1b[" s "m") #ifndef LIBRA_OTHER_INT128_H_ #define LIBRA_OTHER_INT128_H_ #include <stdio.h> #include <iostream> constexpr unsigned __int128 toUInt128(const char *s) { unsigned __int128 x = 0; for (; *s; ++s) x = x * 10 + (*s - '0'); return x; } constexpr __int128 toInt128(const char *s) { if (*s == '-') return -toInt128(s + 1); __int128 x = 0; for (; *s; ++s) x = x * 10 + (*s - '0'); return x; } unsigned __int128 inUInt128() { static char buf[41]; scanf("%s", buf); return toUInt128(buf); } __int128 inInt128() { static char buf[41]; scanf("%s", buf); return toInt128(buf); } void out(unsigned __int128 x) { static char buf[41]; int len = 0; do { buf[len++] = '0' + static_cast<int>(x % 10); } while (x /= 10); for (int i = len; --i >= 0; ) putchar(buf[i]); } void out(__int128 x) { if (x < 0) { putchar('-'); out(-static_cast<unsigned __int128>(x)); } else { out(static_cast<unsigned __int128>(x)); } } std::ostream &operator<<(std::ostream &os, unsigned __int128 x) { static char buf[41]; int len = 0; do { buf[len++] = '0' + static_cast<int>(x % 10); } while (x /= 10); for (int i = len; --i >= 0; ) os << buf[i]; return os; } std::ostream &operator<<(std::ostream &os, __int128 x) { if (x < 0) { os << '-' << -static_cast<unsigned __int128>(x); } else { os << static_cast<unsigned __int128>(x); } return os; } #endif // LIBRA_OTHER_INT128_H_ using INT = __int128; constexpr INT INF = toInt128("1002003004005006007006005004003002001"); #define abs my_abs INT abs(INT x) { return (x < 0) ? -x : x; } #define MAX [810][810] int N; INT H MAX; char C MAX; INT A MAX, B MAX; int id(int x, int y) { return x * N + y; } vector<pair<pair<int, int>, INT>> es; void ae(int u, int v, INT c) { // cerr<<"[ae] "<<u<<" "<<v<<" "<<c<<endl; es.emplace_back(make_pair(u, v), c); } int main() { for (; ~scanf("%d", &N); ) { for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) H[x][y] = inInt128(); for (int x = 0; x < N; ++x) scanf("%s", C[x]); for (int x = 0; x < N - 1; ++x) for (int y = 0; y < N; ++y) A[x][y] = inInt128(); for (int x = 0; x < N; ++x) for (int y = 0; y < N - 1; ++y) B[x][y] = inInt128(); // INT big = 0; // for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) chmax(big, abs(H[x][y])); const INT big = INF / 3; const int U = N * N + 1; const int S = N * N; es.clear(); for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) { if (C[x][y] == '-' || C[x][y] == '=') { // h[x][y] <= H[x][y] if ((x + y) & 1) { ae(id(x, y), S, +H[x][y]); } else { ae(S, id(x, y), +H[x][y]); } } if (C[x][y] == '+' || C[x][y] == '=') { // h[x][y] >= H[x][y] if ((x + y) & 1) { ae(S, id(x, y), -H[x][y]); } else { ae(id(x, y), S, -H[x][y]); } } } for (int x = 0; x < N - 1; ++x) for (int y = 0; y < N; ++y) { // -lim <= h[x][y] - (-h[x+1][y]) <= +lim // -lim <= h[x+1][y] - (-h[x][y]) <= +lim const INT lim = A[x][y] * abs(H[x][y] + H[x+1][y]); ae(id(x, y), id(x+1, y), lim); ae(id(x+1, y), id(x, y), lim); } for (int x = 0; x < N; ++x) for (int y = 0; y < N - 1; ++y) { const INT lim = B[x][y] * abs(H[x][y] + H[x][y+1]); ae(id(x, y), id(x, y+1), lim); ae(id(x, y+1), id(x, y), lim); } /* vector<INT> dist(U, INF), tsid(U, INF); dist[S] = 0; tsid[S] = 0; for (int h = 1; h <= U; ++h) { for (const auto &e : es) { const int u = e.first.first; const int v = e.first.second; const INT c = e.second; chmin(dist[v], dist[u] + c); chmin(tsid[u], c + tsid[v]); } } */ vector<INT> dists[2]; for (int dir = 0; dir < 2; ++dir) { vector<vector<pair<INT, int>>> graph(U); for (const auto &e : es) { int u = e.first.first; int v = e.first.second; INT c = e.second; if (dir) swap(u, v); if (u == S || v == S) c += big; assert(c >= 0); graph[u].emplace_back(c, v); } using Entry = pair<INT, int>; priority_queue<Entry, vector<Entry>, greater<Entry>> que; auto &dist = dists[dir]; dist.assign(U, INF); que.emplace(dist[S] = 0, S); for (; que.size(); ) { const INT c = que.top().first; const int u = que.top().second; que.pop(); if (dist[u] != c) continue; for (const auto &cv : graph[u]) { const INT cc = dist[u] + cv.first; const int v = cv.second; if (chmin(dist[v], cc)) { que.emplace(cc, v); } } } for (int u = 0; u < U; ++u) if (S != u) { dist[u] -= big; } } const auto &dist = dists[0]; const auto &tsid = dists[1]; #ifdef LOCAL for(int x=0;x<N;++x)pv(dist.begin()+id(x,0),dist.begin()+id(x+1,0));cerr<<dist[S]<<endl; for(int x=0;x<N;++x)pv(tsid.begin()+id(x,0),tsid.begin()+id(x+1,0));cerr<<tsid[S]<<endl; vector<vector<INT>>d(U,vector<INT>(U,INF)); for(int u=0;u<U;++u)d[u][u]=0; for(const auto&e:es)chmin(d[e.first.first][e.first.second],e.second); for(int w=0;w<U;++w)for(int u=0;u<U;++u)for(int v=0;v<U;++v)chmin(d[u][v],d[u][w]+d[w][v]); for(int u=0;u<U;++u)assert(min(d[S][u],INF/9)==min(dist[u],INF/9)); for(int u=0;u<U;++u)assert(min(d[u][S],INF/9)==min(tsid[u],INF/9)); #endif int Q; scanf("%d", &Q); for (; Q--; ) { int X, Y; scanf("%d%d", &X, &Y); --X; --Y; const INT E = inInt128(); // cerr<<COLOR("33")<<X<<" "<<Y<<" "<<E<<": "<<dist[id(X,Y)]<<" "<<tsid[id(X,Y)]<<COLOR()<<endl; // h[X][Y] >= E bool ans; if ((X + Y) & 1) { // ae(S, id(X, Y), -E); ans = (-E + tsid[id(X, Y)] >= 0); } else { // ae(id(X, Y), S, -E); ans = (-E + dist[id(X, Y)] >= 0); } puts(ans ? "Yes" : "No"); } } return 0; } /* -8 7 -6 32 1 -2 9 -4 0 3 2 -3 63 6 -5 4 0 14 20 6 105 5 2 31 87 0 3 24 79 63 73 101 -4 0 */