QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#291293 | #5458. Shortest Path Query | ngpin04 | WA | 315ms | 14972kb | C++20 | 2.9kb | 2023-12-26 10:21:07 | 2023-12-26 10:21:08 |
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;
assert(v - u <= 1000);
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--;
} else
break;
}
res.push_back({x, y});
sz++;
}
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])
if (mini(ans[ind], x * a + y * b) && n >= 100 && ind == 0)
cout << i << " " << ans[ind] << " " << x << " " << a << " " << y << " " << b << "\n";
}
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3464kb
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
Wrong Answer
time: 315ms
memory: 14972kb
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 ...
output:
49999 2673460 59 5190 557 4250 49999 2661650 60 5190 553 4250 49999 2638970 63 5190 544 4250 49999 2509880 102 5190 466 4250 49999 2487650 110 5190 451 4250 49999 2475350 115 5190 442 4250 49999 2466360 119 5190 435 4250 49999 2451690 126 5190 423 4250 49999 2446010 129 5190 418 4250 49999 2434160 1...
result:
wrong answer 1st numbers differ - expected: '164602050', found: '49999'