QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#225785#7103. Red Black Treeucup-team992AC ✓684ms37020kbC++174.5kb2023-10-25 08:57:262023-10-25 08:57:26

Judging History

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

  • [2023-10-25 08:57:26]
  • 评测
  • 测评结果:AC
  • 用时:684ms
  • 内存:37020kb
  • [2023-10-25 08:57:26]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long
typedef int uci;
#define int long long
#define F first
#define S second
typedef complex<double> cd;

seed_seq seq{
    (uint64_t) chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(),
    (uint64_t) __builtin_ia32_rdtsc(),
    (uint64_t) (uintptr_t) make_unique<char>().get()
};
mt19937 rng(seq);
// mt19937_64 lrng(seq);

struct debugger{
    template <typename T>
    debugger& operator<<(T &a){
        #ifdef DEBUG
            cerr << a;
        #endif
        return *this;
    }
    template <typename T>
    debugger& operator<<(T &&a){
        #ifdef DEBUG
            cerr << a;
        #endif
        return *this;
    }
} deb;

const double PI = acos(-1.0);
const int MAX_N = 1e5 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;

//! function insert

//THINK FIRST, CODE SECOND
//DON'T GET STUCK ON ONE STRATEGY
//CALM DOWNNN FOR ONCE IN YOUR LIFE
//REDUCE
//COUGH E??!?!?!! O.O
//uwu i see you ryan
bool isred[100001];
int dist[100001];
int lift[100001][20];
int cost[100001];
int depth[100001];

void dfs(int v, int p, int c, int d, int de, vector<vector<ar<int, 2>>> &adj){
    if(isred[v])
        d = 0;
    dist[v] = d;
    depth[v] = de;
    lift[v][0] = p;
    cost[v] = c;
    for(int i{1}; i < 20; ++i){
        lift[v][i] = lift[lift[v][i-1]][i-1];
    }
    for(auto i : adj[v]){
        if(i[0] == p)
            continue;
        dfs(i[0], v, c+i[1], d+i[1], de+1, adj);
    }
}

int goup(int v, int p){
    int c{};
    while(p){
        if(p&1){
            v = lift[v][c];
        }
        p >>= 1;
        c++;
    }
    return v;
}

int lca(int u, int v){
    if(depth[u] > depth[v])
        swap(u, v);
    v = goup(v, depth[v] - depth[u]);
    if(u == v)
        return u;
    for(int i = 19; i >= 0; --i){
        if(lift[u][i] != lift[v][i]){
            u = lift[u][i];
            v = lift[v][i];
        }
    }
    return lift[u][0];
}

void solve() {
    int n, m, q;
    cin >> n >> m >> q;

    for(int i{}; i < n; ++i)
        isred[i] = false;
    isred[0] = true;
    for(int i{}; i < m; ++i){
        int t;
        cin >> t;
        t--;
        isred[t] = true;
    }

    vector<vector<ar<int, 2>>> adj(n);
    for(int i{}; i < n-1; ++i){
        int u, v;
        cin >> u >> v;
        int w;
        u--, v--;
        cin >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dfs(0, 0, 0, 0, 0, adj);

    for(int i{}; i < q; ++i){
        int k;
        cin >> k;
        vector<int> a(k);
        for(int j{}; j < k; ++j){
            cin >> a[j];
            a[j]--;
        }
        sort(a.begin(), a.end(), [&](auto a, auto b){
            return dist[a] > dist[b];
                });

        int best = cost[a[0]];
        int lc = a[0];
        int mde = cost[a[0]];
        for(int j{}; j < k; ++j){
            lc = lca(lc, a[j]);
            mde = max(mde, cost[a[j]]);
            if(j == k-1){
                best = min(best, mde - cost[lc]);
            }else{
                best = min(best, max(dist[a[j+1]], mde-cost[lc]));
            }
        }
        cout << best << '\n';
    }
}

uci main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int tc; cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t  << ": ";
        solve();
    }
}

/*
    random number generator stuff
    num = rng(); gives integer number
    num = uniform_int_distribution<int>(a, b)(rng); -> bounds [a, b]
    num = uniform_real_distribution<double>(a, b)(rng); -> bounds [a, b)
    can also instantiate distributions and call on generator:
    uniform_int_distribution<int> thing(a, b);
    num = thing(rng);
*/
// struct custom_hash {
//     static uint64_t splitmix64(uint64_t x) {
//         // http://xorshift.di.unimi.it/splitmix64.c
//         x += 0x9e3779b97f4a7c15;
//         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
//         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
//         return x ^ (x >> 31);
//     }
//     size_t operator()(uint64_t x) const {
//         static const uint64_t FIXED_RANDOM = lrng();
//         return splitmix64(x + FIXED_RANDOM);
//     }
// };

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

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7696kb

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: 684ms
memory: 37020kb

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