Submission #1074194

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1074194	2024-08-25T08:46:18 Z	Zanite	Board Game (JOI24_boardgame)	C++17	49 / 100	2039 ms	16088 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;

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];

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

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

   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);

   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:306:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  306 |    scanf("%d %d %d", &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("%d %d", &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:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  317 |    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	11 ms	4956 KB	Output is correct
2	Correct	729 ms	11100 KB	Output is correct
3	Correct	2039 ms	16020 KB	Output is correct
4	Correct	46 ms	15508 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	4952 KB	Output is correct
2	Correct	737 ms	11136 KB	Output is correct
3	Correct	55 ms	15652 KB	Output is correct
4	Correct	51 ms	15656 KB	Output is correct
5	Correct	1615 ms	15948 KB	Output is correct
6	Correct	57 ms	15568 KB	Output is correct
7	Correct	47 ms	14328 KB	Output is correct
8	Correct	47 ms	15080 KB	Output is correct

Subtask #3

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	4956 KB	Output is correct
2	Correct	733 ms	11088 KB	Output is correct
3	Correct	72 ms	15640 KB	Output is correct
4	Correct	124 ms	15580 KB	Output is correct
5	Correct	1366 ms	16088 KB	Output is correct
6	Correct	61 ms	15644 KB	Output is correct
7	Correct	77 ms	15384 KB	Output is correct
8	Correct	1372 ms	16088 KB	Output is correct
9	Correct	96 ms	11380 KB	Output is correct
10	Correct	23 ms	11028 KB	Output is correct

Subtask #4

0.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4700 KB	Output is correct
2	Correct	6 ms	4956 KB	Output is correct
3	Correct	5 ms	4956 KB	Output is correct
4	Correct	6 ms	4952 KB	Output is correct
5	Correct	5 ms	4700 KB	Output is correct
6	Correct	4 ms	4700 KB	Output is correct
7	Incorrect	7 ms	4700 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	56 ms	15380 KB	Output is correct
2	Correct	59 ms	15520 KB	Output is correct
3	Correct	44 ms	15656 KB	Output is correct
4	Correct	50 ms	15436 KB	Output is correct
5	Correct	76 ms	15504 KB	Output is correct
6	Correct	46 ms	14400 KB	Output is correct
7	Correct	25 ms	11336 KB	Output is correct
8	Correct	25 ms	10224 KB	Output is correct
9	Correct	26 ms	10344 KB	Output is correct
10	Correct	44 ms	14272 KB	Output is correct
11	Correct	43 ms	14284 KB	Output is correct
12	Correct	67 ms	15144 KB	Output is correct

Subtask #6

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	15380 KB	Output is correct
2	Correct	59 ms	15520 KB	Output is correct
3	Correct	44 ms	15656 KB	Output is correct
4	Correct	50 ms	15436 KB	Output is correct
5	Correct	76 ms	15504 KB	Output is correct
6	Correct	46 ms	14400 KB	Output is correct
7	Correct	25 ms	11336 KB	Output is correct
8	Correct	25 ms	10224 KB	Output is correct
9	Correct	26 ms	10344 KB	Output is correct
10	Correct	44 ms	14272 KB	Output is correct
11	Correct	43 ms	14284 KB	Output is correct
12	Correct	67 ms	15144 KB	Output is correct
13	Correct	55 ms	15580 KB	Output is correct
14	Correct	67 ms	15440 KB	Output is correct
15	Correct	169 ms	15532 KB	Output is correct
16	Correct	133 ms	15504 KB	Output is correct
17	Correct	46 ms	14408 KB	Output is correct
18	Correct	144 ms	14428 KB	Output is correct
19	Correct	135 ms	13960 KB	Output is correct
20	Correct	73 ms	15608 KB	Output is correct
21	Correct	27 ms	10404 KB	Output is correct
22	Correct	34 ms	10588 KB	Output is correct
23	Correct	36 ms	10668 KB	Output is correct
24	Correct	46 ms	14596 KB	Output is correct
25	Correct	53 ms	15140 KB	Output is correct
26	Correct	69 ms	15076 KB	Output is correct
27	Correct	50 ms	10792 KB	Output is correct
28	Correct	168 ms	10780 KB	Output is correct
29	Correct	311 ms	10640 KB	Output is correct
30	Correct	62 ms	15132 KB	Output is correct
31	Correct	298 ms	15088 KB	Output is correct
32	Correct	545 ms	15284 KB	Output is correct

Subtask #7

0.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4700 KB	Output is correct
2	Correct	6 ms	4956 KB	Output is correct
3	Correct	5 ms	4956 KB	Output is correct
4	Correct	6 ms	4952 KB	Output is correct
5	Correct	5 ms	4700 KB	Output is correct
6	Correct	4 ms	4700 KB	Output is correct
7	Incorrect	7 ms	4700 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	11 ms	4956 KB	Output is correct
2	Correct	729 ms	11100 KB	Output is correct
3	Correct	2039 ms	16020 KB	Output is correct
4	Correct	46 ms	15508 KB	Output is correct
5	Correct	11 ms	4952 KB	Output is correct
6	Correct	737 ms	11136 KB	Output is correct
7	Correct	55 ms	15652 KB	Output is correct
8	Correct	51 ms	15656 KB	Output is correct
9	Correct	1615 ms	15948 KB	Output is correct
10	Correct	57 ms	15568 KB	Output is correct
11	Correct	47 ms	14328 KB	Output is correct
12	Correct	47 ms	15080 KB	Output is correct
13	Correct	11 ms	4956 KB	Output is correct
14	Correct	733 ms	11088 KB	Output is correct
15	Correct	72 ms	15640 KB	Output is correct
16	Correct	124 ms	15580 KB	Output is correct
17	Correct	1366 ms	16088 KB	Output is correct
18	Correct	61 ms	15644 KB	Output is correct
19	Correct	77 ms	15384 KB	Output is correct
20	Correct	1372 ms	16088 KB	Output is correct
21	Correct	96 ms	11380 KB	Output is correct
22	Correct	23 ms	11028 KB	Output is correct
23	Correct	3 ms	4700 KB	Output is correct
24	Correct	6 ms	4956 KB	Output is correct
25	Correct	5 ms	4956 KB	Output is correct
26	Correct	6 ms	4952 KB	Output is correct
27	Correct	5 ms	4700 KB	Output is correct
28	Correct	4 ms	4700 KB	Output is correct
29	Incorrect	7 ms	4700 KB	Output isn't correct
30	Halted	0 ms	0 KB	-