QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#66098#5102. Dungeon Crawlerb4xji4TL 0ms0kbC++142.9kb2022-12-06 17:39:132022-12-06 17:39:14

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 17:39:14]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2022-12-06 17:39:13]
  • 提交

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, 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

output:


result: