Submission #1074288

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1074288	2024-08-25T09:23:29 Z	Zanite	Board Game (JOI24_boardgame)	C++17	49 / 100	2843 ms	123060 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	15 ms	11612 KB	Output is correct
2	Correct	843 ms	69068 KB	Output is correct
3	Correct	2458 ms	110820 KB	Output is correct
4	Correct	44 ms	14768 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	13320 KB	Output is correct
2	Correct	1463 ms	77308 KB	Output is correct
3	Correct	83 ms	14756 KB	Output is correct
4	Correct	60 ms	14680 KB	Output is correct
5	Correct	2837 ms	122884 KB	Output is correct
6	Correct	68 ms	14688 KB	Output is correct
7	Correct	45 ms	13640 KB	Output is correct
8	Correct	74 ms	14228 KB	Output is correct

Subtask #3

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	13404 KB	Output is correct
2	Correct	1263 ms	77440 KB	Output is correct
3	Correct	1134 ms	122956 KB	Output is correct
4	Correct	1376 ms	122912 KB	Output is correct
5	Correct	2843 ms	123060 KB	Output is correct
6	Correct	61 ms	14624 KB	Output is correct
7	Correct	92 ms	14608 KB	Output is correct
8	Correct	2796 ms	123052 KB	Output is correct
9	Correct	301 ms	34280 KB	Output is correct
10	Correct	25 ms	10208 KB	Output is correct

Subtask #4

0.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4444 KB	Output is correct
2	Correct	8 ms	4440 KB	Output is correct
3	Correct	35 ms	13396 KB	Output is correct
4	Correct	7 ms	4444 KB	Output is correct
5	Correct	6 ms	4444 KB	Output is correct
6	Correct	6 ms	4496 KB	Output is correct
7	Incorrect	18 ms	9820 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #5

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	14608 KB	Output is correct
2	Correct	61 ms	14572 KB	Output is correct
3	Correct	50 ms	14636 KB	Output is correct
4	Correct	50 ms	14836 KB	Output is correct
5	Correct	115 ms	14852 KB	Output is correct
6	Correct	43 ms	13660 KB	Output is correct
7	Correct	36 ms	10420 KB	Output is correct
8	Correct	23 ms	9576 KB	Output is correct
9	Correct	30 ms	9804 KB	Output is correct
10	Correct	39 ms	14272 KB	Output is correct
11	Correct	58 ms	14196 KB	Output is correct
12	Correct	79 ms	14912 KB	Output is correct

Subtask #6

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	14608 KB	Output is correct
2	Correct	61 ms	14572 KB	Output is correct
3	Correct	50 ms	14636 KB	Output is correct
4	Correct	50 ms	14836 KB	Output is correct
5	Correct	115 ms	14852 KB	Output is correct
6	Correct	43 ms	13660 KB	Output is correct
7	Correct	36 ms	10420 KB	Output is correct
8	Correct	23 ms	9576 KB	Output is correct
9	Correct	30 ms	9804 KB	Output is correct
10	Correct	39 ms	14272 KB	Output is correct
11	Correct	58 ms	14196 KB	Output is correct
12	Correct	79 ms	14912 KB	Output is correct
13	Correct	64 ms	15300 KB	Output is correct
14	Correct	63 ms	15464 KB	Output is correct
15	Correct	180 ms	15272 KB	Output is correct
16	Correct	141 ms	15340 KB	Output is correct
17	Correct	41 ms	14132 KB	Output is correct
18	Correct	150 ms	14172 KB	Output is correct
19	Correct	133 ms	13768 KB	Output is correct
20	Correct	65 ms	15352 KB	Output is correct
21	Correct	25 ms	9952 KB	Output is correct
22	Correct	36 ms	10296 KB	Output is correct
23	Correct	33 ms	10404 KB	Output is correct
24	Correct	52 ms	14340 KB	Output is correct
25	Correct	57 ms	14884 KB	Output is correct
26	Correct	53 ms	14868 KB	Output is correct
27	Correct	48 ms	10452 KB	Output is correct
28	Correct	170 ms	10520 KB	Output is correct
29	Correct	312 ms	10636 KB	Output is correct
30	Correct	58 ms	15040 KB	Output is correct
31	Correct	299 ms	14832 KB	Output is correct
32	Correct	539 ms	15048 KB	Output is correct

Subtask #7

0.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4444 KB	Output is correct
2	Correct	8 ms	4440 KB	Output is correct
3	Correct	35 ms	13396 KB	Output is correct
4	Correct	7 ms	4444 KB	Output is correct
5	Correct	6 ms	4444 KB	Output is correct
6	Correct	6 ms	4496 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	15 ms	11612 KB	Output is correct
2	Correct	843 ms	69068 KB	Output is correct
3	Correct	2458 ms	110820 KB	Output is correct
4	Correct	44 ms	14768 KB	Output is correct
5	Correct	62 ms	13320 KB	Output is correct
6	Correct	1463 ms	77308 KB	Output is correct
7	Correct	83 ms	14756 KB	Output is correct
8	Correct	60 ms	14680 KB	Output is correct
9	Correct	2837 ms	122884 KB	Output is correct
10	Correct	68 ms	14688 KB	Output is correct
11	Correct	45 ms	13640 KB	Output is correct
12	Correct	74 ms	14228 KB	Output is correct
13	Correct	40 ms	13404 KB	Output is correct
14	Correct	1263 ms	77440 KB	Output is correct
15	Correct	1134 ms	122956 KB	Output is correct
16	Correct	1376 ms	122912 KB	Output is correct
17	Correct	2843 ms	123060 KB	Output is correct
18	Correct	61 ms	14624 KB	Output is correct
19	Correct	92 ms	14608 KB	Output is correct
20	Correct	2796 ms	123052 KB	Output is correct
21	Correct	301 ms	34280 KB	Output is correct
22	Correct	25 ms	10208 KB	Output is correct
23	Correct	4 ms	4444 KB	Output is correct
24	Correct	8 ms	4440 KB	Output is correct
25	Correct	35 ms	13396 KB	Output is correct
26	Correct	7 ms	4444 KB	Output is correct
27	Correct	6 ms	4444 KB	Output is correct
28	Correct	6 ms	4496 KB	Output is correct
29	Incorrect	18 ms	9820 KB	Output isn't correct
30	Halted	0 ms	0 KB	-