QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#66135#5102. Dungeon Crawlerb4xji4TL 0ms0kbC++3.2kb2022-12-07 00:37:362022-12-07 00:37:38

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-07 00:37:38]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2022-12-07 00:37:36]
  • 提交

answer

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

#define re register
#define ll long long

// Path: start -> key -> trap -> finish
// Lowest Common Ancestor + DP
// O(qn)

inline int read() // input
{
    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]; // record corridors, time
int rt = 0, tim = 0;
int siz[2002][2002], dfn[2002][2002], fa[2002][2002];
ll dis[2002][2002], 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) // Lowest Common Ancestor
{
    while(y^z)
    {
        if(dfn[x][y] > dfn[x][z])
            y = fa[x][y];
        else
            z = fa[x][z];
    }
    return y;
}

int rooms = 0, scenarios = 0;
long long int sum = 0;

int main()
{
    rooms = read(), scenarios = read();
    for(re int i = 1; i < rooms; ++i)
    {
        re int u = read(), v = read(), time = read();
        E[u].push_back(v), E[v].push_back(v);
        W[u].push_back(time), W[v].push_back(time);
        sum += time;
    }
    for(re int i = 1; i <= rooms; ++i)
    {
        rt = i;
        tim = 0;
        dfs(i,i); // traverse the tree from root = i, dp for each scenario
    }
    while(scenarios--)
    {
        re int x = read(), y = read(), z = read();
        re ll mx = 0;
        if(in(x,y,z))
        {
            for(re int i = 1; i <= rooms; ++i)
                mx = max(mx, dis[x][i]);
            printf("%lld\n", sum+sum-mx);
        }
        else if(in(x,z,y))
            puts("impossible");
        else
        {
            re int o = lca(x,z,y), oy = y;
            while(fa[x][y]^o) y = fa[x][y];
            for(re int i = 1; i <= rooms; ++i)
            {
                if(!in(x,y,i))
                    mx = max(mx, dis[x][i]);
            }
            ll tmp = sum+sum-mx;
            int lst = 0;
            while(oy^o)
            {
                tmp = min(tmp, sum+sum-dis[x][oy]+dis[o][oy]*2);
                for(auto z : E[oy])
                {
                    if(z^fa[x][oy] && z^lst)
                        tmp = min(tmp, sum+sum-Mx[x][z]+dis[o][oy]*2);
                }
                lst = oy, oy = fa[x][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: