QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#536684 | #5102. Dungeon Crawler | RngBased# | WA | 0ms | 3596kb | C++20 | 2.4kb | 2024-08-29 15:44:09 | 2024-08-29 15:44:09 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pi3 tuple<int, int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
struct sparse
{
static const int P = 12;
ll n, table[2005][P];
void init(int _n)
{
n = _n;
for (int i = 1; i <= n; i++)
table[i][0] = 0;
}
void set(int p, ll v)
{
table[p][0] = v;
}
void build()
{
for (int p = 0; p + 1 < P; p++)
for (int i = 1; (i + (1 << p)) <= n; i++)
table[i][p + 1] = max(table[i][p], table[i + (1 << p)][p + 1]);
}
ll query(int l, int r)
{
if (r < l) return 0;
int lg = __lg(r - l + 1);
return max(table[l][lg], table[r - (1 << lg) + 1][lg]);
}
} st;
int n, q, vis[2005], t;
ll ans[200005], d[2005], sum;
pii io[2005];
vector<pi3> qs[2005];
vector<pll> E[2005];
void dfs(int u)
{
io[u].F = ++t;
vis[u] = 1;
for (auto [v, w] : E[u])
if (!vis[v])
{
d[v] = d[u] + w;
dfs(v);
}
io[u].S = t;
}
bool is_child(int r, int c)
{
return io[r].F <= io[c].F && io[c].S <= io[r].S;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> q;
for (int i = 1; i < n; i++)
{
int u, v, w;
cin >> u >> v >> w;
E[u].emplace_back(v, w);
E[v].emplace_back(u, w);
sum += 2 * w;
}
for (int i = 1; i <= q; i++)
{
int s, k, t;
cin >> s >> k >> t;
qs[s].emplace_back(k, t, i);
}
for (int r = 1; r <= n; r++)
{
t = 0, d[r] = 0;
fill(vis + 1, vis + 1 + n, 0);
dfs(r);
st.init(n);
for (int i = 1; i <= n; i++)
st.set(io[i].F, d[i]);
st.build();
for (auto [key, trap, i] : qs[r])
{
if (is_child(key, trap))
ans[i] = -st.query(1, n);
else if (is_child(trap, key))
ans[i] = 1;
else
ans[i] = -max(st.query(1, io[key].F - 1), st.query(io[key].S + 1, n));
}
}
for (int i = 1; i <= q; i++)
{
if (ans[i] > 0)
cout << "impossible\n";
else
cout << sum + ans[i] << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3596kb
input:
22 5 1 2 7 2 3 5 3 4 8 3 6 6 3 7 3 2 5 6 5 8 2 8 9 11 2 10 16 1 11 12 11 12 4 11 13 9 1 14 25 14 15 4 15 16 5 15 17 6 15 18 1 15 19 8 14 20 7 20 21 9 20 22 17 1 19 9 1 9 19 1 8 9 1 9 8 2 22 11
output:
301 313 329 impossible 307
result:
wrong answer 1st lines differ - expected: '316', found: '301'