QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#182509#7103. Red Black TreeFeet_McYeetRE 23ms215716kbC++174.2kb2023-09-18 06:35:252023-09-18 06:35:26

Judging History

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

  • [2023-09-18 06:35:26]
  • 评测
  • 测评结果:RE
  • 用时:23ms
  • 内存:215716kb
  • [2023-09-18 06:35:25]
  • 提交

answer

#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <array>
#include <iterator>
#include <algorithm>
// #include <bit>
#include <numeric>
#include <iomanip>
using namespace std;
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#define el << '\n'
#define nl cout << '\n'
#define cina(a,n) for (int i=0; i<n; i++) cin >> a[i]
#define ll long long
#define spc << ' '
#define forn(i,n) for (int i=0; i<n; i++)
#define forl(i,s,e) for (int i=s; i<e; i++)
#define pb push_back
#define ansyes cout << "YES\n"
#define ansno cout << "NO\n"
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pss pair<short, short>
#define MAX *max_element
#define MIN *min_element
#define rsz resize
#define sz(x) ((int) x.size())
#define all(x) x.begin(), x.end()
#define bsi(x, v) (int) (lower_bound(x.begin(), x.end(), v) - x.begin());
const int inf = 1000000000;
const ll inf2 = 4000000000000000000;

int lg(int k) {
    return 31-__builtin_clz(k);
}

const int MAXN = 1000005;

int n;

bool r[MAXN];

vector<pii> adj[MAXN];

vector<int> etd;

int tin[MAXN];
int dep[MAXN];

int ti;

void et(int cn, int pn, int d) {
    tin[cn] = ti;
    dep[cn] = d;
    etd.pb(cn);
    ti++;
    for (pii i : adj[cn]) {
        if (i.fi == pn) continue;
        et(i.fi, cn, d+1);
        etd.pb(cn);
        ti++;
    }
}

vector<int> spd[4*MAXN];
vector<int> spi[4*MAXN];

void gst() {
    int m = sz(etd);
    forn(i,m) {
        spi[i].rsz(lg(m-i+1));
        spd[i].rsz(lg(m-i+1));
        spi[i][0]=etd[i];
        spd[i][0]=dep[etd[i]];
    }
    for (int js = 1; (1<<js) <= m; js++) {
        forn(i, m-(1<<js)+1) {
            int l2 = i + (1<<(js-1));
            if (spd[i][js-1] < spd[l2][js-1]) {
                spd[i][js] = spd[i][js-1];
                spi[i][js] = spi[i][js-1];
            }
            else {
                spd[i][js] = spd[l2][js-1];
                spi[i][js] = spi[l2][js-1];
            }
        }
    }
}

int lca(int a, int b) {
    a = tin[a]; 
    b = tin[b];
    if (a>b) swap(a,b);
    int d = lg(b-a+1);
    if (spd[a][d] < spd[b-(1<<d)+1][d]) return spi[a][d];
    return spi[b-(1<<d)+1][d];
}

ll d[MAXN];
int dtr[MAXN];
ll ad[MAXN];

void dfs(int cn, int pn, ll de, int ud, ll td) {
    if (r[cn]) {
        de = 0;
        ud = 0;
    }
    d[cn] = de;
    dtr[cn] = ud;
    ad[cn] = td;
    for (pii i : adj[cn]) {
        if (i.fi == pn) continue;
        dfs(i.fi, cn, de+i.se, ud+1, td+i.se);
    }
}

int t;

ll query (int qs) {
    pair<ll, int> v[qs]; 
    forn(i,qs) {
        cin >> v[i].se;
        v[i].se--;
        v[i].fi = d[v[i].se];
    }
    if (qs == 1) return 0;
    sort(v,v+qs);
    // forn(i,qs) cout << v[i].se spc << v[i].fi el;
    ll ans = v[qs-2].fi;
    int l = v[qs-1].se;
    for (int i = qs-2; i>0; i--) {
        // if (t==521) cout << 'a';
        l = lca(l, v[i].se);
        // if (t==521) cout << 'b';
        // if (t==521) return qs;
        ans = min(ans, max(ad[v[qs-1].se] - ad[l], v[i-1].fi));
    }
    l = lca(v[0].se, l);
    ans = min(ans, ad[v[qs-1].se] - ad[l]);
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> t;
    while (t--) {
        etd.clear();
        ti = 0;
        int m, q; cin >> n >> m >> q;
        forn(i,n) {
            r[i] = false;
            adj[i].clear();
        }
        forn(i,8*n) {
            spd[i].clear();
            spi[i].clear();
        }
        forn(i,m) {
            int a; cin >> a; a--;
            r[a] = true;
        }
        forn(i,n-1) {
            int u, v, w; cin >> u >> v >> w;
            u--; v--;
            adj[u].pb({v,w});
            adj[v].pb({u,w});
        }
        et(0, -1, 0);
        // for (int i : etd) cout << i spc;
        // nl el;
        gst();
        dfs(0, -1, 0, 0, 0);
        forn(qn, q) {
            int qt; cin >> qt;
            cout << query(qt) << endl;
            // if (t==521) break;
        }
        // forn(i,n) forn(j,n) cout << lca(i,j) spc;
        // nl;
        // if (t==521) break;
    }
}

详细

Test #1:

score: 100
Accepted
time: 23ms
memory: 215716kb

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: -100
Runtime Error

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

result: