oj.uz

Submission #977495

# Submission time Handle Problem Language Result Execution time Memory
977495 2024-05-08T05:05:13 Z tnknguyen_ Janjetina (COCI21_janjetina) C++14
15 / 110
 1500 ms 58704 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n' 
#define ll long long 
#define len(s) (int)s.size() 
#define pii pair<int, int>
//#define int long long 

struct BIT{
    int n;
    vector<ll> f;

    BIT(int N = 1e5): n(N+5), f(N+5, 0) {};

    void update(int i, int val){
        while(i < n){
            f[i] += val;
            i += (i & -i);
        }
    }

    ll get(int i){
        ll ans = 0;
        while(i > 0){
            ans += f[i];
            i -= (i & -i);
        }
        return ans;
    }

    ll get(int l, int r){
        return get(r) - get(l-1);
    }
};

const int MX = 1e5 + 5;
vector<pii> gr[MX];
int del[MX], sz[MX], id[MX];
int n, k;
ll ans = 0;

int dfs(int u, int p){
    sz[u] = 1;
    for(pii e : gr[u]){
        int v = e.first;
        if(v != p && !del[v]){
            sz[u] += dfs(v, u);
        }
    }
    return sz[u];
}

int centroid(int u, int p, const int &n){
    for(pii e : gr[u]){
        int v = e.first;
        if(v != p && !del[v] && sz[v]*2 > n){
            return centroid(v, u, n);
        }
    }
    return u;
}

int idx = 0;
void solve(int u, int p, int len, int _max, vector<pair<pii, int>> &vals, const int &cent){
    vals.push_back({{_max, len}, u});
    id[u] = (p == cent ? ++idx : id[p]);

    for(pii e : gr[u]){
        int v, c;
        tie(v, c) = e;
        if(v != p && !del[v]){
            solve(v, u, len + 1, max(_max, c), vals, cent);
        }
    }
}

void decompose(int u){
    dfs(u, 0);
    u = centroid(u, 0, sz[u]);
    del[u] = 1;


    vector<pair<pii, int>> vals;
    idx = 0;
    for(pii e : gr[u]){
        int v, c;
        tie(v, c) = e;
        if(!del[v]){
            solve(v, u, 1, c, vals, u);
        }
    }

    vector<BIT> cnt(idx + 1);
    sort(vals.begin(), vals.end());

    BIT bit;
    int res = 0;
    for(pair<pii, int> p : vals){
        int w, l, u = p.second;
        tie(w, l) = p.first;
        int need = w - l - k;
        // cout<<u<<' '<<w<<' '<<l<<"\n";
        // cout<<"need: "<<need<<' '<<bit.get(need) - cnt[id[u]].get(need)<<"\n\n";
        res += (bit.get(need) - cnt[id[u]].get(need));
        res += (w - l >= k);

        bit.update(l, 1);
        cnt[id[u]].update(l, 1);
    }
    // cout<<"Current Centroid: "<<u<<"\n";
    // cout<<res<<"\n";
    ans += res;

    for(pii e : gr[u]){
        int v = e.first;
        if(!del[v]){
            decompose(v);
        }
    }
 }

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // freopen("main.inp","r",stdin);
    // freopen("main.out","w",stdout);

    cin>>n>>k;

    for(int i=1; i<n; ++i){
        int u, v, w;
        cin>>u>>v>>w;
        gr[u].push_back({v, w});
        gr[v].push_back({u, w});
    }

    decompose(1);
    cout<<ans*2;

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 67 ms 24308 KB Output is correct
4 Correct 658 ms 34228 KB Output is correct
5 Correct 650 ms 33968 KB Output is correct
6 Correct 642 ms 34044 KB Output is correct
7 Correct 656 ms 34136 KB Output is correct
8 Correct 665 ms 34248 KB Output is correct
9 Correct 629 ms 49556 KB Output is correct
10 Correct 630 ms 52620 KB Output is correct
11 Correct 629 ms 57364 KB Output is correct
12 Correct 664 ms 49396 KB Output is correct
13 Correct 665 ms 47020 KB Output is correct
14 Correct 656 ms 47716 KB Output is correct
15 Correct 662 ms 47108 KB Output is correct
16 Correct 658 ms 43916 KB Output is correct
17 Correct 656 ms 48668 KB Output is correct
18 Correct 666 ms 51688 KB Output is correct
19 Correct 669 ms 53252 KB Output is correct
20 Correct 649 ms 51020 KB Output is correct
21 Correct 656 ms 58704 KB Output is correct
22 Correct 671 ms 52812 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 71 ms 24328 KB Output is correct
4 Correct 652 ms 34348 KB Output is correct
5 Execution timed out 1558 ms 47404 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 67 ms 24308 KB Output is correct
4 Correct 658 ms 34228 KB Output is correct
5 Correct 650 ms 33968 KB Output is correct
6 Correct 642 ms 34044 KB Output is correct
7 Correct 656 ms 34136 KB Output is correct
8 Correct 665 ms 34248 KB Output is correct
9 Correct 629 ms 49556 KB Output is correct
10 Correct 630 ms 52620 KB Output is correct
11 Correct 629 ms 57364 KB Output is correct
12 Correct 664 ms 49396 KB Output is correct
13 Correct 665 ms 47020 KB Output is correct
14 Correct 656 ms 47716 KB Output is correct
15 Correct 662 ms 47108 KB Output is correct
16 Correct 658 ms 43916 KB Output is correct
17 Correct 656 ms 48668 KB Output is correct
18 Correct 666 ms 51688 KB Output is correct
19 Correct 669 ms 53252 KB Output is correct
20 Correct 649 ms 51020 KB Output is correct
21 Correct 656 ms 58704 KB Output is correct
22 Correct 671 ms 52812 KB Output is correct
23 Correct 2 ms 5208 KB Output is correct
24 Correct 3 ms 7516 KB Output is correct
25 Correct 71 ms 24328 KB Output is correct
26 Correct 652 ms 34348 KB Output is correct
27 Execution timed out 1558 ms 47404 KB Time limit exceeded
28 Halted 0 ms 0 KB -