Submission #1074214

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1074214	2024-08-25T08:52:44 Z	Zanite	Board Game (JOI24_boardgame)	C++17	49 / 100	2037 ms	15628 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 ll;
using ll  = long long;
using ull = unsigned long long;
using lll = __int128;
using ld  = long double;

// Pairs
using pii  = pair<ll, ll>;
// 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 ll _tc; cin >> _tc; for (ll _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<ll MOD>
class ModInt {
  public:
   ll v;
   ModInt() : v(0) {}
   ModInt(long long _v) {
      v = ll((-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 ll ModA = 998244353;
const ll 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 ll maxN  = 50'023;

ll N, M, K;
vector<ll> board[maxN];
bool state[maxN];
ll 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];

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

   while (!pyqe.empty()) {
      ll 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, ll, ll>;

   for (ll 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;
         ll 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 (ll i = 1; i <= N; i++) {
      chmin(ans[i], tmp_dist[1][i]);
   }

   // debug(m, c, s);
   // for (ll 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 (ll i = 1; i <= N; i++) ans[i] = INF;
   ans[st_pos[1]] = 0;

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

   while (!q.empty()) {
      ll 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() {
   // compute distances to single and double stop nodes
   for (ll i = 1; i <= N; i++) dist_single[i] = dist_double[i] = INF;

   for (ll 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 (ll i = 1; i <= N; i++) {
      if (dist_single[i] == 0) dist_single[i] = 2;
      // if (dist_double[i] == 0) dist_double[i] = 1;
      // debug(i, dist_single[i], dist_double[i]);
   }

   for (ll 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 (ll i = 1; i <= N; i++) {
         total_cost[i] += min(
            2ll * i + c_single,
            (ll)i + c_double
         );
      }
   }

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

   vector<pll> lines;
   for (ll 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);

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

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

   solve_reachable();
   solve();
}

// dibisakan

Compilation message

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

Subtask #1

3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	4440 KB	Output is correct
2	Correct	737 ms	10676 KB	Output is correct
3	Correct	2037 ms	15476 KB	Output is correct
4	Correct	45 ms	15016 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	4696 KB	Output is correct
2	Correct	800 ms	10732 KB	Output is correct
3	Correct	65 ms	15088 KB	Output is correct
4	Correct	72 ms	15080 KB	Output is correct
5	Correct	1761 ms	15504 KB	Output is correct
6	Correct	64 ms	15120 KB	Output is correct
7	Correct	82 ms	14144 KB	Output is correct
8	Correct	52 ms	14928 KB	Output is correct

Subtask #3

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	4696 KB	Output is correct
2	Correct	816 ms	10724 KB	Output is correct
3	Correct	111 ms	15104 KB	Output is correct
4	Correct	120 ms	15332 KB	Output is correct
5	Correct	1532 ms	15628 KB	Output is correct
6	Correct	74 ms	15124 KB	Output is correct
7	Correct	59 ms	15120 KB	Output is correct
8	Correct	1474 ms	15608 KB	Output is correct
9	Correct	144 ms	10936 KB	Output is correct
10	Correct	23 ms	10952 KB	Output is correct

Subtask #4

0.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4440 KB	Output is correct
2	Correct	8 ms	4440 KB	Output is correct
3	Correct	9 ms	4440 KB	Output is correct
4	Correct	10 ms	4676 KB	Output is correct
5	Correct	7 ms	4440 KB	Output is correct
6	Correct	4 ms	4376 KB	Output is correct
7	Incorrect	13 ms	4444 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	73 ms	15112 KB	Output is correct
2	Correct	59 ms	15244 KB	Output is correct
3	Correct	81 ms	15004 KB	Output is correct
4	Correct	51 ms	14996 KB	Output is correct
5	Correct	76 ms	15060 KB	Output is correct
6	Correct	44 ms	14236 KB	Output is correct
7	Correct	44 ms	11080 KB	Output is correct
8	Correct	26 ms	10036 KB	Output is correct
9	Correct	27 ms	9988 KB	Output is correct
10	Correct	42 ms	14468 KB	Output is correct
11	Correct	71 ms	14796 KB	Output is correct
12	Correct	68 ms	14632 KB	Output is correct

Subtask #6

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	15112 KB	Output is correct
2	Correct	59 ms	15244 KB	Output is correct
3	Correct	81 ms	15004 KB	Output is correct
4	Correct	51 ms	14996 KB	Output is correct
5	Correct	76 ms	15060 KB	Output is correct
6	Correct	44 ms	14236 KB	Output is correct
7	Correct	44 ms	11080 KB	Output is correct
8	Correct	26 ms	10036 KB	Output is correct
9	Correct	27 ms	9988 KB	Output is correct
10	Correct	42 ms	14468 KB	Output is correct
11	Correct	71 ms	14796 KB	Output is correct
12	Correct	68 ms	14632 KB	Output is correct
13	Correct	64 ms	15260 KB	Output is correct
14	Correct	70 ms	15076 KB	Output is correct
15	Correct	187 ms	15296 KB	Output is correct
16	Correct	125 ms	15288 KB	Output is correct
17	Correct	58 ms	14224 KB	Output is correct
18	Correct	160 ms	14116 KB	Output is correct
19	Correct	139 ms	13728 KB	Output is correct
20	Correct	71 ms	15132 KB	Output is correct
21	Correct	30 ms	10212 KB	Output is correct
22	Correct	35 ms	10152 KB	Output is correct
23	Correct	58 ms	10260 KB	Output is correct
24	Correct	82 ms	14452 KB	Output is correct
25	Correct	53 ms	14604 KB	Output is correct
26	Correct	59 ms	14640 KB	Output is correct
27	Correct	62 ms	10240 KB	Output is correct
28	Correct	149 ms	10136 KB	Output is correct
29	Correct	319 ms	10152 KB	Output is correct
30	Correct	64 ms	14632 KB	Output is correct
31	Correct	262 ms	14612 KB	Output is correct
32	Correct	489 ms	14608 KB	Output is correct

Subtask #7

0.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4440 KB	Output is correct
2	Correct	8 ms	4440 KB	Output is correct
3	Correct	9 ms	4440 KB	Output is correct
4	Correct	10 ms	4676 KB	Output is correct
5	Correct	7 ms	4440 KB	Output is correct
6	Correct	4 ms	4376 KB	Output is correct
7	Incorrect	13 ms	4444 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	22 ms	4440 KB	Output is correct
2	Correct	737 ms	10676 KB	Output is correct
3	Correct	2037 ms	15476 KB	Output is correct
4	Correct	45 ms	15016 KB	Output is correct
5	Correct	21 ms	4696 KB	Output is correct
6	Correct	800 ms	10732 KB	Output is correct
7	Correct	65 ms	15088 KB	Output is correct
8	Correct	72 ms	15080 KB	Output is correct
9	Correct	1761 ms	15504 KB	Output is correct
10	Correct	64 ms	15120 KB	Output is correct
11	Correct	82 ms	14144 KB	Output is correct
12	Correct	52 ms	14928 KB	Output is correct
13	Correct	22 ms	4696 KB	Output is correct
14	Correct	816 ms	10724 KB	Output is correct
15	Correct	111 ms	15104 KB	Output is correct
16	Correct	120 ms	15332 KB	Output is correct
17	Correct	1532 ms	15628 KB	Output is correct
18	Correct	74 ms	15124 KB	Output is correct
19	Correct	59 ms	15120 KB	Output is correct
20	Correct	1474 ms	15608 KB	Output is correct
21	Correct	144 ms	10936 KB	Output is correct
22	Correct	23 ms	10952 KB	Output is correct
23	Correct	4 ms	4440 KB	Output is correct
24	Correct	8 ms	4440 KB	Output is correct
25	Correct	9 ms	4440 KB	Output is correct
26	Correct	10 ms	4676 KB	Output is correct
27	Correct	7 ms	4440 KB	Output is correct
28	Correct	4 ms	4376 KB	Output is correct
29	Incorrect	13 ms	4444 KB	Output isn't correct
30	Halted	0 ms	0 KB	-