QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#408253#7103. Red Black Treeucup-team2010WA 488ms27836kbC++208.3kb2024-05-09 21:59:462024-05-09 21:59:47

Judging History

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

  • [2024-05-09 21:59:47]
  • 评测
  • 测评结果:WA
  • 用时:488ms
  • 内存:27836kb
  • [2024-05-09 21:59:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
#define pb push_back
using pll = pair<ll, ll>;
const int maxn = 1e5 + 5;

namespace FastIO {
//不支持while(qin>>x)的多组数据输入方法
//任何情况下请不要关闭sync_with_stdio同步锁!!
//如果您选择关闭同步锁以获得更高的cin/cout速度 使用此模块会导致不可预期的后果
//此处为负数读取功能开关
// 若程序不会读入负数 请去除下方注释符号 以获得30%的输入提速
#define DisableNegative true
//此处为兼容性模式开关 若程序IO存在 *任何* *int/ll/char[]/string/char(包括空格回车)* 之外的类型
//请去除下方注释符号 降低一半的速度以获得兼容性
//#define EnableCompatibility true

class Scanner {
    char cht;
    bool ifNegative;
    char stringBuf[10000];
#ifndef EnableCompatibility
#define BUF_SIZE 524288
    char nc() {
        static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
        if (p1 == pend) {
            p1 = buf;
            pend = buf + fread(buf, 1, BUF_SIZE, stdin);
            if (pend == p1)return ' ';
        }
#ifndef DisableNegative
        if (*p1 == '-') {
            ifNegative = true;
            p1++;
            return nc();
        }
#endif
        return *p1++;
    }
#else
    inline char nc() {
        return getchar();
    }
#endif
    inline bool blank(char ch) {
        return ch == '\r' || ch == '\n' || ch == ' ' || ch == '\t';
    }
public:
    Scanner operator>>(int&x) {
#ifndef DisableNegative
        ifNegative = false;
#endif
        while (blank(cht = nc()));
        for (x = cht - '0'; (cht = nc()) >= '0' && cht <= '9'; x = x * 10 + cht - '0');
#ifndef DisableNegative
        if (ifNegative)x *= -1;
#endif
        return *this;
    }
    Scanner operator>>(long long int&x) {
#ifndef DisableNegative
        ifNegative = false;
#endif
        while (blank(cht = nc()));
        for (x = cht - '0'; (cht = nc()) >= '0' && cht <= '9'; x = x * 10 + cht - '0');
#ifndef DisableNegative
        if (ifNegative)x *= -1;
#endif
        return *this;
    }
    Scanner operator>>(__int128 &x) {
#ifndef DisableNegative
        ifNegative = false;
#endif
        while (blank(cht = nc()));
        for (x = cht - '0'; (cht = nc()) >= '0' && cht <= '9'; x = x * 10 + cht - '0');
#ifndef DisableNegative
        if (ifNegative)x *= -1;
#endif
        return *this;
    }
    Scanner operator>>(string&str) {
        int p = 0;
        while (blank(cht = nc()));
        for (stringBuf[p++] = cht; !blank(cht = nc()); stringBuf[p++] = cht);
        stringBuf[p] = '\0';
        str = stringBuf;
        return *this;
    }
    Scanner operator>>(char str[]) {
        int p = 0;
        while (blank(cht = nc()));
        for (str[p++] = cht; !blank(cht = nc()); str[p++] = cht);
        str[p] = '\0';
        return *this;
    }
    template<typename F>
    inline Scanner operator>>(F&f) {
        cin >> f;
        return *this;
    }
};

class Printer {
    int num;
    char chr[21];
public:
    Printer operator<<(int x) {
        if (x == 0) {
            putchar('0');
            return *this;
        }
        if (x < 0)x *= -1, putchar('-');
        num = 0;
        while (x) chr[++num] = (x % 10) + 48, x /= 10;
        while (num) putchar(chr[num--]);
        return *this;
    }
    Printer operator<<(long long int x) {
        if (x == 0) {
            putchar('0');
            return *this;
        }
        if (x < 0)x *= -1, putchar('-');
        num = 0;
        while (x) chr[++num] = (x % 10) + 48, x /= 10;
        while (num) putchar(chr[num--]);
        return *this;
    }
    Printer operator<<(__int128 x) {
        if (x == 0) {
            putchar('0');
            return *this;
        }
        if (x < 0)x *= -1, putchar('-');
        num = 0;
        while (x) chr[++num] = (x % 10) + 48, x /= 10;
        while (num) putchar(chr[num--]);
        return *this;
    }
    inline Printer operator<<(char x) {
        putchar(x);
        return *this;
    }
    Printer operator<<(const char str[]) {
        int p = 0;
        while (str[p] != '\0') {
            putchar(str[p++]);
        }
        return *this;
    }
    inline Printer operator<<(string&x) {
        for (string::iterator i = x.begin(); i < x.end(); i++)putchar(*i);
        return *this;
    }
    template<typename F>
    inline Printer operator<<(F&f) {
        cout << f;
        return *this;
    }
};
Scanner qin;
Printer qout;
#define endl '\n'
}
using namespace FastIO;
template<typename T>
struct BIT {
    int size;
    std::vector<T> c;
    BIT(int size = 0) {
        init(size);
    }
    void init(int size) {
        this->size = size;
        c.assign(size + 1, T());
    }
    T ask(int n) {
        T sum = 0;
        for (int i = n; i; i -= i & -i) {
            sum += c[i];
        }
        return sum;
    }
    void add(int pos, T x) {
        if (pos == 0)return;
        for (int i = pos; i <= size; i += i & -i) {
            c[i] += x;
        }
    }
    void modify(int l, int r, T x) {
        if (l > r)swap(l, r);
        add(l, x);
        add(r + 1, -x);
    }
    T getsum(T l, T r) {
        if (l > r)swap(l, r);
        return ask(r) - ask(l - 1);
    }
};
BIT<ll>c(maxn);
int fa[maxn][__lg(maxn)];
bool isRed[maxn];
ll dep[maxn];
ll val[maxn];
int layer[maxn];
int Redfa[maxn];
struct edge {
    int v;
    ll w;
};
vector<edge>G[maxn];
void add(int u, int v, int w) {
    G[u].push_back({v, w});
    G[v].push_back({u, w});
}
int lg = 0;
void init(int n) {
    lg = __lg(n);
    auto dfs = [&](auto && dfs, int u, int f, ll d, int redfa)->void{
        fa[u][0] = f;
        // cerr<<"u="<<u<<" fa[0]="<<fa[u][0]<<'\n';
        // dis[u][0]=d;
        dep[u] = dep[f] + d;
        layer[u] = layer[f] + 1;
        if (isRed[u])redfa = u;
        val[u] = dep[u] - dep[redfa];
        Redfa[u]=redfa;
        for (auto [v, w] : G[u]) {
            if (v == f)continue;
            dfs(dfs, v, u, w, redfa);
        }
    };
    dfs(dfs, 1, 0, 0, 0);
    for (int k = 1; k <= lg; k++) {
        for (int i = 1; i <= n; i++) {
            fa[i][k] = fa[fa[i][k - 1]][k - 1];
            // cerr<<"i="<<i<<" 1<<k="<<(1<<k)<<" fa="<<fa[i][k]<<'\n';
            // dis[i][k]=dis[i][k-1]+dis[fa[i][k-1]][k-1];
        }
    }
}
int calcFa(int u, ll d) {
    ll now = 0;
    for (int i = lg; i >= 0; i--) {
        int f = fa[u][i];
        if (f == 0)continue;
        ll dis = dep[u] - dep[f];
        if (now + dis <= d) {
            now += dis;
            u = f;
        }
    }
    return u;
}
int calcLCA(int u, int v) {
    if (layer[u] > layer[v])swap(u, v);
    for (int i = lg; i >= 0; i--) {
        if (layer[v] == layer[u])break;
        int f = fa[v][i];
        if (layer[f] >= layer[u]) {
            v = f;
        }
    }
    if (u == v)return u;
    for (int i = lg; i >= 0; i--) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}
#define cin qin
#define cout qout
void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    c.init(n + 1);
    for (int i = 1; i <= n; i++) {
        G[i].clear();
    }
    fill(isRed, isRed + n + 1, false);
    for (int i = 1; i <= m; i++) {
        int r;
        cin >> r;
        isRed[r] = true;
    }
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        add(u, v, w);
    }
    init(n);
    while (q--) {
        int k;
        cin >> k;
        vector<int>vec(k);
        for (int i = 0; i < k; i++) {
            cin >> vec[i];
        }
        sort(vec.begin(), vec.end(), [&](int a, int b) {
            return val[a] > val[b];
        });
        vec.pb(0);
        ll ffa = vec[0];
        ll madis=dep[vec[0]];
        ll ans=1e18;
        for(int i=0;i<k;i++){
            madis=max(madis,dep[vec[i]]);
            ffa=calcLCA(ffa,vec[i]);
            ans=min(ans,max(madis-dep[ffa],val[vec[i+1]]));
        }
        cout<<ans<<'\n';
    }

}
int main() {
    // ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)solve();
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 8044kb

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
Wrong Answer
time: 488ms
memory: 27836kb

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:

wrong answer 2583rd lines differ - expected: '2733109738', found: '3036491157'