QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#369752 | #6306. Chase Game | ucup-team1191# | WA | 1ms | 3620kb | C++20 | 4.4kb | 2024-03-28 17:30:00 | 2024-03-28 17:30:02 |
Judging History
answer
/*
author: Maksim1744
created: 28.03.2024 12:17:44
*/
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define sum(a) ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a) (*min_element((a).begin(), (a).end()))
#define maxe(a) (*max_element((a).begin(), (a).end()))
#define mini(a) ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a) ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
template<typename T> vector<T>& operator-- (vector<T> &v){for (auto& i : v) --i; return v;}
template<typename T> vector<T>& operator++ (vector<T> &v){for (auto& i : v) ++i; return v;}
template<typename T> istream& operator>>(istream& is, vector<T> &v){for (auto& i : v) is >> i; return is;}
template<typename T> ostream& operator<<(ostream& os, vector<T> v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator-- (pair<T, U> &p){--p.first; --p.second; return p;}
template<typename T, typename U> pair<T,U>& operator++ (pair<T, U> &p){++p.first; ++p.second; return p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second; return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U> p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}
#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun) fun
#define debugv(var) var
#define mclock void(0)
#define shows void(0)
#define debug if (false)
#define OSTREAM(...) ;
#define OSTREAM0(...) ;
#endif
template<typename T>
using pq = priority_queue<T, vector<T>, greater<T>>;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, m, k, d;
cin >> n >> m >> k >> d;
--k;
vector<vector<int>> g(n);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
--u; --v;
g[u].push_back(v);
g[v].push_back(u);
}
auto bfs = [&](int v) {
vector<int> d(n, 1e9);
d[v] = 0;
queue<int> q;
q.push(v);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int k : g[v]) {
if (d[k] > d[v] + 1) {
d[k] = d[v] + 1;
q.push(k);
}
}
}
return d;
};
auto cost = bfs(k);
for (int& x : cost)
x = max(0, d - x);
show(cost);
vector<bool> covered(n);
covered[0] = true;
for (int i = 0; i < n; ++i) {
if (cost[i] > 0)
covered[i] = true;
}
auto fin = bfs(n - 1);
vector<ll> path_cost(n + 5, 0);
for (int i = 1; i < path_cost.size(); ++i) {
path_cost[i] = path_cost[i - 1] + d - (i - 1) % d;
}
show(path_cost);
ll ans = 1e18;
pq<pair<ll, int>> q;
vector<ll> dist(n, 1e18);
q.emplace(cost[0], 0);
dist[0] = cost[0];
while (!q.empty()) {
auto [dd, v] = q.top();
q.pop();
if (dd != dist[v]) continue;
if (!covered[v]) {
show(v, dd, fin[v]);
ans = min(ans, dd + path_cost[fin[v] + 1]);
show(ans);
continue;
}
for (int k : g[v]) {
if (dist[v] + cost[k] < dist[k]) {
dist[k] = dist[v] + cost[k];
q.emplace(dist[k], k);
}
}
}
if (covered[n - 1])
ans = min(ans, dist[n - 1]);
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3620kb
input:
5 5 3 1 1 2 2 4 4 5 1 3 3 5
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
13 17 12 3 1 2 2 3 3 4 4 13 5 13 7 8 7 9 7 10 7 11 7 6 12 7 1 8 8 9 9 10 10 11 11 6 6 13
output:
7
result:
ok 1 number(s): "7"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3544kb
input:
10 9 4 1 4 3 1 2 7 6 6 5 8 9 9 10 5 4 8 7 3 2
output:
9
result:
ok 1 number(s): "9"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3500kb
input:
10 20 9 1 9 5 2 9 4 5 10 5 7 3 1 8 7 1 7 5 3 4 3 1 7 8 3 8 9 3 10 6 9 1 1 6 8 5 6 2 1 10 2 1
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
10 20 3 1 1 4 6 7 5 4 5 3 2 1 8 1 7 8 2 6 2 4 4 8 9 5 1 10 7 4 5 8 4 10 2 5 6 10 4 6 3 7 1 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
10 20 4 1 2 7 6 4 2 3 2 4 6 5 8 5 6 7 10 2 3 10 1 8 3 9 3 7 1 7 5 1 6 1 3 4 2 1 5 2 9 2 9 10
output:
2
result:
ok 1 number(s): "2"
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 3588kb
input:
10 20 1 10 10 9 2 5 7 8 7 10 10 8 8 9 5 6 3 1 6 4 7 9 2 3 3 6 2 1 8 6 5 8 7 4 4 3 2 4 4 1 9 6
output:
34
result:
wrong answer 1st numbers differ - expected: '24', found: '34'