oj.uz

Submission #960572

# Submission time Handle Problem Language Result Execution time Memory
960572 2024-04-10T15:57:50 Z cpptowin Janjetina (COCI21_janjetina) C++17
110 / 110
 400 ms 51252 KB 
#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf (int)1e18
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1 << j))
#define onbit(i, j) (i | (1 << j))
#define vi vector<int>
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
struct BIT
{
    int t[maxn];
    void up(int x, int val)
    {
        x++;
        for (; x; x -= lb(x))
            t[x] += val;
    }
    int get(int x)
    {
        int ans = 0;
        x++;
        for (; x < maxn; x += lb(x))
            ans += t[x];
        return ans;
    }
} t;
int n, k;
vii ke[maxn];
int ans;
// centroid decomposition
bool is_remove[maxn];
vii event;
int sz[maxn];
int d[maxn], val[maxn];
int dfs_size(int u, int parent = -1)
{
    sz[u] = 1;
    for (auto [v, w] : ke[u])
    {
        if (v == parent or is_remove[v])
            continue;
        sz[u] += dfs_size(v, u);
    }
    return sz[u];
}
int dfs_centroid(int u, int tree_size, int parent = 0)
{
    for (auto [v, w] : ke[u])
    {
        if (v == parent or is_remove[v])
            continue;
        if (2 * sz[v] > tree_size)
            return dfs_centroid(v, tree_size, u);
    }
    return u;
}
void dfs_dist(int u, int par, int dist, int maxx)
{
    for (auto [v, w] : ke[u])
    {
        if (v == par or is_remove[v])
            continue;
        dfs_dist(v, u, dist + 1, max(maxx, w));
    }
    event.pb(maxx, dist);
    d[u] = dist;
    val[u] = maxx;
}
void solve(int val)
{
    sort(event.begin(), event.end(), greater<pii>());
    for (auto [maxx, dist] : event)
    {
        // cout << maxx << ' ' << dist << "\n";
        ans += t.get(dist) * val;
        if (maxx - dist - k >= 0)
            t.up(maxx - dist - k, 1);
    }
    // cout << ans;en;
    // cout << "xxxxxxxx\n";
    for (auto [maxx, dist] : event)
    {
        if (maxx - dist - k >= 0)
            t.up(maxx - dist - k, -1);
    }
    event.clear();
}
vi child;
void dfs_set(int u, int parent = -1)
{
    child.pb(u);
    for (auto [v, w] : ke[u])
    {
        if (v == parent or is_remove[v])
            continue;
        dfs_set(v, u);
    }
}
void build_centroid(int u)
{
    u = dfs_centroid(u, dfs_size(u));
    is_remove[u] = 1;
    // do sth
    dfs_dist(u, u, 0, 0);
    solve(1);
    for (auto [v, w] : ke[u])
    {
        if (is_remove[v])
            continue;
        dfs_set(v);
        for (int it : child)
            event.pb(val[it], d[it]);
        solve(-1);
        child.clear();
    }
    for (auto [v, w] : ke[u])
    {
        if (is_remove[v])
            continue;
        build_centroid(v);
    }
}
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    fo(i, 1, n - 1)
    {
        int u, v, w;
        cin >> u >> v >> w;
        ke[u].pb(v, w);
        ke[v].pb(u, w);
    }
    build_centroid(1);
    cout << ans * 2;
}

Compilation message

Main.cpp:156:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  156 | main()
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:161:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:162:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31064 KB Output is correct
2 Correct 7 ms 31068 KB Output is correct
3 Correct 7 ms 31064 KB Output is correct
4 Correct 8 ms 31320 KB Output is correct
5 Correct 8 ms 31324 KB Output is correct
6 Correct 10 ms 31324 KB Output is correct
7 Correct 8 ms 31324 KB Output is correct
8 Correct 8 ms 31324 KB Output is correct
9 Correct 7 ms 31324 KB Output is correct
10 Correct 7 ms 31248 KB Output is correct
11 Correct 7 ms 31324 KB Output is correct
12 Correct 8 ms 31352 KB Output is correct
13 Correct 8 ms 31324 KB Output is correct
14 Correct 8 ms 31324 KB Output is correct
15 Correct 8 ms 31344 KB Output is correct
16 Correct 9 ms 31364 KB Output is correct
17 Correct 8 ms 31324 KB Output is correct
18 Correct 8 ms 31324 KB Output is correct
19 Correct 8 ms 31168 KB Output is correct
20 Correct 8 ms 31324 KB Output is correct
21 Correct 8 ms 31176 KB Output is correct
22 Correct 8 ms 31324 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31064 KB Output is correct
2 Correct 6 ms 31252 KB Output is correct
3 Correct 7 ms 31068 KB Output is correct
4 Correct 9 ms 31324 KB Output is correct
5 Correct 26 ms 32868 KB Output is correct
6 Correct 142 ms 40912 KB Output is correct
7 Correct 213 ms 50176 KB Output is correct
8 Correct 332 ms 50552 KB Output is correct
9 Correct 227 ms 50372 KB Output is correct
10 Correct 332 ms 50688 KB Output is correct
11 Correct 225 ms 50116 KB Output is correct
12 Correct 310 ms 50624 KB Output is correct
13 Correct 225 ms 50368 KB Output is correct
14 Correct 320 ms 51252 KB Output is correct
15 Correct 372 ms 50372 KB Output is correct
16 Correct 321 ms 50624 KB Output is correct
17 Correct 327 ms 50628 KB Output is correct
18 Correct 321 ms 50584 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31064 KB Output is correct
2 Correct 7 ms 31068 KB Output is correct
3 Correct 7 ms 31064 KB Output is correct
4 Correct 8 ms 31320 KB Output is correct
5 Correct 8 ms 31324 KB Output is correct
6 Correct 10 ms 31324 KB Output is correct
7 Correct 8 ms 31324 KB Output is correct
8 Correct 8 ms 31324 KB Output is correct
9 Correct 7 ms 31324 KB Output is correct
10 Correct 7 ms 31248 KB Output is correct
11 Correct 7 ms 31324 KB Output is correct
12 Correct 8 ms 31352 KB Output is correct
13 Correct 8 ms 31324 KB Output is correct
14 Correct 8 ms 31324 KB Output is correct
15 Correct 8 ms 31344 KB Output is correct
16 Correct 9 ms 31364 KB Output is correct
17 Correct 8 ms 31324 KB Output is correct
18 Correct 8 ms 31324 KB Output is correct
19 Correct 8 ms 31168 KB Output is correct
20 Correct 8 ms 31324 KB Output is correct
21 Correct 8 ms 31176 KB Output is correct
22 Correct 8 ms 31324 KB Output is correct
23 Correct 6 ms 31064 KB Output is correct
24 Correct 6 ms 31252 KB Output is correct
25 Correct 7 ms 31068 KB Output is correct
26 Correct 9 ms 31324 KB Output is correct
27 Correct 26 ms 32868 KB Output is correct
28 Correct 142 ms 40912 KB Output is correct
29 Correct 213 ms 50176 KB Output is correct
30 Correct 332 ms 50552 KB Output is correct
31 Correct 227 ms 50372 KB Output is correct
32 Correct 332 ms 50688 KB Output is correct
33 Correct 225 ms 50116 KB Output is correct
34 Correct 310 ms 50624 KB Output is correct
35 Correct 225 ms 50368 KB Output is correct
36 Correct 320 ms 51252 KB Output is correct
37 Correct 372 ms 50372 KB Output is correct
38 Correct 321 ms 50624 KB Output is correct
39 Correct 327 ms 50628 KB Output is correct
40 Correct 321 ms 50584 KB Output is correct
41 Correct 7 ms 31068 KB Output is correct
42 Correct 219 ms 50092 KB Output is correct
43 Correct 314 ms 50688 KB Output is correct
44 Correct 233 ms 50372 KB Output is correct
45 Correct 339 ms 50584 KB Output is correct
46 Correct 224 ms 50064 KB Output is correct
47 Correct 400 ms 50716 KB Output is correct
48 Correct 236 ms 50624 KB Output is correct
49 Correct 295 ms 50628 KB Output is correct
50 Correct 364 ms 50540 KB Output is correct
51 Correct 337 ms 50624 KB Output is correct
52 Correct 95 ms 44228 KB Output is correct
53 Correct 128 ms 44748 KB Output is correct
54 Correct 84 ms 44152 KB Output is correct
55 Correct 137 ms 44672 KB Output is correct
56 Correct 133 ms 44736 KB Output is correct
57 Correct 236 ms 44312 KB Output is correct
58 Correct 311 ms 44592 KB Output is correct
59 Correct 301 ms 44848 KB Output is correct
60 Correct 288 ms 44872 KB Output is correct
61 Correct 315 ms 44740 KB Output is correct
62 Correct 201 ms 44352 KB Output is correct
63 Correct 242 ms 44744 KB Output is correct
64 Correct 307 ms 44736 KB Output is correct
65 Correct 15 ms 31580 KB Output is correct
66 Correct 6 ms 31064 KB Output is correct