oj.uz

답안 #1074117

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1074117 2024-08-25T08:07:52 Z Zanite Board Game (JOI24_boardgame) C++17
3 / 100
 52 ms 15248 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[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) {
   for (int i = 1; i <= N; i++) tmp_dist[i] = INF;

   vector<bool> vis(N + 1, false);
   priority_queue<pll, vector<pll>, greater<pll>> pyqe;
   tmp_dist[st_pos[1]] = c;
   pyqe.push({c, st_pos[1]});

   while (!pyqe.empty()) {
      int cur = pyqe.top().se; pyqe.pop();
      if (vis[cur]) continue;

      vis[cur] = true;
      for (auto nxt : board[cur]) {
         ll w = ((state[cur] && cur != st_pos[1]) ? m : 0) + 1;
         if (tmp_dist[nxt] > tmp_dist[cur] + w) {
            tmp_dist[nxt] = tmp_dist[cur] + w;
            pyqe.push({tmp_dist[nxt], nxt});
         }
      }
   }

   for (int i = 1; i <= N; i++) chmin(ans[i], tmp_dist[i]);
}

void solve_sub1() {
   for (int i = 1; i <= N; i++) ans[i] = INF;
   ans[st_pos[1]] = 0;

   for (int i = 1; i <= N; i++) {
      for (auto j : board[i]) {
         adj_single[i].push_back({j, 1});
      }
   }
   dijkstra(ans, adj_single);

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

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++) {
   //    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<pll> lines;
   for (int i = 2; i <= N; i++) {
      ll m = total_cost[i] - total_cost[i-1];
      ll c = total_cost[i] - i * m;
      lines.push_back({m, c});
   }
   Uniqueify(lines);
   // debug(lines);

   for (int i = 1; i <= N; i++) ans[i] = INF;
   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]);

   if (count(state+1, state+N+1, true) == 0) {
      solve_sub1();
      exit(0);
   }

   solve();
}

// dibisakan

Compilation message

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

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5980 KB Output is correct
2 Correct 20 ms 9432 KB Output is correct
3 Correct 35 ms 12252 KB Output is correct
4 Correct 30 ms 11732 KB Output is correct

Subtask #2
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 6236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 6236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 15248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 15248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5980 KB Output is correct
2 Correct 20 ms 9432 KB Output is correct
3 Correct 35 ms 12252 KB Output is correct
4 Correct 30 ms 11732 KB Output is correct
5 Incorrect 10 ms 6236 KB Output isn't correct
6 Halted 0 ms 0 KB -