QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#66095 | #5102. Dungeon Crawler | b4xji4 | TL | 0ms | 0kb | C++14 | 2.9kb | 2022-12-06 17:33:19 | 2022-12-06 17:33:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int M = 998244353;
void add(int &x, int &y) {(x+=y) >= M ? x-=M : x;}
int Mod(int x) {return x >= M ? x-M : x;}
int ksm(int x, int y)
{
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;
long long int dis[2002][2002], sum, Mx[2002][2002];
void dfs(int x, int y)
{
siz[rt][x] = 1;
dfn[rt][x] = ++tim;
fa[rt][x] = y;
Mx[rt][x] = dis[rt][x];
for(int i = 1; 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]]);
}
}
}
bool in(int x, int y, int z)
{
return dfn[x][z] >= dfn[x][y] && dfn[x][z] < dfn[x][y] + siz[x][y];
}
int lca(int x, int y, 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()
{
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