QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#302389#5249. BanditsLaStataleBlueWA 991ms204332kbC++235.5kb2024-01-10 20:21:012024-01-10 20:21:01

Judging History

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

  • [2024-01-10 20:21:01]
  • 评测
  • 测评结果:WA
  • 用时:991ms
  • 内存:204332kb
  • [2024-01-10 20:21:01]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

struct FenwickSparse{
    vector<array<long long,3>> ft;
    vector<array<int,2>> ind;
    
    void add(int nodo,int dist){
        ft.push_back({dist,nodo,0});
    }
    
    void fix(){
        ft.push_back({(long long)-1e17,0,0});
        sort(ft.begin(),ft.end());
        
        for(int i=1;i<(int)ft.size();i++){
            ind.push_back({ft[i][1],i});
        }
        sort(ind.begin(),ind.end());
    }
    
    int posfromdist(long long dist){
        return lower_bound(ft.begin(),ft.end(),array<long long,3>{dist+1,-1,-1})-ft.begin()-1;
    }
    
    int posfromnode(int node){
        return (*lower_bound(ind.begin(),ind.end(),array<int,2>{node,-1}))[1];
    }
    
    void upd(int pos,int val){
        for(int i=pos;i>0;i-=(i&(-i)))ft[i][2]+=val;
    }
    
    int que(int pos){
        int res=0;
        for(int i=pos;i<(int)ft.size();i+=(i&(-i)))res+=ft[i][2];
        return res;
    }
    
    void update(long long dist,int val){
        upd(posfromdist(dist),val);
    }
    
    int query(int nodo){
        return que(posfromnode(nodo));
    }
};

const int MN = 1e5+10, INF = 0x3f3f3f3f;
int N, M, s[MN], t, b; long long d;
bool r[MN];vector<FenwickSparse> v[MN];vector<pair<int,int>> a[MN];
//v[i][j]=nodo rosso + vicino a i nel sottoalbero j-esimo
struct info { int n,b; long long d; };
//g[i] = lista degli antenati di i nel centroid tree
//g[i][j]={antenato x (diverso da i),indice del sottoalbero
// che contiene i in v[x],distanza i->x}
vector<info> g[MN];
int dfs(int n, int p=0){
    s[n]=1;
    for(auto  [x,cost] :a[n])
        if(x!=p&&!r[x])
            s[n]+=dfs(x, n);
    return s[n];
}
int find(int n, int ms, int p=0){
    for(auto [x,cost]:a[n])
        if(!r[x]&&x!=p&&s[x]*2>ms)
            return find(x, ms, n);
    return n;
}
void dfs2(int n, int p=0){
    for(auto [x,cost]:a[n])
        if(!r[x]&&x!=p){
            d+=cost; dfs2(x, n); d-=cost;
        }
    g[n].push_back({t,b,d});
    v[t].back().add(n,d);
    v[t][0].add(n,d);
}
void centroid(int n=1){ //1-based
    n = find(n, dfs(n));
    v[n].reserve(a[n].size()+1);
    v[n].push_back(FenwickSparse());
    v[n].back().add(n,0);
    for(auto [x,cost]:a[n])
        if(!r[x]){
        t=n, b=v[n].size(), d=cost;
        v[n].push_back(FenwickSparse());
        dfs2(x, n); //aggiorno i g[]
        v[n].back().fix();
    }
    v[n][0].fix();
    r[n]=1;
    for(auto [x,cost]:a[n])
        if(!r[x])
            centroid(x);
}

void solve(int t){
    int n;
    cin>>n;
    
    const int LOGN = 20;
    vector grafo(n+1,vector<pair<int,int>>());
    vector id(n,0);
    vector par(n+1,vector<int>(LOGN,0));
    vector pr(n+1,0ll);
    
    for(int i=0;i<n-1;i++){
        int u,v,x;
        cin>>u>>v>>x;
        a[u].push_back({v,x});
        a[v].push_back({u,x});
        grafo[u].push_back({v,i+1});
        grafo[v].push_back({u,i+1});
    }
    
    auto dfs = [&](auto &dfs,int nodo,int last,int e,long long prof)->void{
        id[e]=nodo;
        par[nodo][0]=last;
        pr[nodo]=prof;
        for(auto [to,x] : grafo[nodo]){
            if(to!=last){
                dfs(dfs,to,nodo,x,prof+1);
            }
        }
    };
    
    dfs(dfs,1,0,0,1);
    for(int j=1;j<LOGN;j++){ //build LCA (1-based)
        for(int i=0;i<=n;i++)
            par[i][j]=par[par[i][j-1]][j-1];
    }
    
    centroid();
    /*
    for(int i=1;i<=n;i++){
        cout<<"recap di "<<i<<"\n";
        for(auto [x,y,_] : v[i][0].ft){
            cout<<"nodo "<<y<<" a "<<x<<"\n";
        }
      }*/
    
    int q;
    cin>>q;
    
    vector lazy(n+1,0);
    
    auto update = [&](int nodo,int dist)->void{
        
        //cout<<"update "<<nodo<<"\n";
        
        //cout<<"+1 per "<<dist<<"\n";
        v[nodo][0].update(dist,1);
        
        for(auto [n,b,d] : g[nodo]){
            //cout<<"nodo "<<n<<"\n";
            //cout<<"+1 per "<<dist-d<<"\n";
            v[n][0].update(dist-d,1);
            
            //cout<<"ramo "<<b<<"\n";
            //cout<<"+1 per "<<dist-d<<"\n";
            v[n][b].update(dist-d,1);
        }
        
        int pos=nodo;
        for(int i=LOGN-1;i>=0;i--){
            if(pr[pos]-pr[par[pos][i]]<=dist){
                dist-=pr[pos]-pr[par[pos][i]];
                pos=par[pos][i];
            }
        }
        lazy[pos]++;
    };
    
    auto query = [&](int nodo){
        
        //cout<<"query "<<nodo<<"\n";
        int res=0;
        
        //cout<<"aggiungo "<<v[nodo][0].query(nodo)<<"\n";
        res+=v[nodo][0].query(nodo);
        
        for(auto [n,b,d] : g[nodo]){
            //cout<<"nodo "<<n<<"\n";
            //cout<<"aggiungo "<<v[n][0].query(nodo)<<"\n";
            //cout<<"ramo "<<b<<"\n";
            //cout<<"tolgo "<<v[n][b].query(nodo)<<"\n";
            res+=v[n][0].query(nodo);
            res-=v[n][b].query(nodo);
        }
        
        return res-lazy[nodo];
    };
    
    for(int i=0;i<q;i++){
        char c;
        cin>>c;
        if(c=='+'){
            int x,r;
            cin>>x>>r;
            update(x,r);
        }else{
            int y;
            cin>>y;
            
            cout<<query(id[y])<<"\n";
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t=1;
    //cin>>t;
    for(int i=1;i<=t;i++)solve(i);
    
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 991ms
memory: 204332kb

input:

100000
2670 75097 4080
87477 75802 1712
51835 36626 2883
19412 25923 5852
23976 19312 2520
82536 19514 2492
27160 66601 4483
99087 15088 3504
47050 58820 2964
37063 5696 9901
7717 1496 4891
79136 5448 4340
22575 81285 9289
96280 3803 9877
41980 32139 2855
44236 64938 3298
5983 99947 9666
95856 62545...

output:

0
0
0
2
2
5
2
2
3
4
4
7
8
9
11
10
14
12
12
10
11
10
10
9
10
11
11
9
15
11
14
13
14
16
11
17
15
13
15
14
14
20
15
20
22
22
20
17
23
23
24
29
24
26
30
31
36
28
37
39
35
34
45
39
46
45
43
46
42
49
44
50
43
47
52
50
49
57
51
56
61
58
68
66
69
69
61
63
67
63
72
74
78
72
73
78
77
73
85
76
86
82
85
76
82
8...

result:

wrong answer 960th lines differ - expected: '875', found: '876'