QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#408224#7103. Red Black Treeucup-team2010TL 0ms8084kbC++208.8kb2024-05-09 21:15:462024-05-09 21:15:47

Judging History

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

  • [2024-05-09 21:15:47]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:8084kb
  • [2024-05-09 21:15: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)];
int dfn[maxn], L[maxn], R[maxn], tot;
bool isRed[maxn];
ll dep[maxn];
ll val[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) {
    tot = 0;
    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;
        dfn[++tot] = u;
        dep[u] = dep[f] + d;
        L[u] = tot;
        if (isRed[u])redfa = u;
        val[u] = dep[u] - dep[redfa];
        for (auto [v, w] : G[u]) {
            if (v == f)continue;
            dfs(dfs,v, u, w, redfa);
        }
        R[u] = tot;
    };
    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;
}
#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];
        }
        ll l = -1, r = 1e16;
        auto check = [&](ll w) {
            std::vector<ll> now;
            int cnt = 0;
            bool ok = 0;
            std::vector<array<ll, 2>> np;
            for (auto q : vec) {
                if (val[q] > w) {
                    int ffa = calcFa(q, w);
                    now.pb(ffa);
                    int id = L[q];
                    c.add(id, 1);
                    np.pb({id, 1});
                    cnt++;
                    ffa = fa[ffa][0];
                    if (L[ffa]) {
                        c.add(L[ffa], -1);
                        np.pb({L[ffa],-1});
                    }
                }
            }
            if (now.empty())ok = 1;
            for (auto q : now) {
                if (c.getsum(L[q], R[q]) == cnt)ok = 1;
            }
            for(auto [l,r]:np){
                c.add(l,-r);
            }
            return ok;
        };
        while (l + 1 < r) {
            ll mid = (l + r) >> 1;
            if (check(mid))r = mid;
            else l = mid;
        }
        cout << r << "\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: 8084kb

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
Time Limit Exceeded

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: