QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#66101 | #5102. Dungeon Crawler | b4xji4 | TL | 0ms | 0kb | C++ | 2.7kb | 2022-12-06 18:05:34 | 2022-12-06 18:05:37 |
Judging History
answer
#include<bits/stdc++.h>
#define re register
#define ll long long
using namespace std;
inline int read(){
re int t=0;re char v=getchar();
while(v<'0')v=getchar();
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
return t;
}
const int M=998244353;
inline void add(re int &x,re int y){(x+=y)>=M?x-=M:x;}
inline int Mod(re int x){return x>=M?x-M:x;}
inline int ksm(re int x,re int y){
re int s=1;
while(y){
if(y&1)s=1ll*s*x%M;
x=1ll*x*x%M,y>>=1;
}
return s;
}
vector<int>E[2002],W[2002];
int dfn[2002][2002],n,m,siz[2002][2002],rt,fa[2002][2002],tim;
ll dis[2002][2002],sum,Mx[2002][2002];
inline void dfs(re int x,re int y){
siz[rt][x]=1,dfn[rt][x]=++tim,fa[rt][x]=y,Mx[rt][x]=dis[rt][x];
for(re int i=0;i<E[x].size();++i)
if(E[x][i]^y){
dis[rt][E[x][i]]=dis[rt][x]+W[x][i];
dfs(E[x][i],x);
siz[rt][x]+=siz[rt][E[x][i]];
Mx[rt][x]=max(Mx[rt][x],Mx[rt][E[x][i]]);
}
}
inline bool in(re int x,re int y,re int z){
return dfn[x][z]>=dfn[x][y]&&dfn[x][z]<dfn[x][y]+siz[x][y];
}
inline int lca(re int x,re int y,re int z){
while(y^z){
if(dfn[x][y]>dfn[x][z])y=fa[x][y];
else z=fa[x][z];
}
return y;
}
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 0; m = 0;
std::cin >> n >> m;
for(int i = 1; i < n; i++)
{
int u, v, w;
std::cin >> u >> v >> w;
E[u].push_back(v), E[v].push_back(u);
W[u].push_back(w), W[v].push_back(w);
sum += w;
}
for(int i = 1; i <= n; i++)
{
rt = i, tim = 0;
dfs(i,i);
}
while(m--)
{
int s, k, t;
std::cin >> s >> k >> t;
ll mx = 0;
if(in(s,k,t))
{
for(int i = 1; i <= n; i++)
mx = max(mx, dis[s][i]);
printf("%lld\n", sum+sum-mx);
}
else if(in(s,t,k))
puts("impossible");
else
{
int o = lca(s,t,k), oy = k;
while(fa[s][k]^o)
k = fa[s][k];
for(int i = 1; i <= n; i++)
{
if(!(in(s,k,i)))
mx = max(mx, dis[s][i]);
ll tmp = sum+sum-mx;
int lst = 0;
while(oy^o)
{
tmp = min(tmp, sum+sum-dis[s][oy]+dis[o][oy]*2);
for(auto z : E[oy])
{
if(z^fa[s][oy] && z^lst)
tmp = min(tmp, sum+sum-Mx[s][z]+dis[o][oy]*2);
lst = oy;
oy = fa[s][oy];
}
}
printf("%lld\n", tmp);
}
}
}
}
詳細信息
Test #1:
score: 0
Time Limit Exceeded
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