QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#392074 | #5102. Dungeon Crawler | nocriz | WA | 1ms | 3796kb | C++14 | 2.3kb | 2024-04-17 06:11:03 | 2024-04-17 06:11:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
int n, q;
vector<pii> G[2020];
vector<pair<pii, int>> query[2020];
int cd = 0;
ll dist[2020], md[2020];
int dfn[2020], sz[2020], ff[2020], depth[2020];
ll ans[200020];
ll tot = 0;
int root;
void dfs(int s, int fa = -1) {
cd += 1;
ff[s] = fa;
dfn[s] = cd;
sz[s] = 1;
md[s] = dist[s];
for(auto ct: G[s]) {
if(ct.first == fa) continue;
dist[ct.first] = dist[s] + ct.second;
depth[ct.first] = depth[s] + 1;
dfs(ct.first, s);
md[s] = max(md[s], md[ct.first]);
sz[s] += sz[ct.first];
}
}
bool isin(int a, int b) {
return dfn[a] >= dfn[b] && dfn[a] < dfn[b]+sz[b];
}
ll solve(int t, int k) {
if(isin(t, k)) {
return tot*2 - md[root];
}
if(isin(k, t)) {
return -1;
}
int ct = t, ck = k;
while(ff[ct] != ff[ck]) {
if(depth[ct] > depth[ck]) ct = ff[ct];
else ck = ff[ck];
}
int lca = ff[ct];
ll ans = 1e18;
ans = min(ans, tot*2 - md[k] + 2*(dist[k]-dist[lca]));
int cp = k;
while(cp != root) {
int cf = ff[cp];
if(depth[cf] >= depth[lca]) {
for(auto cta: G[cf]) {
int ct = cta.first;
if(ct == cp) continue;
ans = min(ans, tot*2 - md[ct] + 2*(dist[cf]-dist[lca]));
}
} else {
for(auto cta: G[cf]) {
int ct = cta.first;
if(ct == cp) continue;
ans = min(ans, tot*2 - md[ct]);
}
}
cp = cf;
}
return ans;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
cin>>n>>q;
for(int i=1;i<n;i++) {
int u, v, w;
cin>>u>>v>>w;
tot += w;
G[u].push_back(make_pair(v, w));
G[v].push_back(make_pair(u, w));
}
for(int i=0;i<q;i++) {
int s, k, t;
cin>>s>>k>>t;
query[s].push_back(make_pair(make_pair(k, t), i));
}
for(int i=1;i<=n;i++) {
cd = 0;
memset(dfn, 0, sizeof(dfn));
memset(dist, 0, sizeof(dist));
memset(depth, 0, sizeof(depth));
root = i;
dfs(i);
for(auto cq: query[i]) {
int k = cq.first.first, t = cq.first.second, id = cq.second;
ans[id] = solve(t, k);
}
}
for(int i=0;i<q;i++) {
if(ans[i] == -1){
cout<<"impossible\n";
} else {
cout<<ans[i]<<'\n';
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3796kb
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:
316 293 293 impossible 286
result:
wrong answer 5th lines differ - expected: '314', found: '286'