Submission #1074285

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1074285	2024-08-25T09:23:12 Z	Zanite	Board Game (JOI24_boardgame)	C++17	17 / 100	3134 ms	123876 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;
         // if (fin_dist[ad][i] + total_cost[act] < 0) {
         //    debug(ad, i, fin_dist[ad][i], total_cost[act]);
         //    exit(0);
         // }
         // 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
         );
         chmin(total_cost[j], INF);
      }
   }

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

   // solve_small_k();
   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:386:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  386 |    scanf("%d %d %d", &N, &M, &K);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:388:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  388 |       scanf("%d %d", &u, &v);
      |       ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:394:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  394 |       scanf(" %c", &buf);
      |       ~~~~~^~~~~~~~~~~~~
Main.cpp:397:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  397 |    for (int i = 1; i <= N; i++) scanf("%d", &st_pos[i]);
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1

3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	11580 KB	Output is correct
2	Correct	852 ms	69596 KB	Output is correct
3	Correct	2181 ms	111712 KB	Output is correct
4	Correct	130 ms	111328 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	13392 KB	Output is correct
2	Correct	1284 ms	77832 KB	Output is correct
3	Correct	1411 ms	123524 KB	Output is correct
4	Correct	1329 ms	123516 KB	Output is correct
5	Correct	2570 ms	123848 KB	Output is correct
6	Correct	846 ms	123332 KB	Output is correct
7	Correct	1123 ms	102456 KB	Output is correct
8	Correct	1426 ms	117784 KB	Output is correct

Subtask #3

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	13360 KB	Output is correct
2	Correct	1427 ms	77820 KB	Output is correct
3	Correct	1146 ms	123396 KB	Output is correct
4	Correct	1403 ms	123536 KB	Output is correct
5	Correct	3134 ms	123876 KB	Output is correct
6	Correct	905 ms	123444 KB	Output is correct
7	Correct	1006 ms	123392 KB	Output is correct
8	Correct	2970 ms	123860 KB	Output is correct
9	Correct	314 ms	34744 KB	Output is correct
10	Correct	227 ms	34756 KB	Output is correct

Subtask #4

0.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	9928 KB	Output is correct
2	Correct	34 ms	13392 KB	Output is correct
3	Correct	33 ms	13392 KB	Output is correct
4	Correct	33 ms	13392 KB	Output is correct
5	Correct	23 ms	11100 KB	Output is correct
6	Correct	25 ms	11100 KB	Output is correct
7	Incorrect	18 ms	9820 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #5

0.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	923 ms	123372 KB	Output is correct
2	Correct	1117 ms	123516 KB	Output is correct
3	Correct	1324 ms	123508 KB	Output is correct
4	Correct	1004 ms	123612 KB	Output is correct
5	Correct	1051 ms	123520 KB	Output is correct
6	Correct	1074 ms	102404 KB	Output is correct
7	Correct	264 ms	34412 KB	Output is correct
8	Incorrect	250 ms	60768 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #6

0.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	923 ms	123372 KB	Output is correct
2	Correct	1117 ms	123516 KB	Output is correct
3	Correct	1324 ms	123508 KB	Output is correct
4	Correct	1004 ms	123612 KB	Output is correct
5	Correct	1051 ms	123520 KB	Output is correct
6	Correct	1074 ms	102404 KB	Output is correct
7	Correct	264 ms	34412 KB	Output is correct
8	Incorrect	250 ms	60768 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #7

0.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	9928 KB	Output is correct
2	Correct	34 ms	13392 KB	Output is correct
3	Correct	33 ms	13392 KB	Output is correct
4	Correct	33 ms	13392 KB	Output is correct
5	Correct	23 ms	11100 KB	Output is correct
6	Correct	25 ms	11100 KB	Output is correct
7	Incorrect	18 ms	9820 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #8

0.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	11580 KB	Output is correct
2	Correct	852 ms	69596 KB	Output is correct
3	Correct	2181 ms	111712 KB	Output is correct
4	Correct	130 ms	111328 KB	Output is correct
5	Correct	36 ms	13392 KB	Output is correct
6	Correct	1284 ms	77832 KB	Output is correct
7	Correct	1411 ms	123524 KB	Output is correct
8	Correct	1329 ms	123516 KB	Output is correct
9	Correct	2570 ms	123848 KB	Output is correct
10	Correct	846 ms	123332 KB	Output is correct
11	Correct	1123 ms	102456 KB	Output is correct
12	Correct	1426 ms	117784 KB	Output is correct
13	Correct	66 ms	13360 KB	Output is correct
14	Correct	1427 ms	77820 KB	Output is correct
15	Correct	1146 ms	123396 KB	Output is correct
16	Correct	1403 ms	123536 KB	Output is correct
17	Correct	3134 ms	123876 KB	Output is correct
18	Correct	905 ms	123444 KB	Output is correct
19	Correct	1006 ms	123392 KB	Output is correct
20	Correct	2970 ms	123860 KB	Output is correct
21	Correct	314 ms	34744 KB	Output is correct
22	Correct	227 ms	34756 KB	Output is correct
23	Correct	21 ms	9928 KB	Output is correct
24	Correct	34 ms	13392 KB	Output is correct
25	Correct	33 ms	13392 KB	Output is correct
26	Correct	33 ms	13392 KB	Output is correct
27	Correct	23 ms	11100 KB	Output is correct
28	Correct	25 ms	11100 KB	Output is correct
29	Incorrect	18 ms	9820 KB	Output isn't correct
30	Halted	0 ms	0 KB	-