QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#291290 | #5458. Shortest Path Query | ngpin04 | WA | 426ms | 14992kb | C++20 | 2.8kb | 2023-12-26 10:16:59 | 2023-12-26 10:16:59 |
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--;
} 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)
cout << 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: 0ms
memory: 3552kb
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: 426ms
memory: 14992kb
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:
0 0 8372 0 7465 25931 1 632 3 8433 18130 2 632 2 8433 22774 1 2450 4 5081 17512 3 2450 2 5081 14742 2 1545 6 1942 13551 5 1545 3 1942 34638 2 756 6 5521 20343 5 756 3 5521 23931 2 8833 7 895 44140 3 7788 7 2968 78114 3 5094 8 7854 69834 6 5094 5 7854 68872 4 6992 8 5113 54959 3 1486 11 4591 36329 9 ...
result:
wrong answer 1st numbers differ - expected: '164602050', found: '0'