Submission #402373

#	Time	Username	Problem	Language	Result	Execution time	Memory
402373		jhnah917	Unique Cities (JOI19_ho_t5)	C++14	68 / 100	1719 ms	46000 KiB

joi2019_ho_t5

#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];

int D[2020], SR[2020], Use[2020];
int BFS(int st){
    memset(SR, 0, sizeof SR);
    memset(D, -1, sizeof D);
    memset(Use, 0, sizeof Use);
    queue<int> Q; Q.push(st); D[st] = 0;
    while(Q.size()){
        int v = Q.front(); Q.pop();
        if(!SR[D[v]]) SR[D[v]] = C[v];
        else SR[D[v]] = -1;
        for(auto i : G[v]) if(D[i] == -1) Q.push(i), D[i] = D[v] + 1;
    }
    for(int i=1; i<=N; i++) if(SR[i] > 0) Use[SR[i]] = 1;
    return accumulate(Use+1, Use+M+1, 0);
}

void Naive(){
    for(int i=1; i<=N; i++) cout << BFS(i) << "\n";
}

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];
    if(N <= 2000){ Naive(); return 0; }
    auto [u,v] = Diameter();

    Solve(u); Solve(v);
    for(int i=1; i<=N; i++) cout << min(R[i], M) << "\n";
}

Compilation message (stderr)

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

• Subtask 1: 4 / 4
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 0 / 32