oj.uz

답안 #1074178

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1074178 2024-08-25T08:36:17 Z Zanite Board Game (JOI24_boardgame) C++17
49 / 100
 1127 ms 14700 KB 
// こんな僕等がお互い蹴落として
// まで掴んだ物は何ですか
// 僕は　僕を愛してあげたい
// 
// こんなことなら生まれてこなけりゃって
// 全部嫌になってくけれど
// 絶えず　脈打つこれは何だろう
// 
// 何だろう...

#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, ll s) {
   // {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 : 0) + 1;
         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;
      for (auto nxt : board[cur]) {
         bool stop_state = (state[cur] && cur != st_pos[1]);
         if (stop_state) continue;
         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;
      // 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
      int hl = 1, hr = N, sw_pos = N+1;
      while (hl <= hr) {
         int hm = (hl + hr) / 2;
         ll cost_single = 2ll * hm + c_single;
         ll cost_double = hm + c_double;

         if (cost_double <= cost_single) {
            sw_pos = hm;
            hr = hm - 1;
         } else {
            hl = hm + 1;
         }
      }
      // debug(c_single, c_double, sw_pos);

      for (int i = 1; i < sw_pos; i++) total_cost[i] += 2ll * i + c_single;
      for (int i = sw_pos; i <= N; i++) total_cost[i] += i + c_double;
   }

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

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

   for (auto [l, s] : lines) linear_dijkstra(l.fi, l.se, s);

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

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 4952 KB Output is correct
2 Correct 358 ms 10420 KB Output is correct
3 Correct 1127 ms 14520 KB Output is correct
4 Correct 38 ms 14220 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 4952 KB Output is correct
2 Correct 441 ms 10348 KB Output is correct
3 Correct 49 ms 14192 KB Output is correct
4 Correct 48 ms 14004 KB Output is correct
5 Correct 880 ms 14700 KB Output is correct
6 Correct 60 ms 14220 KB Output is correct
7 Correct 45 ms 13372 KB Output is correct
8 Correct 45 ms 13808 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 5208 KB Output is correct
2 Correct 412 ms 10368 KB Output is correct
3 Correct 61 ms 14252 KB Output is correct
4 Correct 102 ms 14076 KB Output is correct
5 Correct 812 ms 14440 KB Output is correct
6 Correct 51 ms 14252 KB Output is correct
7 Correct 52 ms 14248 KB Output is correct
8 Correct 763 ms 14428 KB Output is correct
9 Correct 62 ms 10972 KB Output is correct
10 Correct 22 ms 11040 KB Output is correct

Subtask #4
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 5 ms 4952 KB Output is correct
3 Correct 6 ms 4952 KB Output is correct
4 Correct 7 ms 4956 KB Output is correct
5 Correct 4 ms 4920 KB Output is correct
6 Correct 3 ms 4700 KB Output is correct
7 Incorrect 6 ms 4700 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 14296 KB Output is correct
2 Correct 60 ms 14140 KB Output is correct
3 Correct 54 ms 14284 KB Output is correct
4 Correct 49 ms 14288 KB Output is correct
5 Correct 85 ms 14152 KB Output is correct
6 Correct 38 ms 13376 KB Output is correct
7 Correct 24 ms 11096 KB Output is correct
8 Correct 25 ms 9584 KB Output is correct
9 Correct 36 ms 9736 KB Output is correct
10 Correct 64 ms 13304 KB Output is correct
11 Correct 42 ms 13444 KB Output is correct
12 Correct 80 ms 13884 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 14296 KB Output is correct
2 Correct 60 ms 14140 KB Output is correct
3 Correct 54 ms 14284 KB Output is correct
4 Correct 49 ms 14288 KB Output is correct
5 Correct 85 ms 14152 KB Output is correct
6 Correct 38 ms 13376 KB Output is correct
7 Correct 24 ms 11096 KB Output is correct
8 Correct 25 ms 9584 KB Output is correct
9 Correct 36 ms 9736 KB Output is correct
10 Correct 64 ms 13304 KB Output is correct
11 Correct 42 ms 13444 KB Output is correct
12 Correct 80 ms 13884 KB Output is correct
13 Correct 63 ms 14152 KB Output is correct
14 Correct 77 ms 14312 KB Output is correct
15 Correct 167 ms 14204 KB Output is correct
16 Correct 145 ms 14144 KB Output is correct
17 Correct 44 ms 13368 KB Output is correct
18 Correct 156 ms 13512 KB Output is correct
19 Correct 131 ms 13252 KB Output is correct
20 Correct 60 ms 14212 KB Output is correct
21 Correct 26 ms 9756 KB Output is correct
22 Correct 30 ms 9856 KB Output is correct
23 Correct 43 ms 9808 KB Output is correct
24 Correct 63 ms 13464 KB Output is correct
25 Correct 51 ms 13736 KB Output is correct
26 Correct 80 ms 13688 KB Output is correct
27 Correct 39 ms 9888 KB Output is correct
28 Correct 191 ms 9876 KB Output is correct
29 Correct 370 ms 9872 KB Output is correct
30 Correct 61 ms 13760 KB Output is correct
31 Correct 311 ms 13696 KB Output is correct
32 Correct 579 ms 13696 KB Output is correct

Subtask #7
0.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4696 KB Output is correct
2 Correct 5 ms 4952 KB Output is correct
3 Correct 6 ms 4952 KB Output is correct
4 Correct 7 ms 4956 KB Output is correct
5 Correct 4 ms 4920 KB Output is correct
6 Correct 3 ms 4700 KB Output is correct
7 Incorrect 6 ms 4700 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #8
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 4952 KB Output is correct
2 Correct 358 ms 10420 KB Output is correct
3 Correct 1127 ms 14520 KB Output is correct
4 Correct 38 ms 14220 KB Output is correct
5 Correct 12 ms 4952 KB Output is correct
6 Correct 441 ms 10348 KB Output is correct
7 Correct 49 ms 14192 KB Output is correct
8 Correct 48 ms 14004 KB Output is correct
9 Correct 880 ms 14700 KB Output is correct
10 Correct 60 ms 14220 KB Output is correct
11 Correct 45 ms 13372 KB Output is correct
12 Correct 45 ms 13808 KB Output is correct
13 Correct 13 ms 5208 KB Output is correct
14 Correct 412 ms 10368 KB Output is correct
15 Correct 61 ms 14252 KB Output is correct
16 Correct 102 ms 14076 KB Output is correct
17 Correct 812 ms 14440 KB Output is correct
18 Correct 51 ms 14252 KB Output is correct
19 Correct 52 ms 14248 KB Output is correct
20 Correct 763 ms 14428 KB Output is correct
21 Correct 62 ms 10972 KB Output is correct
22 Correct 22 ms 11040 KB Output is correct
23 Correct 3 ms 4696 KB Output is correct
24 Correct 5 ms 4952 KB Output is correct
25 Correct 6 ms 4952 KB Output is correct
26 Correct 7 ms 4956 KB Output is correct
27 Correct 4 ms 4920 KB Output is correct
28 Correct 3 ms 4700 KB Output is correct
29 Incorrect 6 ms 4700 KB Output isn't correct
30 Halted 0 ms 0 KB -