답안 #1074273

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1074273	2024-08-25T09:17:36 Z	Zanite	Board Game (JOI24_boardgame)	C++17	46 / 100	3128 ms	123816 KB

Main

// こんな僕等がお互い蹴落として
// まで掴んだ物は何ですか
// 僕は　僕を愛してあげたい
// 
// こんなことなら生まれてこなけりゃって
// 全部嫌になってくけれど
// 絶えず　脈打つこれは何だろう
// 
// 何だろう...

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// Pragmas
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

// Namespaces
using namespace std;
using namespace __gnu_pbds;

// Data types
using si  = short int;
using ll  = long long;
using ull = unsigned long long;
using lll = __int128;
using ld  = long double;

// Pairs
using pii  = pair<int, int>;
using psi  = pair<si, si>;
using pll  = pair<ll, ll>;
using plll = pair<lll, lll>;
using pld  = pair<ld, ld>;
#define fi first
#define se second

// PBDS
template<typename Z>
using ordered_set = tree<Z, null_type, less<Z>, rb_tree_tag, tree_order_statistics_node_update>;

// Various outputs and debug
template<typename Z, typename = void> struct is_iterable : false_type {};
template<typename Z> struct is_iterable<Z, void_t<decltype(begin(declval<Z>())),decltype(end(declval<Z>()))>> : true_type {};
template<typename Z> typename enable_if<is_iterable<Z>::value&&!is_same<Z, string>::value,ostream&>::type operator<<(ostream &os, const Z &v);

template<typename Y, typename Z> ostream& operator<<(ostream &os, const pair<Y, Z> &p) {
   return os << "(" << p.fi << ", " << p.se << ")";
}
template<class TupType, size_t... I> void printTuple(ostream& os, const TupType& _tup, index_sequence<I...>) {
   os << "(";
   (..., (os << (I == 0? "" : ", ") << get<I>(_tup)));
   os << ")";
}
template<class... Z> ostream& operator<<(ostream& os, const tuple<Z...>& _tup) {
   printTuple(os, _tup, make_index_sequence<sizeof...(Z)>());
   return os;
}
template<typename Z> typename enable_if<is_iterable<Z>::value&&!is_same<Z, string>::value,ostream&>::type operator<<(ostream &os, const Z &v) {
   os << "["; 
   for (auto it = v.begin(); it != v.end();) { os << *it; if (++it != v.end()) os << ", "; }
   return os << "]";
}

#define debug(...)   logger(cout, #__VA_ARGS__, __VA_ARGS__)
#define debugV(v, x)  vlogger(cout, #v, x, v[x]);
#define rrebug(...)   logger(cerr, #__VA_ARGS__, __VA_ARGS__)
#define rrebugV(v, x) vlogger(cerr, #v, x, v[x]);
template <typename... Args>
void logger(ostream& os, string vars, Args &&...values) {
   os << vars << " = "; string delim = "";
   (..., (os << delim << values, delim = ", "));
   os << "\n";
}
template<class Y, class Z>
void vlogger(ostream& os, string var, Y idx, Z val) {
   os << var << "[" << idx << "] = " << val << "\n";
}

// Various macros
#define All(x)         x.begin(), x.end()
#define Sort(x)         sort(All(x))
#define Reverse(x)      reverse(All(x))
#define Uniqueify(x)     Sort(x); x.erase(unique(All(x)), x.end())
#define RandomSeed      chrono::steady_clock::now().time_since_epoch().count()
#define MultipleTestcases int _tc; cin >> _tc; for (int _cur_tc = 1; _cur_tc <= _tc; _cur_tc++)

// Chmin & chmax
template<typename Z> bool chmin(Z &a, Z b) { return (b < a) ? a = b, true : false; }
template<typename Z> bool chmax(Z &a, Z b) { return (b > a) ? a = b, true : false; }
 
// Modular arithmetic
template<int MOD>
class ModInt {
  public:
   int v;
   ModInt() : v(0) {}
   ModInt(long long _v) {
      v = int((-MOD < _v && _v < MOD) ? (_v) : (_v % MOD));
      if (v < 0) v += MOD;
   }
 
   friend bool operator==(const ModInt &a, const ModInt &b) { return a.v == b.v; }
   friend bool operator!=(const ModInt &a, const ModInt &b) { return a.v != b.v; }
   friend bool operator< (const ModInt &a, const ModInt &b) { return a.v <  b.v; }
   friend bool operator<=(const ModInt &a, const ModInt &b) { return a.v <= b.v; }
   friend bool operator> (const ModInt &a, const ModInt &b) { return a.v >  b.v; }
   friend bool operator>=(const ModInt &a, const ModInt &b) { return a.v >= b.v; }
 
   ModInt &operator+=(const ModInt &a) { if ((v += a.v) >= MOD) v -= MOD; return *this; }
   ModInt &operator-=(const ModInt &a) { if ((v -= a.v) < 0) v += MOD; return *this; }
   ModInt &operator*=(const ModInt &a) { v = 1ll * v * a.v % MOD; return *this; }
   ModInt &operator/=(const ModInt &a) { return (*this) *= inverse(a); }
 
   friend ModInt pow(ModInt a, long long x) {
      ModInt res = 1;
      for (; x; x /= 2, a *= a) if (x & 1) res *= a;
      return res;
   }
   friend ModInt inverse(ModInt a) { return pow(a, MOD - 2); }
 
   ModInt operator+ () const { return ModInt( v); }
   ModInt operator- () const { return ModInt(-v); }
   ModInt operator++() const { return *this += 1; }
   ModInt operator--() const { return *this -= 1; }
 
   friend ModInt operator+(ModInt a, const ModInt &b) { return a += b; }
   friend ModInt operator-(ModInt a, const ModInt &b) { return a -= b; }
   friend ModInt operator*(ModInt a, const ModInt &b) { return a *= b; }
   friend ModInt operator/(ModInt a, const ModInt &b) { return a /= b; }
 
   friend istream &operator>>(istream &is, ModInt &v) { return is >> v.v; }
   friend ostream &operator<<(ostream &os, const ModInt &v) { return os << v.v; }
};
const int ModA = 998244353;
const int ModC = 1e9 + 7;
using MintA   = ModInt<ModA>;
using MintC   = ModInt<ModC>;

// Other constants
const ll INF  = 1e18;
const ll iINF = 1e9;
const ld EPS  = 1e-9;
const ld iEPS = 1e-6;

const int maxN  = 50'023;
const int THRES = 250;

int N, M, K;
vector<int> board[maxN];
bool state[maxN];
int st_pos[maxN];

ll dist_single[maxN], dist_double[maxN];
vector<pll> adj_single[maxN], adj_double[maxN];

ll total_cost[maxN];
ll tmp_dist[2][maxN], ans[maxN];

int min_stops[maxN];
ll fin_dist[THRES][maxN];
bool fin_vis[THRES][maxN];

void dijkstra(ll* dist, vector<pll> *adj) {
   vector<bool> vis(N + 1, false);
   priority_queue<pll, vector<pll>, greater<pll>> pyqe;
   for (int i = 1; i <= N; i++) {
      pyqe.push({dist[i], i});
   }

   while (!pyqe.empty()) {
      int cur = pyqe.top().se; pyqe.pop();
      if (vis[cur]) continue;

      vis[cur] = true;
      for (auto [nxt, w] : adj[cur]) {
         if (dist[nxt] > dist[cur] + w) {
            dist[nxt] = dist[cur] + w;
            pyqe.push({dist[nxt], nxt});
         }
      }
   }
}

void linear_dijkstra(ll m, ll c) {
   // {dist, gone at least once to stop, vertex}
   using State = tuple<ll, int, int>;

   for (int i = 1; i <= N; i++) {
      tmp_dist[0][i] = tmp_dist[1][i] = INF;
   }

   vector vis(2, vector(N + 1, false));
   priority_queue<State, vector<State>, greater<State>> pyqe;
   tmp_dist[0][st_pos[1]] = c;
   pyqe.push({c, 0, st_pos[1]});

   while (!pyqe.empty()) {
      auto [_, cs, cv] = pyqe.top(); pyqe.pop();
      if (vis[cs][cv]) continue;

      vis[cs][cv] = true;
      // cout << make_pair(cs, cv) << ": " << _ << "\n";
      for (auto nxt : board[cv]) {
         bool stop_state = (state[cv] && cv != st_pos[1]);
         ll w = (stop_state ? m : 0ll) + 1ll;
         int ns = cs | stop_state;
         if (tmp_dist[ns][nxt] > tmp_dist[cs][cv] + w) {
            tmp_dist[ns][nxt] = tmp_dist[cs][cv] + w;
            pyqe.push({tmp_dist[ns][nxt], ns, nxt});
         }
      }
   }

   for (int i = 1; i <= N; i++) {
      chmin(ans[i], tmp_dist[1][i]);
   }

   // debug(m, c, s);
   // for (int i = 1; i <= N; i++) {
   //    if (tmp_dist[1][i] >= INF) cout << "- ";
   //    else cout << tmp_dist[1][i] << " ";
   // }
   // cout << "\n\n";
}

void solve_reachable() {
   for (int i = 1; i <= N; i++) ans[i] = INF;
   ans[st_pos[1]] = 0;

   vector<bool> vis(N + 1, false);
   queue<int> q;
   for (int i = 1; i <= N; i++) q.push(st_pos[1]);

   while (!q.empty()) {
      int cur = q.front(); q.pop();
      if (vis[cur]) continue;

      vis[cur] = true;
      bool stop_state = (state[cur] && cur != st_pos[1]);
      if (stop_state) continue;
      for (auto nxt : board[cur]) {
         if (ans[nxt] > ans[cur] + 1) {
            ans[nxt] = ans[cur] + 1;
            q.push(nxt);
         }
      }
   }
}

void solve_small_k() {
   vector<pll> lines;
   for (int i = 2; i <= N; i++) {
      ll m = total_cost[i] - total_cost[i-1];
      ll c = total_cost[i] - (ll)i * m;
      lines.push_back({m, c});
   }
   Uniqueify(lines);
   // debug(lines);

   for (auto [m, c] : lines) linear_dijkstra(m, c);
}

void solve_large_k() {
   // get minimum stops needed to get to each node
   {
      for (int i = 1; i <= N; i++) min_stops[i] = iINF;
      min_stops[st_pos[1]] = 0;
      deque<int> dq;
      dq.push_back(st_pos[1]);

      vector<bool> vis(N+1, false);
      while (!dq.empty()) {
         int cur = dq.front(); dq.pop_front();
         if (vis[cur]) continue;

         vis[cur] = true;
         for (auto nxt : board[cur]) {
            int w = (state[cur] && cur != st_pos[1]);
            if (min_stops[nxt] > min_stops[cur] + w) {
               min_stops[nxt] = min_stops[cur] + w;
               if (w) dq.push_back(nxt);
               else dq.push_front(nxt);
            }
         }
      }
   }
   
   // Dijkstra with extra states
   {
      for (int ad = 0; ad < THRES; ad++) {
         for (int i = 1; i <= N; i++) fin_dist[ad][i] = INF;
      }
      queue<pii> q;
      q.push({0, st_pos[1]});
      fin_dist[0][st_pos[1]] = 0;

      while (!q.empty()) {
         auto [ad, cur] = q.front(); q.pop();
         if (fin_vis[ad][cur]) continue;

         fin_vis[ad][cur] = true;
         for (auto nxt : board[cur]) {
            bool stop_state = (state[cur] && cur != st_pos[1]);
            int nxt_ad = ad + min_stops[cur] - min_stops[nxt] + stop_state;
            if (0 <= nxt_ad && nxt_ad < THRES) {
               if (fin_dist[nxt_ad][nxt] > fin_dist[ad][cur] + 1) {
                  fin_dist[nxt_ad][nxt] = fin_dist[ad][cur] + 1;
                  q.push({nxt_ad, nxt});
               }
            }
         }
      }
   }

   for (int i = 1; i <= N; i++) {
      ans[i] = INF;
      for (int ad = 0; ad < THRES; ad++) {
         int act = ad + min_stops[i];
         if (act > N) break;
         // debug(i, act, fin_dist[ad][i], total_cost[act]);
         chmin(ans[i], fin_dist[ad][i] + total_cost[act]);
      }
   }
}

void solve() {
   // compute distances to single and double stop nodes
   for (int i = 1; i <= N; i++) dist_single[i] = dist_double[i] = INF;

   for (int i = 1; i <= N; i++) {
      for (auto j : board[i]) {
         adj_single[i].push_back({j, 1});
         adj_double[i].push_back({j, !state[i]});
      }
      if (state[i]) {
         dist_single[i] = 0;
         for (auto j : board[i]) {
            if (state[j]) dist_double[i] = dist_double[j] = 0;
         }
      }
   }

   dijkstra(dist_single, adj_single);
   dijkstra(dist_double, adj_double);

   for (int i = 1; i <= N; i++) {
      if (dist_single[i] == 0) dist_single[i] = 2;
      // debug(i, dist_single[i], dist_double[i]);
   }

   for (int i = 2; i <= K; i++) {
      ll c_single = dist_single[st_pos[i]] - 2;
      ll c_double = dist_double[st_pos[i]];

      // binary search switching position from single to double
      for (int j = 1; j <= N; j++) {
         total_cost[j] += min(
            2ll * j + c_single,
            1ll * j + c_double
         );
      }
   }

   // for (int i = 1; i <= N; i++) debugV(total_cost, i);

   // solve_large_k();

   if (K <= THRES) solve_small_k();
   else solve_large_k();

   for (int i = 1; i <= N; i++) {
      printf("%lld\n", ans[i]);
   }
}

int main() {
   scanf("%d %d %d", &N, &M, &K);
   for (int u, v, i = 1; i <= M; i++) {
      scanf("%d %d", &u, &v);
      board[u].push_back(v);
      board[v].push_back(u);
   }
   for (int i = 1; i <= N; i++) {
      char buf;
      scanf(" %c", &buf);
      state[i] = (buf == '1');
   }
   for (int i = 1; i <= N; i++) scanf("%d", &st_pos[i]);

   solve_reachable();
   solve();
}

// dibisakan

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:380:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  380 |    scanf("%d %d %d", &N, &M, &K);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:382:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  382 |       scanf("%d %d", &u, &v);
      |       ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:388:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  388 |       scanf(" %c", &buf);
      |       ~~~~~^~~~~~~~~~~~~
Main.cpp:391:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  391 |    for (int i = 1; i <= N; i++) scanf("%d", &st_pos[i]);
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1

0.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	15 ms	11664 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	13452 KB	Output is correct
2	Correct	1351 ms	77836 KB	Output is correct
3	Correct	74 ms	15240 KB	Output is correct
4	Correct	71 ms	15364 KB	Output is correct
5	Correct	2880 ms	123736 KB	Output is correct
6	Correct	66 ms	15300 KB	Output is correct
7	Correct	58 ms	14168 KB	Output is correct
8	Correct	90 ms	14932 KB	Output is correct

Subtask #3

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	56 ms	13220 KB	Output is correct
2	Correct	1396 ms	77808 KB	Output is correct
3	Correct	1218 ms	123304 KB	Output is correct
4	Correct	1541 ms	123424 KB	Output is correct
5	Correct	3128 ms	123816 KB	Output is correct
6	Correct	77 ms	15184 KB	Output is correct
7	Correct	70 ms	15352 KB	Output is correct
8	Correct	2891 ms	123032 KB	Output is correct
9	Correct	309 ms	34232 KB	Output is correct
10	Correct	25 ms	10204 KB	Output is correct

Subtask #4

0.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	4444 KB	Output is correct
2	Correct	6 ms	4532 KB	Output is correct
3	Correct	47 ms	13400 KB	Output is correct
4	Correct	6 ms	4444 KB	Output is correct
5	Correct	6 ms	4444 KB	Output is correct
6	Correct	4 ms	4444 KB	Output is correct
7	Incorrect	18 ms	9880 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #5

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	61 ms	14620 KB	Output is correct
2	Correct	92 ms	14740 KB	Output is correct
3	Correct	55 ms	14756 KB	Output is correct
4	Correct	73 ms	14836 KB	Output is correct
5	Correct	101 ms	14656 KB	Output is correct
6	Correct	49 ms	13588 KB	Output is correct
7	Correct	27 ms	10568 KB	Output is correct
8	Correct	27 ms	9704 KB	Output is correct
9	Correct	24 ms	9836 KB	Output is correct
10	Correct	45 ms	14188 KB	Output is correct
11	Correct	51 ms	14188 KB	Output is correct
12	Correct	65 ms	15036 KB	Output is correct

Subtask #6

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	61 ms	14620 KB	Output is correct
2	Correct	92 ms	14740 KB	Output is correct
3	Correct	55 ms	14756 KB	Output is correct
4	Correct	73 ms	14836 KB	Output is correct
5	Correct	101 ms	14656 KB	Output is correct
6	Correct	49 ms	13588 KB	Output is correct
7	Correct	27 ms	10568 KB	Output is correct
8	Correct	27 ms	9704 KB	Output is correct
9	Correct	24 ms	9836 KB	Output is correct
10	Correct	45 ms	14188 KB	Output is correct
11	Correct	51 ms	14188 KB	Output is correct
12	Correct	65 ms	15036 KB	Output is correct
13	Correct	69 ms	15452 KB	Output is correct
14	Correct	63 ms	15360 KB	Output is correct
15	Correct	182 ms	15460 KB	Output is correct
16	Correct	167 ms	15216 KB	Output is correct
17	Correct	38 ms	14148 KB	Output is correct
18	Correct	144 ms	14172 KB	Output is correct
19	Correct	134 ms	13688 KB	Output is correct
20	Correct	64 ms	15348 KB	Output is correct
21	Correct	27 ms	9944 KB	Output is correct
22	Correct	32 ms	10400 KB	Output is correct
23	Correct	33 ms	10408 KB	Output is correct
24	Correct	46 ms	14344 KB	Output is correct
25	Correct	58 ms	14884 KB	Output is correct
26	Correct	62 ms	14844 KB	Output is correct
27	Correct	41 ms	10408 KB	Output is correct
28	Correct	174 ms	10528 KB	Output is correct
29	Correct	313 ms	10400 KB	Output is correct
30	Correct	68 ms	14888 KB	Output is correct
31	Correct	325 ms	14904 KB	Output is correct
32	Correct	546 ms	15044 KB	Output is correct

Subtask #7

0.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	4444 KB	Output is correct
2	Correct	6 ms	4532 KB	Output is correct
3	Correct	47 ms	13400 KB	Output is correct
4	Correct	6 ms	4444 KB	Output is correct
5	Correct	6 ms	4444 KB	Output is correct
6	Correct	4 ms	4444 KB	Output is correct
7	Incorrect	18 ms	9880 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #8

0.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	15 ms	11664 KB	Output isn't correct
2	Halted	0 ms	0 KB	-