QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#66099 | #5102. Dungeon Crawler | b4xji4 | TL | 0ms | 0kb | C++ | 2.9kb | 2022-12-06 17:39:41 | 2022-12-06 17:39:42 |
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, time;
std::cin >> u >> v >> time;
E[u].push_back(v);
E[v].push_back(u);
W[u].push_back(time);
W[v].push_back(time);
sum += time;
}
for(int i = 1; i <= n; i++)
{
rt = i;
tim = 0;
dfs(i, i);
}
while(m--)
{
int start, key, trap;
std::cin >> start >> key >> trap;
long long int mx = 0;
if(in(start,key,trap))
{
for(int i = 1; i <= n; i++)
mx = max(mx, dis[start][i]);
std::cout << sum + sum - mx << "\n";
}
else if(in(start,trap,key))
std::cout << "impossible" << "\n";
else
{
int o = lca(start,trap,key), oy = key;
while(fa[start][key]^o)
key = fa[start][key];
long long int tmp = 0;
for(int i = 1; i <= n; i++)
{
if(!in(start,key,i))
mx = max(mx, dis[start][i]);
tmp = sum + sum - mx;
int lst = 0;
while(oy^o)
{
tmp = min(tmp, sum+sum-dis[start][oy]+dis[o][oy]*2);
for(auto z : E[oy])
{
if(z^fa[start][oy] && z^lst)
tmp = min(tmp, sum+sum-Mx[start][z]+dis[o][oy]*2);
lst = oy;
oy = fa[start][oy];
}
}
}
std::cout << tmp << "\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
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