QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#390069#5102. Dungeon Crawler0_GB_RAM#WA 1ms7960kbC++232.5kb2024-04-15 02:00:202024-04-15 02:00:20

Judging History

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

  • [2024-04-15 02:00:20]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7960kb
  • [2024-04-15 02:00:20]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
#define int ll
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define all(x) begin(x),end(x)
#define sz(x) (int)((x).size())
using pii=pair<int,int>;
using vi=vector<int>;
#define fi first
#define se second
#define pb push_back

const int N=2010,L=12;

vector<pii> g[N];

struct Tree
{
    int par[N][L];
    int dep1[N],depw[N];
    int longest[N];
    int best[N];
    void dfs(int v,int p,int d1,int dw)
    {
        dep1[v]=d1;
        depw[v]=dw;
        par[v][0]=p;
        for(int i=1;i<L;i++)
            par[v][i]=par[par[v][i-1]][i-1];
        int lon1=depw[v],lon2=0;
        for(auto[to,w]:g[v])
            if(to!=p) {
                dfs(to, v, d1 + 1, dw + w);
                lon2 = max(lon2, longest[to]);
                if(lon2>lon1)
                    swap(lon1,lon2);
            }
        longest[v]=lon1;
        for(auto[to,w]:g[v])
            if(to!=p) {
                if(longest[to]==lon1)
                    best[to]=lon2-2*depw[v];
                else
                    best[to]=lon1-2*depw[v];
                best[to]=max(best[to],best[v]);
            }
    }
    int lca(int v,int u)
    {
        if(dep1[v]>dep1[u])
            swap(v,u);
        for(int i=L-1;i>=0;i--)
            if(dep1[par[u][i]]>=dep1[v])
                u=par[u][i];
        if(u==v)
            return u;
        for(int i=L-1;i>=0;i--)
            if(par[u][i]!=par[v][i])
                u=par[u][i],
                v=par[v][i];
        return par[u][0];
    }
} trees[N];

signed main() {
	cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int n,q;
    cin>>n>>q;
    int sum=0;
    for(int i=1;i<=n-1;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        g[u].pb({v,w});
        g[v].pb({u,w});
        sum+=w;
    }
    for(int i=1;i<=n;i++) {
        trees[i].dfs(i, i, 0, 0);
//        cout<<i<<": ";
//        for(int j=1;j<=n;j++)
//            cout<<trees[i].longest[j]<<" ";
//        cout<<i<<": ";
//        for(int j=1;j<=n;j++)
//            cout<<trees[i].best[j]<<" ";
//        cout<<"\n";
    }
    while(q--)
    {
        int s,k,t;
        cin>>s>>k>>t;
        auto&tree=trees[t];
        if(tree.lca(s,k)==t)
            cout<<"impossible\n";
        else {
            int ans = sum * 2 - tree.depw[s];
            int best = max(tree.best[s], tree.best[k]);
//            cout<<ans<<" "<<best<<"\n";
            cout << ans - best << "\n";
        }
    }
}

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 7960kb

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:

316
293
316
impossible
286

result:

wrong answer 3rd lines differ - expected: '293', found: '316'