QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#66135 | #5102. Dungeon Crawler | b4xji4 | TL | 0ms | 0kb | C++ | 3.2kb | 2022-12-07 00:37:36 | 2022-12-07 00:37:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define re register
#define ll long long
// Path: start -> key -> trap -> finish
// Lowest Common Ancestor + DP
// O(qn)
inline int read() // input
{
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]; // record corridors, time
int rt = 0, tim = 0;
int siz[2002][2002], dfn[2002][2002], fa[2002][2002];
ll dis[2002][2002], 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) // Lowest Common Ancestor
{
while(y^z)
{
if(dfn[x][y] > dfn[x][z])
y = fa[x][y];
else
z = fa[x][z];
}
return y;
}
int rooms = 0, scenarios = 0;
long long int sum = 0;
int main()
{
rooms = read(), scenarios = read();
for(re int i = 1; i < rooms; ++i)
{
re int u = read(), v = read(), time = read();
E[u].push_back(v), E[v].push_back(v);
W[u].push_back(time), W[v].push_back(time);
sum += time;
}
for(re int i = 1; i <= rooms; ++i)
{
rt = i;
tim = 0;
dfs(i,i); // traverse the tree from root = i, dp for each scenario
}
while(scenarios--)
{
re int x = read(), y = read(), z = read();
re ll mx = 0;
if(in(x,y,z))
{
for(re int i = 1; i <= rooms; ++i)
mx = max(mx, dis[x][i]);
printf("%lld\n", sum+sum-mx);
}
else if(in(x,z,y))
puts("impossible");
else
{
re int o = lca(x,z,y), oy = y;
while(fa[x][y]^o) y = fa[x][y];
for(re int i = 1; i <= rooms; ++i)
{
if(!in(x,y,i))
mx = max(mx, dis[x][i]);
}
ll tmp = sum+sum-mx;
int lst = 0;
while(oy^o)
{
tmp = min(tmp, sum+sum-dis[x][oy]+dis[o][oy]*2);
for(auto z : E[oy])
{
if(z^fa[x][oy] && z^lst)
tmp = min(tmp, sum+sum-Mx[x][z]+dis[o][oy]*2);
}
lst = oy, oy = fa[x][oy];
}
printf("%lld\n", tmp);
}
}
}
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