Submission #1016001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016001		phong	Unique Cities (JOI19_ho_t5)	C++17	4 / 100	2085 ms	76816 KiB

joi2019_ho_t5

#include<bits/stdc++.h>

#define ll long long
const int nmax = 2e5 + 5, N = 4e5;
const ll oo = 1e18;
const int lg = 18, M = 4e3;
const int base = 2e5, mod = 1e9 + 7;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' ';cout << endl
using namespace std;

int n, m;
vector<int> adj[nmax];
int h[nmax], a[nmax], dep[nmax][2], H[nmax];

void dfs_1(int u, int p){
    for(auto v : adj[u]){
        if(v == p) continue;
        H[v] = H[u] + 1;
        dfs_1(v, u);

    }
}
void ckmax(int &a, int b){
    a = max(a, b);
}
vector<int> gg[nmax];
int sz[nmax], up[nmax][lg + 1], mx[nmax];
int nchain = 1, Time = 0, head[nmax], ind[nmax], pos[nmax];
void dfs_4(int u, int p, int id){
    sz[u] = 1;
    for(auto v : adj[u]){
        if(v == p) continue;
        dep[v][id] = dep[u][id] + 1;
        dfs_4(v, u, id);
        sz[u] += sz[v];
    }
}
int two[nmax];

void dfs_2(int u, int p){
    if(!head[nchain])head[nchain] = u;
    ind[u] = nchain;
    pos[u] = ++Time;
    two[Time] = u;
    int idx = -1;
    for(auto v : adj[u]){
        if(v == p) continue;
        up[v][0] = u;
        for(int j = 1; j <= lg; ++j) up[v][j] = up[up[v][j - 1]][j - 1];
        if(idx == -1 || sz[v] > sz[idx]){
            idx = v;
        }
    }
    if(idx != -1){
        int v = idx;
        dfs_2(v, u);
        h[u] = max(h[u], h[v] + 1);
    }
    for(auto v : adj[u]){
        if(v == p || v == idx) continue;
        ++nchain;
        dfs_2(v, u);
        h[u] = max(h[u], h[v] + 1);
    }
    int ma = 0;
    for(auto v : adj[u]){
        if(v == p) continue;
        mx[v] = max(mx[v], ma);

        ma = max(ma, h[v] + 1);
    }
    reverse(adj[u].begin(), adj[u].end());
    ma = 0;
    for(auto v : adj[u]){
        if(v == p) continue;
        mx[v] = max(mx[v], ma);
        ma = max(ma, h[v] + 1);
    }
    sort(adj[u].begin(), adj[u].end(),[](int a, int b){
         return mx[a] > mx[b];
         });
}

int ans[nmax][2];
struct BIT{
    int f[nmax];

    void update(int x, int val){
        ++x;
        for(; x <= n; x += x&-x) f[x] += val;
    }
    int get(int x){
        ++x;
        int res = 0;
        for(; x; x -= x&-x) res += f[x];
        return res;
    }
}F;
struct holder{
    int c[nmax], ans = 0;
    vector<int> tmp;
    void add(int u, int d, int lc){
        if(c[a[u]] == -1){
            F.update(d, 1);
            c[a[u]] = d;
        }
    }
    void erase(int u, int d, int lc){
//        cout << u << ' ' << c[a[u]] << ' ' << lc << endl;
//        cout <<
        if(c[a[u]] == d){
            F.update(c[a[u]], -1);
//            cout << c[1] << ' ';
//        cout << F.get(2) << ' ';
            c[a[u]] = -1;
        }
    }

}one;
int tree[nmax << 2], lz[nmax << 2];
void build(int id, int l, int r){
    tree[id] = lz[id] = 0;
    if(l == r){
        return;
    }
    int mid = r + l >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
}
void fix(int id, int val){
    tree[id] += val;
    lz[id] += val;
}
void down(int id){
    fix(id << 1,lz[id]);
    fix(id << 1 | 1, lz[id]);
    lz[id] = 0;
}
vector<int> fur;
void apply(int id, int l, int r, int u, int v, int ma){
    if(l > v || r < u || tree[id] < ma) return;
    if(l == r){
//        cout << two[l] << ' ';
        fur.push_back(two[l]);
//        if(ma != 0) one.add(a[two[l]]);
//        else one.erase(a[two[l]]);
        return;
    }
    down(id);
    int mid = r + l >> 1;
    apply(id << 1 | 1, mid + 1, r, u, v, ma);
    apply(id << 1, l, mid, u, v, ma);
    tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
}
#define apply(u, v, ma) apply(1, 1, n, u, v, ma)

void Update(int id, int l, int r, int u, int v, int val){
    if(l > v || r < u) return;
    if(l >= u && r <= v){
        return fix(id, val);
    }
    down(id);
    int mid = r + l >> 1;
    Update(id << 1, l, mid, u, v, val);
    Update(id << 1 | 1, mid + 1, r, u, v, val);
    tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
}
#define Update(u, v, ma) Update(1, 1, n, u, v, ma)

int fly(int u, int k){
    for(int j = 0; j <= lg; ++j){
        if(k >> j & 1){
            u = up[u][j];
        }
    }
    return u;
}
void update(int u, int a,int id, int val){
    if(dep[u][id] < dep[a][id] || dep[a][id] == -1) return;
//        cerr << dep[u][id] << "#" << dep[a][id] << ' ';
    int uchain = ind[u], achain = ind[a];
//    cout << u << ' ' << a << ' ';
    while(1){
//        cerr << u << ' ' << a << endl;
        if(achain == uchain){
            if(val == 1) apply(pos[a], pos[u], -1);
            else apply(pos[a], pos[u], 0);
            Update(pos[a], pos[u], val);
//            cout << u << ' ';
//            for(auto p : fur) cout << p << ' ';
//            cout << endl;
            reverse(fur.begin(), fur.end());
            for(auto p : fur){
                if(val != -1) one.add(p, dep[p][id], dep[a][id]);
                else one.erase(p, dep[p][id], dep[a][id]);
//                cout << p << ' ';
            }
            fur.clear();
            return;
        }
        if(val == 1) apply(pos[head[uchain]], pos[u], -1);
        else apply(pos[head[uchain]], pos[u], 0);
        Update(pos[head[uchain]], pos[u], val);
        u = up[head[uchain]][0];
        uchain = ind[u];
    }

//    cout << endl;
}
void dfs_3(int u, int p, int id){
//    R[a[u]] = last[a[u]];
//cout << u << ' ' << dep[u][id] << endl;
//    cout << F.get(1) << ' ';
//    if(u == 3) exit(0);
//cout << u << ' ';
    bool ok = 1;
    int idx = -1;
    for(auto v : adj[u]){
        if(v == p) continue;
        if(ok){
            int x = min(dep[u][id], mx[v]);
            int y = u;
//            cout << u << ' ' << mx[v] << endl;
//cout << v << ' ';
//            if(v == 1) cout << up[u][0] << ' ' << fly(u, x) << endl;
            update(up[u][0], fly(u, x), id, -1);
            ok = 0;
            one.add(u, dep[u][id], dep[u][id]);
        }
        else{
//            if()
            one.erase(u, dep[u][id], dep[u][id]);
            update(fly(u, mx[v] + 1), fly(u, idx), id, 1);
            one.add(u, dep[u][id], dep[u][id]);
//            if(v == 1) cout << F.get(2) << endl;

        }

//        if(v == 1) cout << F.get(0) << ' ';
        ans[v][id] =  F.get(max(dep[v][id] - h[v] - 1, -1));
//        if(v == 1) exit(0);
        idx = min(mx[v], dep[u][id]);
        dfs_3(v, u, id);
    }
    if(idx != -1){
        one.erase(u, dep[u][id], dep[u][id]);
        update(up[u][0], fly(u, idx), id, 1);


    }
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> m;
    for(int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 1; i <= n; ++i) cin >> a[i];
    int s, t, ma;
    ma = -1;
    dfs_1(1, -1);
    for(int i = 1; i <= n; ++i){
        if(ma < H[i]){
            ma = max(ma, H[i]);
            s = i;
        }
    }
    ma = -1;
    dep[0][0] = dep[0][1] = -1;
    dfs_1(s, -1);
    for(int i = 1; i <= n; ++i){
        if(ma < H[i]){
            ma = max(ma, H[i]);
            t = i;
        }
    }
//    swap(s, t);
//    cout << s << ' ' << t << endl;
    for(int i = 1; i <= m; ++i) one.c[i] = -1;
    dfs_4(s, -1, 0);
    dfs_2(s, -1);
    dfs_3(s, -1, 0);
//    debug(h, n);
    for(int i = 1; i <= m; ++i) one.c[i] = -1;

    for(int i = 1; i <= n; ++i){
        mx[i] = 0;
        for(int j = 0; j <= lg; ++j) up[i][j] = 0;
        head[i] = 0;
        h[i] = 0;
    }
    Time = 0;nchain = 1;
    build(1, 1, n);
    dfs_4(t, -1, 1);
    for(int i = 1; i <= n; ++i) h[i] = 0;

    dfs_2(t, -1);
    dfs_3(t, -1, 1);
    for(int i = 1; i <= n; ++i){
//        cout << dep[i][0] << ' ' << dep[i][1] << endl;
        if(dep[i][0] >= dep[i][1]) cout << ans[i][0];
        else cout << ans[i][1];
        cout << endl;
    }

}
/*


*/

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'void build(int, int, int)':
joi2019_ho_t5.cpp:130:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  130 |     int mid = r + l >> 1;
      |               ~~^~~
joi2019_ho_t5.cpp: In function 'void apply(int, int, int, int, int, int)':
joi2019_ho_t5.cpp:154:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  154 |     int mid = r + l >> 1;
      |               ~~^~~
joi2019_ho_t5.cpp: In function 'void Update(int, int, int, int, int, int)':
joi2019_ho_t5.cpp:167:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  167 |     int mid = r + l >> 1;
      |               ~~^~~
joi2019_ho_t5.cpp: In function 'void dfs_3(int, int, int)':
joi2019_ho_t5.cpp:226:17: warning: unused variable 'y' [-Wunused-variable]
  226 |             int y = u;
      |                 ^
joi2019_ho_t5.cpp: At global scope:
joi2019_ho_t5.cpp:256:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  256 | main(){
      | ^~~~
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:309:10: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
  309 |     dfs_3(t, -1, 1);
      |     ~~~~~^~~~~~~~~~
joi2019_ho_t5.cpp:293:10: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
  293 |     dfs_3(s, -1, 0);
      |     ~~~~~^~~~~~~~~~

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