QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#555894#5102. Dungeon CrawlerevirirWA 0ms3692kbC++201.6kb2024-09-10 11:57:312024-09-10 11:57:32

Judging History

你现在查看的是最新测评结果

  • [2024-09-10 11:57:32]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3692kb
  • [2024-09-10 11:57:31]
  • 提交

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;
}

详细

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'