oj.uz

Submission #1039645

# Submission time Handle Problem Language Result Execution time Memory
1039645 2024-07-31T06:52:26 Z 정민찬(#10992) Petrol stations (CEOI24_stations) C++17
18 / 100
 884 ms 21356 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

struct SegmentTree{
    vector<ll> tree;
    void init(ll n) {
        ll sz = 1 << __lg(n-1) + 2;
        tree.assign(sz, 0);
    }
    void update(ll node, ll s, ll e, ll tar, ll val) {
        if (s > tar || tar > e) return;
        if (s == e) {
            tree[node] = val;
            return;
        }
        ll mid = s + e >> 1;
        update(node*2, s, mid, tar, val);
        update(node*2+1, mid+1, e, tar, val);
        tree[node] = tree[node*2] + tree[node*2+1];
    }
    ll query(ll node, ll s, ll e, ll l, ll r) {
        if (l > e || s > r) return 0;
        if (l <= s && e <= r) return tree[node];
        ll mid = s + e >> 1;
        return query(node*2, s, mid, l, r) + query(node*2+1, mid+1, e, l, r);
    }
    ll Findright(ll node, ll s, ll e, ll k) {
        if (s == e) {
            if (tree[node] >= k) return s;
            return 0;
        }
        ll mid = s + e >> 1;
        if (tree[node*2+1] >= k) return Findright(node*2+1, mid+1, e, k);
        return Findright(node*2, s, mid, k-tree[node*2+1]);
    }
};

vector<pll> adj[70010];
ll sz[70010];
ll chk[70010];

ll getSize(ll x, ll p) {
    sz[x] = 1;
    for (auto &[y, _] : adj[x]) {
        if (y == p || chk[y]) continue;
        sz[x] += getSize(y, x);
    }
    return sz[x];
}

ll getCent(ll x, ll p, ll cap) {
    for (auto &[y, _] : adj[x]) {
        if (y == p || chk[y]) continue;
        if (sz[y] * 2 > cap) return getCent(y, x, cap);
    }
    return x;
}

ll N, K;

SegmentTree seg;
vector<ll> vtx;
ll ans[70010];
ll dp[70010], dp2[70010];

// go up
void dfs(ll x, ll p, ll dep) {
    vtx.push_back(x);
    dp[x] = 0;
    if (seg.tree[1] > K) {
        ll pos = seg.Findright(1, 1, N, K+1);
        assert(pos >= 1);
        assert(seg.query(1, 1, N, pos+1, N) <= K);
        assert(seg.query(1, 1, N, pos, N) > K);
        dp2[x] = dp2[vtx[pos]];
    }
    else {
        dp2[x] = K - seg.tree[1];
    }
    for (auto &[y, z] : adj[x]) {
        if (y == p || chk[y]) continue;
        seg.update(1, 1, N, dep, z);
        dfs(y, x, dep+1);
        seg.update(1, 1, N, dep, 0);
    }
    if (seg.tree[1] > K) {
        ll pos = seg.Findright(1, 1, N, K+1);
        dp[vtx[pos]] += dp[x] + 1;
    }
    vtx.pop_back();
}

ll dp3[70010];
vector<ll> vals, vals2;
SegmentTree seg2;

void dfs3(ll x, ll p, vector<ll> &vec) {
    vec.push_back(dp2[x]);
    for (auto &[y, z] : adj[x]) {
        if (y == p || chk[y]) continue;
        dfs3(y, x, vec);
    }
}

// go down
void dfs2(ll x, ll p, ll dep, ll e) {
    seg.update(1, 1, N, dep-1, e);
    dp3[x] = 0;
    if (seg.tree[1] > K) {
        ll rpos = seg.Findright(1, 1, N, K+1);
        ll lpos = seg.Findright(1, 1, N, K+e+1) + 1;
        if (lpos <= rpos) {
            dp3[x] = seg2.query(1, 1, N, lpos, rpos);
        }
    }
    if (seg.tree[1] <= K+e) {
        ll d = seg.tree[1] - e;
        dp3[x] += upper_bound(vals.begin(), vals.end(), d+e-1) - lower_bound(vals.begin(), vals.end(), d);
        dp3[x] -= upper_bound(vals2.begin(), vals2.end(), d+e-1) - lower_bound(vals2.begin(), vals2.end(), d);
    }
    seg2.update(1, 1, N, dep-1, dp3[x]);
    for (auto &[y, z] : adj[x]) {
        if (y == p || chk[y]) continue;
        dfs2(y, x, dep+1, z);
    }
    seg2.update(1, 1, N, dep-1, 0);
    seg.update(1, 1, N, dep-1, 0);
}

void dfs4(ll x, ll p) {
    for (auto &[y, _] : adj[x]) {
        if (y == p || chk[y]) continue;
        ans[x] += dp3[y] * sz[y];
        dfs4(y, x);
    }
}

void dfs5(ll x, ll p, ll ssz) {
    ans[x] += dp[x] * ssz;
    for (auto &[y, _] : adj[x]) {
        if (y == p || chk[y]) continue;
        dfs5(y, x, ssz);
    }
}

void dnc(ll x) {
    x = getCent(x, -1, getSize(x, -1));
    getSize(x, -1);
    dfs(x, -1, 1);
    vals.clear();
    dfs3(x, -1, vals);
    sort(vals.begin(), vals.end());
    for (auto &[y, z] : adj[x]) {
        if (chk[y]) continue;
        vals2.clear();
        dfs3(y, x, vals2);
        sort(vals2.begin(), vals2.end());
        dfs2(y, x, 2, z);
    }
    dfs4(x, -1);
    for (auto &[y, _] : adj[x]) {
        if (chk[y]) continue;
        dfs5(y, x, sz[x] - sz[y]);
    }
    chk[x] = 1;
    for (auto &[y, _] : adj[x]) {
        if (!chk[y])
            dnc(y);
    }
}

int main() {
    scanf("%lld %lld", &N, &K);
    for (ll i=0; i<N-1; i++) {
        ll u, v, l;
        scanf("%lld %lld %lld", &u, &v, &l);
        u ++; v ++;
        adj[u].push_back({v, l});
        adj[v].push_back({u, l});
    }
    seg.init(N);
    seg2.init(N);
    dnc(1);
    for (ll i=1; i<=N; i++) {
        printf("%d\n", ans[i]);
    }
}

Compilation message

Main.cpp: In member function 'void SegmentTree::init(ll)':
Main.cpp:10:32: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   10 |         ll sz = 1 << __lg(n-1) + 2;
      |                      ~~~~~~~~~~^~~
Main.cpp: In member function 'void SegmentTree::update(ll, ll, ll, ll, ll)':
Main.cpp:19:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |         ll mid = s + e >> 1;
      |                  ~~^~~
Main.cpp: In member function 'll SegmentTree::query(ll, ll, ll, ll, ll)':
Main.cpp:27:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |         ll mid = s + e >> 1;
      |                  ~~^~~
Main.cpp: In member function 'll SegmentTree::Findright(ll, ll, ll, ll)':
Main.cpp:35:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         ll mid = s + e >> 1;
      |                  ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:188:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll' {aka 'long long int'} [-Wformat=]
  188 |         printf("%d\n", ans[i]);
      |                 ~^     ~~~~~~
      |                  |          |
      |                  int        ll {aka long long int}
      |                 %lld
Main.cpp:176:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |     scanf("%lld %lld", &N, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:179:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |         scanf("%lld %lld %lld", &u, &v, &l);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 3 ms 2140 KB Output is correct
4 Correct 3 ms 2140 KB Output is correct
5 Correct 3 ms 2276 KB Output is correct
6 Correct 5 ms 2136 KB Output is correct
7 Correct 4 ms 2140 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 3 ms 2140 KB Output is correct
10 Correct 3 ms 2132 KB Output is correct
11 Correct 3 ms 2140 KB Output is correct
12 Correct 3 ms 2140 KB Output is correct
13 Correct 3 ms 2140 KB Output is correct
14 Correct 2 ms 2136 KB Output is correct

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Incorrect 884 ms 21356 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 1 ms 1884 KB Output is correct
4 Incorrect 884 ms 21356 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 645 ms 15276 KB Output is correct
4 Incorrect 860 ms 21056 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 645 ms 15276 KB Output is correct
4 Incorrect 860 ms 21056 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 3 ms 2140 KB Output is correct
4 Correct 3 ms 2140 KB Output is correct
5 Correct 3 ms 2276 KB Output is correct
6 Correct 5 ms 2136 KB Output is correct
7 Correct 4 ms 2140 KB Output is correct
8 Correct 1 ms 1884 KB Output is correct
9 Correct 3 ms 2140 KB Output is correct
10 Correct 3 ms 2132 KB Output is correct
11 Correct 3 ms 2140 KB Output is correct
12 Correct 3 ms 2140 KB Output is correct
13 Correct 3 ms 2140 KB Output is correct
14 Correct 2 ms 2136 KB Output is correct
15 Correct 1 ms 1884 KB Output is correct
16 Incorrect 884 ms 21356 KB Output isn't correct
17 Halted 0 ms 0 KB -