oj.uz

Submission #890134

# Submission time Handle Problem Language Result Execution time Memory
890134 2023-12-20T15:24:43 Z hafo Unique Cities (JOI19_ho_t5) C++14
64 / 100
 738 ms 58468 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 7;
const ll oo = 1e9 + 69;

int n, m, u, v, a[maxn], dep[maxn], mx_dep[maxn], res[maxn];
vector<int> g[maxn];

struct ST {
    struct node {
        int mn, cnt;
        friend node operator + (node a, node b) {
            if(mini(a.mn, b.mn)) a.cnt = b.cnt;
            else if(a.mn == b.mn) a.cnt += b.cnt;
            return a;
        }

    };

    node st[4 * maxn];
    int lz[4 * maxn];

    void fix(int id, int l, int r) {
        if(!lz[id]) return;
        st[id].mn += lz[id];
        if(l != r) {
            lz[id << 1] += lz[id];
            lz[id << 1 | 1] += lz[id];
        }
        lz[id] = 0;
    }

    void build(int id, int l, int r) {
        if(l == r) {
            st[id] = {0, 1};
            return;
        }
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }

    void update(int id, int l, int r, int u, int v, int val) {
        fix(id, l, r);
        if(r < u || l > v) return;
        if(u <= l && r <= v) {
            lz[id] = val;
            fix(id, l, r);
            return;
        }
        int mid = l + r >> 1;
        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid + 1, r, u, v, val);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }

    node get(int id, int l, int r, int u, int v) {
        fix(id, l, r);
        if(r < u || l > v) return {oo, 0};
        if(u <= l && r <= v) return st[id];
        int mid = l + r >> 1;
        return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
    }

} st;

void dfs(int u, int par) {
    mx_dep[u] = 0;
    for(auto v:g[u]) {
        if(v == par) continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
        maxi(mx_dep[u], mx_dep[v] + 1);
    }
}

void dfs2(int u, int par) {
    auto tmp = st.get(1, 1, n, 1, dep[u] - mx_dep[u] - 1);
    if(tmp.mn == 0) maxi(res[u], tmp.cnt);

    for(auto v:g[u]) {
        if(v == par) continue;
        st.update(1, 1, n, dep[u] - mx_dep[v] - 1, dep[u] - 1, 1);
    }

    for(auto v:g[u]) {
        if(v == par) continue;
        st.update(1, 1, n, dep[u] - mx_dep[v] - 1, dep[u] - 1, -1);
        dfs2(v, u);
        st.update(1, 1, n, dep[u] - mx_dep[v] - 1, dep[u] - 1, 1);
    }

    for(auto v:g[u]) {
        if(v == par) continue;
        st.update(1, 1, n, dep[u] - mx_dep[v] - 1, dep[u] - 1, -1);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    cin>>n>>m;
    for(int i = 1; i < n; i++) {
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    for(int i = 1; i <= n; i++) cin>>a[i];

    dep[1] = 1;
    dfs(1, 0);
    int mx = -1, l = 0;
    for(int i = 1; i <= n; i++) {
        if(maxi(mx, dep[i])) l = i;
    }

    dep[l] = 1;
    dfs(l, 0);
    mx = -1;
    int r = 0;
    for(int i = 1; i <= n; i++) {
        if(maxi(mx, dep[i])) r = i;
    }

    st.build(1, 1, n);
    dep[l] = 1;
    dfs(l, 0);
    dfs2(l, 0);

    dep[r] = 1;
    dfs(r, 0);
    dfs2(r, 0);

    for(int i = 1; i <= n; i++) cout<<min(m, res[i])<<"\n";
    return 0;
}

Compilation message

joi2019_ho_t5.cpp: In member function 'void ST::build(int, int, int)':
joi2019_ho_t5.cpp:54:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         int mid = l + r >> 1;
      |                   ~~^~~
joi2019_ho_t5.cpp: In member function 'void ST::update(int, int, int, int, int, int)':
joi2019_ho_t5.cpp:68:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |         int mid = l + r >> 1;
      |                   ~~^~~
joi2019_ho_t5.cpp: In member function 'ST::node ST::get(int, int, int, int, int)':
joi2019_ho_t5.cpp:78:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Incorrect 5 ms 8796 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 16724 KB Output is correct
2 Correct 343 ms 35384 KB Output is correct
3 Correct 70 ms 14400 KB Output is correct
4 Correct 504 ms 23124 KB Output is correct
5 Correct 738 ms 56488 KB Output is correct
6 Correct 695 ms 39740 KB Output is correct
7 Correct 469 ms 23244 KB Output is correct
8 Correct 515 ms 26704 KB Output is correct
9 Correct 525 ms 25424 KB Output is correct
10 Correct 553 ms 25364 KB Output is correct
11 Correct 357 ms 23948 KB Output is correct
12 Correct 653 ms 43856 KB Output is correct
13 Correct 594 ms 39472 KB Output is correct
14 Correct 671 ms 38604 KB Output is correct
15 Correct 353 ms 23716 KB Output is correct
16 Correct 612 ms 45648 KB Output is correct
17 Correct 720 ms 39932 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 21708 KB Output is correct
2 Correct 697 ms 56132 KB Output is correct
3 Correct 80 ms 14924 KB Output is correct
4 Correct 495 ms 24148 KB Output is correct
5 Correct 727 ms 58468 KB Output is correct
6 Correct 711 ms 40852 KB Output is correct
7 Correct 499 ms 24020 KB Output is correct
8 Correct 556 ms 31060 KB Output is correct
9 Correct 520 ms 28544 KB Output is correct
10 Correct 584 ms 26760 KB Output is correct
11 Correct 433 ms 24400 KB Output is correct
12 Correct 704 ms 51284 KB Output is correct
13 Correct 558 ms 38604 KB Output is correct
14 Correct 715 ms 38852 KB Output is correct
15 Correct 371 ms 24688 KB Output is correct
16 Correct 643 ms 47232 KB Output is correct
17 Correct 673 ms 40948 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Incorrect 5 ms 8796 KB Output isn't correct
3 Halted 0 ms 0 KB -