QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#390069 | #5102. Dungeon Crawler | 0_GB_RAM# | WA | 1ms | 7960kb | C++23 | 2.5kb | 2024-04-15 02:00:20 | 2024-04-15 02:00:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define int ll
#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())
using pii=pair<int,int>;
using vi=vector<int>;
#define fi first
#define se second
#define pb push_back
const int N=2010,L=12;
vector<pii> g[N];
struct Tree
{
int par[N][L];
int dep1[N],depw[N];
int longest[N];
int best[N];
void dfs(int v,int p,int d1,int dw)
{
dep1[v]=d1;
depw[v]=dw;
par[v][0]=p;
for(int i=1;i<L;i++)
par[v][i]=par[par[v][i-1]][i-1];
int lon1=depw[v],lon2=0;
for(auto[to,w]:g[v])
if(to!=p) {
dfs(to, v, d1 + 1, dw + w);
lon2 = max(lon2, longest[to]);
if(lon2>lon1)
swap(lon1,lon2);
}
longest[v]=lon1;
for(auto[to,w]:g[v])
if(to!=p) {
if(longest[to]==lon1)
best[to]=lon2-2*depw[v];
else
best[to]=lon1-2*depw[v];
best[to]=max(best[to],best[v]);
}
}
int lca(int v,int u)
{
if(dep1[v]>dep1[u])
swap(v,u);
for(int i=L-1;i>=0;i--)
if(dep1[par[u][i]]>=dep1[v])
u=par[u][i];
if(u==v)
return u;
for(int i=L-1;i>=0;i--)
if(par[u][i]!=par[v][i])
u=par[u][i],
v=par[v][i];
return par[u][0];
}
} trees[N];
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int n,q;
cin>>n>>q;
int sum=0;
for(int i=1;i<=n-1;i++)
{
int u,v,w;
cin>>u>>v>>w;
g[u].pb({v,w});
g[v].pb({u,w});
sum+=w;
}
for(int i=1;i<=n;i++) {
trees[i].dfs(i, i, 0, 0);
// cout<<i<<": ";
// for(int j=1;j<=n;j++)
// cout<<trees[i].longest[j]<<" ";
// cout<<i<<": ";
// for(int j=1;j<=n;j++)
// cout<<trees[i].best[j]<<" ";
// cout<<"\n";
}
while(q--)
{
int s,k,t;
cin>>s>>k>>t;
auto&tree=trees[t];
if(tree.lca(s,k)==t)
cout<<"impossible\n";
else {
int ans = sum * 2 - tree.depw[s];
int best = max(tree.best[s], tree.best[k]);
// cout<<ans<<" "<<best<<"\n";
cout << ans - best << "\n";
}
}
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 7960kb
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 316 impossible 286
result:
wrong answer 3rd lines differ - expected: '293', found: '316'