結果

問題 No.2826 Earthwork
ユーザー 👑 hos.lyrichos.lyric
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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
*/
0