QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#210532#2065. Cyclic DistancehellojimWA 33ms8164kbC++143.3kb2023-10-11 16:06:452023-10-11 16:06:46

Judging History

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

  • [2023-10-11 16:06:46]
  • 评测
  • 测评结果:WA
  • 用时:33ms
  • 内存:8164kb
  • [2023-10-11 16:06:45]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=200005;
mt19937 rng(19260817);
int rnd(int l,int r){
    return rng()%(r-l+1)+l;
}
struct node{
    ll val,tag;
    int key,l,r,sz;
}tr[N];
int cnt=0,rt[N];
void pushup(int id){
    int ls=tr[id].l,rs=tr[id].r;
    tr[id].sz=tr[ls].sz+tr[rs].sz+1;
}
void pushtag(int id,ll k){
    tr[id].val+=k;tr[id].tag+=k;
}
void pushdown(int id){
    int ls=tr[id].l,rs=tr[id].r;
    ll k=tr[id].tag=0;tr[id].tag=0;
    pushtag(ls,k);pushtag(rs,k);
}
int newnode(ll val){
    ++cnt;
    tr[cnt].val=val;tr[cnt].tag=0;tr[cnt].l=tr[cnt].r=0;
    tr[cnt].key=rng();tr[cnt].sz=1;
    return cnt;
}
void splitsz(int cur,int siz,int &x,int &y){
    if(!cur){
        x=y=0;return;
    }
    pushdown(cur);
    if(tr[tr[cur].l].sz+1<=siz){
        x=cur;
        splitsz(tr[x].r,siz-tr[tr[cur].l].sz-1,tr[x].r,y);
    }
    else{
        y=cur;
        splitsz(tr[y].l,siz,x,tr[y].l);
    }
    pushup(cur);
}
void splitval(int cur,int val,int &x,int &y){
    if(!cur){
        x=y=0;return;
    }
    pushdown(cur);
    if(tr[cur].val>=val){
        x=cur;
        splitval(tr[x].r,val,tr[x].r,y);
    }
    else{
        y=cur;
        splitval(tr[y].l,val,x,tr[y].l);
    }
    pushup(cur);
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(tr[x].key<=tr[y].key){
        pushdown(x);
        tr[x].r=merge(tr[x].r,y);
        pushup(x);
        return x;
    }
    else{
        pushdown(y);
        tr[y].l=merge(x,tr[y].l);
        pushup(y);
        return y;
    }
}
void dfs(int u){
    if(!u)return;
    pushdown(u);
    dfs(tr[u].l);
    cout<<tr[u].val<<" ";
    dfs(tr[u].r);
}
int A,B,C;
void ins(int u,ll val){
    splitval(rt[u],val,A,B);
    rt[u]=merge(A,merge(newnode(val),B));
}
int n,k;
vector<pii>g[N];
void dfs(int u,int fa){
    for(auto pr:g[u]){
        int v=pr.fi;ll w=pr.se;
        if(v==fa)continue;
        dfs(v,u);
        if(tr[rt[v]].sz<=k/2){
            pushtag(rt[v],w);
        }
        else if(tr[rt[v]].sz==(k+1)/2){
            splitsz(rt[v],k/2,A,B);
            pushtag(A,w);
            rt[v]=merge(A,B);
        }
        else{
            splitsz(rt[v],(k+1)/2,A,C);
            splitsz(A,k/2,A,B);
            pushtag(A,w);pushtag(C,-w);
            rt[v]=merge(A,merge(B,C));
        }
        if(tr[u].sz<tr[v].sz)swap(rt[u],rt[v]);
        while(rt[v]){
            pushdown(rt[v]);
            ins(u,tr[rt[v]].val);
            rt[v]=merge(tr[rt[v]].l,tr[rt[v]].r);
        }
    }
    ins(u,0);
}
void solve(){
    cin>>n>>k;
    for(int i=1;i<n;i++){
        int x,y,w;
        cin>>x>>y>>w;
        g[x].push_back({y,w});
        g[y].push_back({x,w});
    }
    dfs(1,0);
    splitsz(rt[1],k,A,C);
    ll ans=0;
    while(A){
        ans+=tr[A].val;
        pushdown(A);
        A=merge(tr[A].l,tr[A].r);
    }
    cout<<ans*2<<"\n";
    for(int i=1;i<=n;i++){
        g[i].clear();rt[i]=0;
    }
    for(int i=1;i<=cnt;i++){
        tr[i].key=tr[i].l=tr[i].r=tr[i].sz=tr[i].val=tr[i].tag=0;
    }
    cnt=0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 8112kb

input:

1
5 3
1 2 4
1 3 1
1 4 8
4 5 9

output:

44

result:

ok single line: '44'

Test #2:

score: -100
Wrong Answer
time: 33ms
memory: 8164kb

input:

57206
3 2
1 2 574927
2 3 406566
2 2
1 2 308806
4 3
1 2 312588
2 3 500141
2 4 53602
3 3
1 2 797183
2 3 944061
5 3
1 2 624010
2 3 488613
3 4 734514
4 5 497493
5 4
1 2 540278
2 3 488655
2 4 228989
2 5 653896
2 2
1 2 569117
4 2
1 2 821764
2 3 499471
1 4 549060
2 2
1 2 991159
2 2
1 2 482941
5 4
1 2 30462...

output:

1962986
617612
1732662
3482488
4689260
2743080
1138234
3740590
1982318
965882
3418504
5026562
1623414
1885106
1952142
2088464
1691896
3102076
2380932
3076270
4288682
4175910
879020
2500212
3613854
1358950
1182198
2273662
2331560
1681964
5532154
2373066
3163042
3104226
3642898
2579674
3036446
3669186...

result:

wrong answer 6th lines differ - expected: '3823636', found: '2743080'