QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#268063 | #5458. Shortest Path Query | ngpin04 | TL | 1ms | 3420kb | C++14 | 2.7kb | 2023-11-28 01:01:38 | 2023-11-28 01:01:39 |
Judging History
answer
#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define bit(n) (1LL << (n))
#define getbit(x, i) (((x) >> (i)) & 1)
#define pii pair<int, int>
#define ALL(x) x.begin(), x.end()
using namespace std;
const int M = 5e5 + 5;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int oo = 1e9;
const long long ooo = 1e18;
const double pi = acos(-1);
template<typename T1, typename T2> bool mini(T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}
typedef long long ll;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("file.inp", "r",stdin);
#endif
int n,m;
cin >> n >> m;
vector <vector <pair <int, int>>> adj(n);
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
u--, v--;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
int q; cin >> q;
vector <vector <tuple <int, int, int>>> qr(n);
for (int i = 0; i < q; i++) {
int a, b, x;
cin >> a >> b >> x;
x--;
qr[x].push_back({a, b, i});
}
const int mod = 1005;
vector <vector <pair <int, int>>> points(1005);
vector <int> ans(q);
points[0].push_back({0, 0});
auto convex = [&](vector <pair <int, int>> &p) {
sort(ALL(p));
vector <pair <int, int>> res;
int sz = 0;
for (auto [x, y] : p) {
while (sz >= 2) {
int a = res[sz - 1].fi - res[sz - 2].fi;
int b = res[sz - 1].se - res[sz - 2].se;
int u = x - res[sz - 2].fi;
int v = y - res[sz - 2].se;
long long prod = (long long) a * v - (long long) b * u;
if (prod <= 0) {
res.pop_back();
sz--;
}
}
res.push_back({x, y});
}
p = res;
};
for (int i = 0; i < n; i++) {
int j = i % mod;
convex(points[j]);
for (auto [a, b, ind] : qr[i]) {
ans[ind] = 2 * oo;
for (auto [x, y] : points[j])
mini(ans[ind], x * a + y * b);
}
for (auto [k, w] : adj[i]) {
int nxt = k % mod;
for (auto [x, y] : points[j]) {
x += (w == 0);
y += (w == 1);
points[nxt].push_back({x, y});
}
}
points[j].clear();
}
for (int i = 0; i < q; i++)
cout << ans[i] << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3420kb
input:
4 4 1 2 0 1 3 1 2 4 0 3 4 1 3 3 5 2 3 2 4 2 3 4
output:
3 4 4
result:
ok 3 number(s): "3 4 4"
Test #2:
score: -100
Time Limit Exceeded
input:
50000 100000 1 2 1 2 3 0 3 4 1 4 5 0 5 6 1 6 7 0 7 8 1 8 9 1 9 10 0 10 11 1 11 12 1 12 13 1 13 14 0 14 15 0 15 16 0 16 17 0 17 18 1 18 19 1 19 20 0 20 21 1 21 22 0 22 23 0 23 24 1 24 25 1 25 26 0 26 27 1 27 28 0 28 29 0 29 30 0 30 31 0 31 32 1 32 33 0 33 34 1 34 35 1 35 36 1 36 37 1 37 38 0 38 39 0 ...