Submission #474673

#	Time	Username	Problem	Language	Result	Execution time	Memory
474673		mychecksedad	Janjetina (COCI21_janjetina)	C++17	15 / 110	20 ms	3276 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 1e5+10;



int n, k, s[N], parent[N], rmq[N][22], r[N];
pair<int, int> arr[N];
ll ans = 0;
vector<pair<int, int>> g[N];
void dfs(int v, int p, int mx, int d){
    for(auto u: g[v]){
        if(u.first != p){
            if(max(mx, u.second) - d - 1 >= k) ++ans;
            dfs(u.first, v, max(mx, u.second), d+1);
        }
    }
}
int find_set(int v){
    if(parent[v] == v) return v;
    return parent[v] = find_set(parent[v]);
}
void union_set(int a, int b){
    a = find_set(a);
    b = find_set(b);
    if(a != b){
        if(s[a] < s[b]) swap(a, b);
        parent[b] = a;
        s[a] += s[b]; 
    }
}
void precalc(){
    for(int i = 1; i < n; i++) rmq[i][0] = r[i];
    for(int j = 1; j < 22; j++){
        for(int i = 1; i <= n; i++){
            rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1<<j)][j - 1]);
        }
    }
}
int mx(int x, int y){
    int k = __lg(y - x + 1);
    return max(rmq[x][k], rmq[y - (1<<k) + 1][k]);
}
int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    cin >> n >> k;
    for(int i = 0; i < n-1; i++){
        int a, b, w;
        cin >> a >> b >> w;
        arr[i + 1] = {w, i};
        r[i + 1] = w; 
        g[a].pb({b, w});
        g[b].pb({a, w});
    }
    // precalc();
    if(n <= 1000){
        for(int i = 1; i <= n; i++) dfs(i, 0, 0, 0);

    }else{
        sort(arr + 1, arr + n);
        for(int i = 1; i <= n; i++){
            s[i] = 1;
            parent[i] = i;
        }
        for(int i = 1; i < n; i++){
            int pos = arr[i].second;
            int x = s[find_set(pos)];
            int y = s[find_set(pos+1)];
            int t = mx(pos - x + 1, pos + 1 + y - 2) - k;
            if(x <= t){
                ans += ll(x) * ll(t - x + 1);
                // ans += 
            }
            else{
                ans += ll(min(t, y)) * ll((min(t, y) + 1) / 2);
            }
            union_set(i, i+1);
        }
    }
    cout << ans;

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 35
• Subtask 3: 0 / 60