QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#795614#7103. Red Black Treeender_shayanWA 1045ms59296kbC++173.6kb2024-11-30 22:09:122024-11-30 22:09:12

Judging History

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

  • [2024-11-30 22:09:12]
  • 评测
  • 测评结果:WA
  • 用时:1045ms
  • 内存:59296kb
  • [2024-11-30 22:09:12]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double	ld;
typedef pair<int, int>	pii  ;
typedef pair<ll, ll>	pll  ;
typedef vector<pii>     vii  ;
typedef vector<int>     veci ;
typedef vector<pll>     vll  ;
typedef vector<ll>      vecll;

// find_by_order             order_of_key

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp		        make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl
#define set_dec(x)	    cout << fixed << setprecision(x);
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("in.txt" , "r" , stdin) ; freopen("out.txt" , "w" , stdout);
#define lb              lower_bound
#define ub              upper_bound
#define for1(n)         for(int i=1;i<=n;i++)
#define for0(n)         for(int i=0;i<n;i++)
#define forn(n)         for(int i=n;i>0;i--)
#define pq              priority_queue <pii, vector<pii>, greater<pii>>


ll mod = 1e9+7 ;// 998244353 ;// 1e9+9;

ll inf=1e18;
const int N=1e6+10,L=21,bs=701;
int A[N],B[N],is[N],n,m,k,q,par[N][L],h[N],st[N],en[N],t;
vector<pii>g[N];
ll hh[N],rd[N];
void dfs1(int v,ll ww=0){
    if(is[v])ww=0;
    rd[v]=ww;
    st[v]=++t;
    for(auto [u,w]:g[v])if(u!=par[v][0]){
        par[u][0]=v;
        h[u]=h[v]+1;
        hh[u]=hh[v]+w;
        dfs1(u,ww+w);
    }
    en[v]=t;
}
ll ans;
int LCA(int v1,int v2){
    if(h[v1]<h[v2])swap(v1,v2);
    int x=h[v1]-h[v2];
    for(int j=0;j<L;j++)if(x>>j&1)v1=par[v1][j];
    if(v1==v2)return v1;
    for(int j=L-1;j>=0;j--)if(par[v1][j]!=par[v2][j]){
        v1=par[v1][j];
        v2=par[v2][j];
    }
    return par[v1][0];
}
int main(){
    fast_io
    en[0]=N;
    int T;cin>>T;
    while(T--){
        cin>>n>>k>>q;
        while(k--){
            int x;cin>>x;
            is[x]=1;
        }
        for1(n-1){
            int u,v,w;cin>>u>>v>>w;
            g[u].pb({v,w});
            g[v].pb({u,w});
        }
        dfs1(1);
        for(int j=1;j<L;j++)for1(n)par[i][j]=par[par[i][j-1]][j-1];
        while(q--){
            cin>>k;
            vector<pii>vec;
            vector<pll>vec2;
            pll MAX={0,0};
            ll ans=0,tmp=0;
            for1(k){
                int v;cin>>v;
                vec2.pb({st[v],v});
                MAX=max(MAX,{rd[v],v});
                ans=max(ans,rd[v]);
            }
            sort(all(vec2));
            int v=MAX.S;
            for(auto[t,vv]:vec2){
                int v2=LCA(v,vv);
                vec.pb({h[v2],v2});
            }
            sort(all(vec));vec.resize(unique(all(vec))-vec.begin());
            int l=0,r=k-1;
            for(auto [t,vv]:vec){
                while(st[vec2[l].S]<st[vv]){
                    tmp=max(tmp,rd[vec2[l].S]);
                    l++;
                }
                while(en[vec2[r].S]>en[vv]){
                    tmp=max(tmp,rd[vec2[r].S]);
                    r--;
                }
                ll ans2=max(tmp,hh[v]-hh[vv]);
                ans=min(ans,ans2);
            }
            cout<<ans<<endl;
        }
        t=0;
        for1(n){g[i].clear();rd[i]=h[i]=hh[i]=is[i]=0;}
    }




}




详细

Test #1:

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

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: 1045ms
memory: 59296kb

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 691st lines differ - expected: '549790714', found: '374667774'