// こんな僕等がお互い蹴落として
// まで掴んだ物は何ですか
// 僕は 僕を愛してあげたい
//
// こんなことなら生まれてこなけりゃって
// 全部嫌になってくけれど
// 絶えず 脈打つこれは何だろう
//
// 何だろう...
#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;
// 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
);
}
}
// for (int i = 1; i <= N; i++) debugV(total_cost, i);
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:380:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
380 | scanf("%d %d %d", &N, &M, &K);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:382:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
382 | scanf("%d %d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:388:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
388 | scanf(" %c", &buf);
| ~~~~~^~~~~~~~~~~~~
Main.cpp:391:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
391 | for (int i = 1; i <= N; i++) scanf("%d", &st_pos[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
11612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
13396 KB |
Output is correct |
| 2 |
Correct |
1214 ms |
78024 KB |
Output is correct |
| 3 |
Correct |
1151 ms |
123524 KB |
Output is correct |
| 4 |
Correct |
1166 ms |
123412 KB |
Output is correct |
| 5 |
Correct |
2376 ms |
123736 KB |
Output is correct |
| 6 |
Correct |
800 ms |
123496 KB |
Output is correct |
| 7 |
Correct |
1020 ms |
102468 KB |
Output is correct |
| 8 |
Correct |
1211 ms |
117632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
13396 KB |
Output is correct |
| 2 |
Correct |
1185 ms |
77820 KB |
Output is correct |
| 3 |
Correct |
916 ms |
123384 KB |
Output is correct |
| 4 |
Correct |
1267 ms |
123604 KB |
Output is correct |
| 5 |
Correct |
2757 ms |
123856 KB |
Output is correct |
| 6 |
Correct |
1097 ms |
123392 KB |
Output is correct |
| 7 |
Correct |
942 ms |
123316 KB |
Output is correct |
| 8 |
Correct |
2978 ms |
123840 KB |
Output is correct |
| 9 |
Correct |
355 ms |
34744 KB |
Output is correct |
| 10 |
Correct |
246 ms |
34596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
9820 KB |
Output is correct |
| 2 |
Correct |
32 ms |
13280 KB |
Output is correct |
| 3 |
Correct |
67 ms |
13228 KB |
Output is correct |
| 4 |
Correct |
55 ms |
13392 KB |
Output is correct |
| 5 |
Correct |
38 ms |
11152 KB |
Output is correct |
| 6 |
Correct |
33 ms |
10924 KB |
Output is correct |
| 7 |
Incorrect |
27 ms |
9816 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1231 ms |
123556 KB |
Output is correct |
| 2 |
Correct |
1344 ms |
123516 KB |
Output is correct |
| 3 |
Correct |
1404 ms |
123512 KB |
Output is correct |
| 4 |
Correct |
1351 ms |
123604 KB |
Output is correct |
| 5 |
Correct |
1151 ms |
123516 KB |
Output is correct |
| 6 |
Correct |
1147 ms |
102400 KB |
Output is correct |
| 7 |
Correct |
254 ms |
34604 KB |
Output is correct |
| 8 |
Incorrect |
270 ms |
60752 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1231 ms |
123556 KB |
Output is correct |
| 2 |
Correct |
1344 ms |
123516 KB |
Output is correct |
| 3 |
Correct |
1404 ms |
123512 KB |
Output is correct |
| 4 |
Correct |
1351 ms |
123604 KB |
Output is correct |
| 5 |
Correct |
1151 ms |
123516 KB |
Output is correct |
| 6 |
Correct |
1147 ms |
102400 KB |
Output is correct |
| 7 |
Correct |
254 ms |
34604 KB |
Output is correct |
| 8 |
Incorrect |
270 ms |
60752 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
9820 KB |
Output is correct |
| 2 |
Correct |
32 ms |
13280 KB |
Output is correct |
| 3 |
Correct |
67 ms |
13228 KB |
Output is correct |
| 4 |
Correct |
55 ms |
13392 KB |
Output is correct |
| 5 |
Correct |
38 ms |
11152 KB |
Output is correct |
| 6 |
Correct |
33 ms |
10924 KB |
Output is correct |
| 7 |
Incorrect |
27 ms |
9816 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
11612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
