QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#66101#5102. Dungeon Crawlerb4xji4TL 0ms0kbC++2.7kb2022-12-06 18:05:342022-12-06 18:05:37

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-06 18:05:37]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2022-12-06 18:05:34]
  • 提交

answer

#include<bits/stdc++.h>
#define re register
#define ll long long
using namespace std;
inline int read(){
	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];
int dfn[2002][2002],n,m,siz[2002][2002],rt,fa[2002][2002],tim;
ll dis[2002][2002],sum,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){
	while(y^z){
		if(dfn[x][y]>dfn[x][z])y=fa[x][y];
		else z=fa[x][z];
	}
	return y;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n = 0; m = 0; 
    std::cin >> n >> m;
    for(int i = 1; i < n; i++)
    {
        int u, v, w;
        std::cin >> u >> v >> w;
        E[u].push_back(v), E[v].push_back(u);
        W[u].push_back(w), W[v].push_back(w);
        sum += w;
    }
    for(int i = 1; i <= n; i++)
    {
        rt = i, tim = 0;
        dfs(i,i);
    }
    while(m--)
    {
        int s, k, t;
        std::cin >> s >> k >> t;
        ll mx = 0;
        if(in(s,k,t))
        {
            for(int i = 1; i <= n; i++)
                mx = max(mx, dis[s][i]);
            printf("%lld\n", sum+sum-mx);
        }
        else if(in(s,t,k))
            puts("impossible");
        else
        {
            int o = lca(s,t,k), oy = k;
            while(fa[s][k]^o)
                k = fa[s][k];
            for(int i = 1; i <= n; i++)
            {
                if(!(in(s,k,i)))
                    mx = max(mx, dis[s][i]);
                ll tmp = sum+sum-mx;
                int lst = 0;
                while(oy^o)
                {
                    tmp = min(tmp, sum+sum-dis[s][oy]+dis[o][oy]*2);
                    for(auto z : E[oy])
                    {
                        if(z^fa[s][oy] && z^lst)
                            tmp = min(tmp, sum+sum-Mx[s][z]+dis[o][oy]*2);
                        lst = oy;
                        oy = fa[s][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

output:


result: