QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#555894 | #5102. Dungeon Crawler | evirir | WA | 0ms | 3692kb | C++20 | 1.6kb | 2024-09-10 11:57:31 | 2024-09-10 11:57:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define F first
#define S second
#define pb push_back
using ll = long long;
using ii = pair<ll, ll>;
using ld = long double;
template<class T> void amax(T& x, T y){ x = max(x, y); }
template<class T> void amin(T& x, T y){ x = min(x, y); }
static constexpr int MAXN = 2005;
int n,Q;
vector<ii> adj[MAXN];
ll dep[MAXN];
bool ok = 1;
bool ksubt = 0;
ll sumw = 0;
ll mx = 0;
void dfs(int u, int p, int k, int t, bool subt, bool subk)
{
if (subt && u == k) ok = 0;
if (subk && u == t) ksubt = 1;
subt |= u == t;
subk |= u == k;
if (!subk) amax(mx, dep[u]);
for (const auto& [v, w] : adj[u])
{
if (v == p) continue;
dep[v] = dep[u] + w;
dfs(v, u, k, t, subt, subk);
}
}
void solve(int s, int k, int t)
{
dep[s] = 0;
mx = 0;
ok = 1;
ksubt = 0;
dfs(s, -1, k, t, 0, 0);
if (!ok)
{
cout<<"impossible\n";
return;
}
if (ksubt)
{
mx = 0;
forn(i,0,n) mx = max(mx, dep[i]);
}
cout << 2 * sumw - mx << '\n';
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin>>n>>Q;
forn(i,0,n-1)
{
int u,v; ll w; cin>>u>>v>>w; u--; v--;
adj[u].pb({v, w});
adj[v].pb({u, w});
sumw += w;
}
forn(z,0,Q)
{
int s,k,t; cin>>s>>k>>t; s--; k--; t--;
solve(s, k, t);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3692kb
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:
293 293 293 impossible 294
result:
wrong answer 1st lines differ - expected: '316', found: '293'