QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#66096#5102. Dungeon Crawlerb4xji4TL 0ms0kbC++142.9kb2022-12-06 17:35:182022-12-06 17:35:19

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

answer

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

const int M = 998244353;
inline void add(int &x, int &y) {(x+=y) >= M ? x-=M : x;}
inline int Mod(int x) {return x >= M ? x-M : x;}
inline int ksm(int x, int y)
{
    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;
long long int dis[2002][2002], sum, Mx[2002][2002];

inline void dfs(int x, int y)
{
    siz[rt][x] = 1;
    dfn[rt][x] = ++tim;
    fa[rt][x] = y;
    Mx[rt][x] = dis[rt][x];
    
    for(int i = 1; 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(int x, int y, int z)
{
    return dfn[x][z] >= dfn[x][y] && dfn[x][z] < dfn[x][y] + siz[x][y];
}
inline int lca(int x, int y, 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()
{
    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";
        }
    }
}

详细

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: