oj.uz

Submission #402354

# Submission time Handle Problem Language Result Execution time Memory
402354 2021-05-11T15:56:05 Z jhnah917 Unique Cities (JOI19_ho_t5) C++14
64 / 100
 1726 ms 49780 KB 
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

using PII = pair<int,int>;
constexpr int SZ = 1 << 18;

int N, M, C[SZ], R[SZ];
vector<int> G[SZ];

PII T[SZ << 1]; int L[SZ << 1];
PII Merge(const PII &l, const PII &r){
    return l.x == r.x ? PII(l.x, l.y + r.y) : min(l, r);
}
void Push(int node, int s, int e){
    T[node].x += L[node];
    if(s != e) L[node<<1] += L[node], L[node<<1|1] += L[node];
    L[node] = 0;
}
void Init(int node=1, int s=1, int e=N){
    L[node] = 0;
    if(s == e){ T[node] = {0, 1}; return; }
    int m = s + e >> 1;
    Init(node<<1, s, m);
    Init(node<<1|1, m+1, e);
    T[node] = Merge(T[node<<1], T[node<<1|1]);
}
void Update(int l, int r, int v, int node=1, int s=1, int e=N){
    Push(node, s, e);
    if(r < s || e < l) return;
    if(l <= s && e <= r){ L[node] += v; Push(node, s, e); return; }
    int m = s + e >> 1;
    Update(l, r, v, node<<1, s, m);
    Update(l, r, v, node<<1|1, m+1, e);
    T[node] = Merge(T[node<<1], T[node<<1|1]);
}
PII Query(int l, int r, int node=1, int s=1, int e=N){
    Push(node, s, e);
    if(r < s || e < l) return T[0];
    if(l <= s && e <= r) return T[node];
    int m = s + e >> 1;
    return Merge(Query(l, r, node<<1, s, m), Query(l, r, node<<1|1, m+1, e));
}

PII Diameter(int root=1){
    function<PII(int,int,int)> dfs_far = [&dfs_far](int v, int b, int d){
        PII ret(d, v);
        for(auto i : G[v]) if(i != b) ret = max(ret, dfs_far(i, v, d+1));
        return ret;
    };
    int t1 = dfs_far(root, -1, 0).y;
    int t2 = dfs_far(t1, -1, 0).y;
    return {t1, t2};
}

int Dep[SZ]; PII Sub[SZ];
void dfs_info(int v, int b=-1){
    Sub[v] = {0, v};
    for(auto i : G[v]){
        if(i == b) continue;
        Dep[i] = Dep[v] + 1;
        dfs_info(i, v);
        Sub[v] = max(Sub[v], PII(Sub[i].x+1, Sub[i].y));
    }
}
void dfs_calc(int v, int b=-1){
    auto [mn,cnt] = Query(1, Dep[v]-Sub[v].x-1);
    if(mn == 0) R[v] = max(R[v], cnt);
    for(auto i : G[v]){
        if(i == b) continue;
        Update(Dep[v]-Sub[i].x-1, Dep[v]-1, +1);
    }
    for(auto i : G[v]){
        if(i == b) continue;
        Update(Dep[v]-Sub[i].x-1, Dep[v]-1, -1);
        dfs_calc(i, v);
        Update(Dep[v]-Sub[i].x-1, Dep[v]-1, +1);
    }
    for(auto i : G[v]){
        if(i == b) continue;
        Update(Dep[v]-Sub[i].x-1, Dep[v]-1, -1);
    }
}
void Solve(int st){
    Dep[st] = 1;
    dfs_info(st);
    Init();
    dfs_calc(st);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1,s,e; i<N; i++) cin >> s >> e, G[s].push_back(e), G[e].push_back(s);
    for(int i=1; i<=N; i++) cin >> C[i];
    auto [u,v] = Diameter();
    
    Solve(u); Solve(v);
    for(int i=1; i<=N; i++) cout << min(R[i], M) << "\n";
}

Compilation message

joi2019_ho_t5.cpp: In function 'void Init(int, int, int)':
joi2019_ho_t5.cpp:24:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |     int m = s + e >> 1;
      |             ~~^~~
joi2019_ho_t5.cpp: In function 'void Update(int, int, int, int, int, int)':
joi2019_ho_t5.cpp:33:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |     int m = s + e >> 1;
      |             ~~^~~
joi2019_ho_t5.cpp: In function 'PII Query(int, int, int, int, int)':
joi2019_ho_t5.cpp:42:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |     int m = s + e >> 1;
      |             ~~^~~
joi2019_ho_t5.cpp: In function 'void dfs_calc(int, int)':
joi2019_ho_t5.cpp:68:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |     auto [mn,cnt] = Query(1, Dep[v]-Sub[v].x-1);
      |          ^
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:97:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |     auto [u,v] = Diameter();
      |          ^

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6476 KB Output is correct
2 Incorrect 11 ms 6648 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 648 ms 17248 KB Output is correct
2 Correct 867 ms 29712 KB Output is correct
3 Correct 177 ms 10632 KB Output is correct
4 Correct 1324 ms 26228 KB Output is correct
5 Correct 1726 ms 48008 KB Output is correct
6 Correct 1677 ms 37076 KB Output is correct
7 Correct 1219 ms 26296 KB Output is correct
8 Correct 1328 ms 28448 KB Output is correct
9 Correct 1290 ms 27736 KB Output is correct
10 Correct 1303 ms 27672 KB Output is correct
11 Correct 1167 ms 26944 KB Output is correct
12 Correct 1486 ms 39804 KB Output is correct
13 Correct 1357 ms 36892 KB Output is correct
14 Correct 1548 ms 36308 KB Output is correct
15 Correct 1088 ms 26804 KB Output is correct
16 Correct 1538 ms 41012 KB Output is correct
17 Correct 1530 ms 37232 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 933 ms 23952 KB Output is correct
2 Correct 1617 ms 48076 KB Output is correct
3 Correct 179 ms 11172 KB Output is correct
4 Correct 1292 ms 27120 KB Output is correct
5 Correct 1658 ms 49780 KB Output is correct
6 Correct 1668 ms 38208 KB Output is correct
7 Correct 1228 ms 27048 KB Output is correct
8 Correct 1354 ms 31784 KB Output is correct
9 Correct 1284 ms 30256 KB Output is correct
10 Correct 1348 ms 28868 KB Output is correct
11 Correct 1215 ms 27424 KB Output is correct
12 Correct 1598 ms 45216 KB Output is correct
13 Correct 1351 ms 36796 KB Output is correct
14 Correct 1508 ms 37056 KB Output is correct
15 Correct 1090 ms 27964 KB Output is correct
16 Correct 1435 ms 42400 KB Output is correct
17 Correct 1564 ms 38372 KB Output is correct

Subtask #4
0 / 32.0

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