QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#306048#7103. Red Black TreeMinhhoAC ✓788ms41316kbC++173.3kb2024-01-16 11:11:252024-01-16 11:11:26

Judging History

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

  • [2024-01-16 11:11:26]
  • 评测
  • 测评结果:AC
  • 用时:788ms
  • 内存:41316kb
  • [2024-01-16 11:11:25]
  • 提交

answer

#define taskname "B"
#include <bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define ff first
#define ss second

using namespace std;
const int maxn = 1e5 + 10;
vector<ii> adj[maxn];
int in[maxn], dp[maxn], out[maxn], par[maxn], dep[maxn], depth[maxn], mark[maxn];
int p[maxn][20];
int n, m, q, k, cnt;

void DFS(int u = 1, int pa = 0, int cur = 0, int pp = 0)
{
    if (mark[u]) cur = 0, pp = u;
    in[u] = ++cnt;
    dp[u] = cur;
    par[u] = pp;
    for (auto [v, c]: adj[u]) if (v != pa)
    {
        p[v][0] = u;
        dep[v] = dep[u] + 1;
        depth[v] = depth[u] + c;
        DFS(v, u, cur + c, pp);
    }
    out[u] = cnt;
}

inline int lca(int u, int v)
{
    if (dep[u] > dep[v]) swap(u, v);
    int dif = dep[v] - dep[u];
    for (int i=k; i>=0; i--) if (dif >> i & 1) v = p[v][i];
    if (v == u) return u;
    for (int i=k; i>=0; i--) if (p[v][i] != p[u][i]) v = p[v][i], u = p[u][i];
    return p[u][0];
}

inline bool isPar(int u, int v)
{
    return (in[u] <= in[v] && out[u] >= out[v]);
}

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin.tie(nullptr); cout.tie(nullptr);
    int tst; cin>>tst; while (tst--)
    {
        cin>>n>>m>>q;
        for (int i=1; i<=n; i++) mark[i] = 0, adj[i].clear();
        for (int i=1, x; i<=m; i++) cin>>x, mark[x] = 1;
        for (int i=1, u, v, c; i<n; i++)
        {
            cin>>u>>v>>c;
            adj[u].emplace_back(v, c);
            adj[v].emplace_back(u, c);
        }
        cnt = 0;
        dep[1] = depth[1] = 0;
        DFS();
        k = log2(n);
        for (int i=1; i<=k; i++)
            for (int j=1; j<=n; j++)
                p[j][i] = p[p[j][i-1]][i-1];
        while (q--)
        {
            vector<int> v, v2;
            int x;
            cin>>x;
            for (int i=1, y; i<=x; i++)
            {
                cin>>y;
                if (!mark[y]) v.emplace_back(y);
            }
            x = v.size();
            if (v.empty())
            {
                cout<<"0\n";
                continue;
            }
            sort(v.begin(), v.end(), [](int x, int y) {return dp[x] > dp[y];});
            int cur = v[0], ans = dp[v[0]];
            int mx = dep[par[cur]];
            v2.emplace_back(cur);
            for (int i=1; i<x; i++)
            {
                int tmp = lca(cur, v[i]);
                if (dep[tmp] <= max(dep[par[v[i]]], mx)) break;
                mx = max(mx, dep[par[v[i]]]);
                cur = tmp;
                v2.emplace_back(cur);
            }
            sort(v2.begin(), v2.end());
            v2.resize(unique(v2.begin(), v2.end()) - v2.begin());
            for (int can: v2)
            {
                // cout<<"CAN: "<<can<<"\n";
                int res = depth[v[0]] - depth[can];
                for (int i: v)
                    if (isPar(can, i))
                        res = max(res, min(dp[i], depth[i] - depth[can]));
                    else res = max(res, dp[i]);
                ans = min(ans, res);
            }
            cout<<ans<<"\n";
        }
    }
}
/**
 * 2
12 2 4
1 9
1 2 1
2 3 4
3 4 3
3 5 2
2 6 2
6 7 1
6 8 2
2 9 5
9 10 2
9 11 3
1 12 10
3 3 7 8
4 4 5 7 8
4 7 8 10 11
3 4 5 12
3 2 3
1 2
1 2 1
1 3 1
1 1
2 1 2
3 1 2 3
*/



这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 13336kb

input:

2
12 2 4
1 9
1 2 1
2 3 4
3 4 3
3 5 2
2 6 2
6 7 1
6 8 2
2 9 5
9 10 2
9 11 3
1 12 10
3 3 7 8
4 4 5 7 8
4 7 8 10 11
3 4 5 12
3 2 3
1 2
1 2 1
1 3 1
1 1
2 1 2
3 1 2 3

output:

4
5
3
8
0
0
0

result:

ok 7 lines

Test #2:

score: 0
Accepted
time: 788ms
memory: 41316kb

input:

522
26 1 3
1
1 4 276455
18 6 49344056
18 25 58172365
19 9 12014251
2 1 15079181
17 1 50011746
8 9 2413085
23 24 23767115
22 2 26151339
26 21 50183935
17 14 16892041
9 26 53389093
1 20 62299200
24 18 56114328
11 2 50160143
6 26 14430542
16 7 32574577
3 16 59227555
3 15 8795685
4 12 5801074
5 20 57457...

output:

148616264
148616264
0
319801028
319801028
255904892
317070839
1265145897
1265145897
1072765445
667742619
455103436
285643094
285643094
285643094
317919339
0
785245841
691421476
605409472
479058444
371688030
303203698
493383271
919185207
910180170
919185207
121535083
181713164
181713164
181713164
181...

result:

ok 577632 lines

Extra Test:

score: 0
Extra Test Passed