oj.uz

Submission #879006

# Submission time Handle Problem Language Result Execution time Memory
879006 2023-11-26T04:41:06 Z _anhxinloi_ Janjetina (COCI21_janjetina) C++14
15 / 110
 1500 ms 421940 KB 
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int maxn = 1e5 + 5;
typedef pair<int, int> pii;

int n, k, pa[maxn], child[maxn], ans;
vector<pii> adj[maxn], g[maxn];
int bit[2*maxn];
bool check[maxn];

void update(int idx, int val){
    for(++idx; idx <= 100000; idx += idx&(-idx))
        bit[idx] += val;
}
int get(int idx){
    int ret = 0;
    for(++idx; idx > 0; idx -= idx&(-idx))
        ret += bit[idx];
    return ret;
}

int dfs_sz(int u, int par){
    child[u] = 1;
    for(auto z : adj[u]){
        auto [w, v] = z;
        if(v == par || check[v])
            continue;
        child[u] += dfs_sz(v, u);
    }
    return child[u];
}

int centroid(int v, int prt, int tot){
    for(auto u : g[v])
        if(u.se != prt && !check[u.se] && child[u.se]*2 >= tot)
            return centroid(u.se, v, tot);
    return v;
}

void dfs_work(int u, int par, int val, int dist, int top){
    g[top].push_back(make_pair(val, dist));
    for(auto z : adj[u]){
        auto [w, v] = z;
        if(v == par || check[v])
            continue;
        dfs_work(v, u, max(val, w), dist+1, top);
    }
}

void build(int u, int par){
    int sz = dfs_sz(u, par);
    int center = centroid(u, par, sz);
//    cout << u << endl;
    pa[center] = u;

    vector<pii> vec = {};
    for(auto z : adj[center]){
        auto [w, v] = z;
        if(check[v])
            continue;
        dfs_work(v, u, w, 1, v);
        sort(g[v].begin(), g[v].end());

        for(auto z : g[v]){
            auto [val, dist] = z;
            int cur = val - dist - k;
            if(cur >= 0){
                ++ans;
                ans -= get(cur);
            }
            update(dist, 1);
        }

        for(auto z : g[v]){
            auto [val, dist] = z;
            update(dist, -1);
            vec.push_back(z);
        }
    }

    sort(vec.begin(), vec.end());
    for(auto z : vec){
        auto [val, dist] = z;
        int cur = val - dist - k;
        if(cur >= 0){
            ans += get(cur);
        }
        update(dist, 1);
    }

    for(auto z : vec){
        auto [val, dist] = z;
        update(dist, -1);
    }

    for(auto z : adj[center]){
        auto [w, v] = z;
        g[v].clear();
    }

    check[center] = true;
    for(auto z : adj[center]){
        auto [w, v] = z;
        if(!check[v])
            build(v, center);
    }
}

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

    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

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

    build(1, -1);
    cout << ans * 2;
}

Compilation message

Main.cpp: In function 'long long int dfs_sz(long long int, long long int)':
Main.cpp:30:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |         auto [w, v] = z;
      |              ^
Main.cpp: In function 'void dfs_work(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |         auto [w, v] = z;
      |              ^
Main.cpp: In function 'void build(long long int, long long int)':
Main.cpp:63:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |         auto [w, v] = z;
      |              ^
Main.cpp:70:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |             auto [val, dist] = z;
      |                  ^
Main.cpp:80:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |             auto [val, dist] = z;
      |                  ^
Main.cpp:88:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |         auto [val, dist] = z;
      |              ^
Main.cpp:97:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |         auto [val, dist] = z;
      |              ^
Main.cpp:102:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |         auto [w, v] = z;
      |              ^
Main.cpp:108:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |         auto [w, v] = z;
      |              ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 64 ms 26960 KB Output is correct
5 Correct 56 ms 26964 KB Output is correct
6 Correct 58 ms 26964 KB Output is correct
7 Correct 58 ms 26964 KB Output is correct
8 Correct 75 ms 26828 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6620 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 6 ms 7452 KB Output is correct
13 Correct 6 ms 7512 KB Output is correct
14 Correct 8 ms 7580 KB Output is correct
15 Correct 3 ms 6748 KB Output is correct
16 Correct 2 ms 6748 KB Output is correct
17 Correct 3 ms 6748 KB Output is correct
18 Correct 3 ms 6748 KB Output is correct
19 Correct 3 ms 6748 KB Output is correct
20 Correct 3 ms 6748 KB Output is correct
21 Correct 3 ms 6748 KB Output is correct
22 Correct 4 ms 6748 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6724 KB Output is correct
4 Correct 63 ms 26812 KB Output is correct
5 Execution timed out 1592 ms 421940 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 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 64 ms 26960 KB Output is correct
5 Correct 56 ms 26964 KB Output is correct
6 Correct 58 ms 26964 KB Output is correct
7 Correct 58 ms 26964 KB Output is correct
8 Correct 75 ms 26828 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6620 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 6 ms 7452 KB Output is correct
13 Correct 6 ms 7512 KB Output is correct
14 Correct 8 ms 7580 KB Output is correct
15 Correct 3 ms 6748 KB Output is correct
16 Correct 2 ms 6748 KB Output is correct
17 Correct 3 ms 6748 KB Output is correct
18 Correct 3 ms 6748 KB Output is correct
19 Correct 3 ms 6748 KB Output is correct
20 Correct 3 ms 6748 KB Output is correct
21 Correct 3 ms 6748 KB Output is correct
22 Correct 4 ms 6748 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6492 KB Output is correct
25 Correct 2 ms 6724 KB Output is correct
26 Correct 63 ms 26812 KB Output is correct
27 Execution timed out 1592 ms 421940 KB Time limit exceeded
28 Halted 0 ms 0 KB -