oj.uz

Submission #1016001

# Submission time Handle Problem Language Result Execution time Memory
1016001 2024-07-07T08:56:12 Z phong Unique Cities (JOI19_ho_t5) C++17
4 / 100
 2000 ms 76816 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 6 ms 10072 KB Output is correct
3 Correct 4 ms 10076 KB Output is correct
4 Correct 5 ms 10332 KB Output is correct
5 Correct 6 ms 10328 KB Output is correct
6 Correct 5 ms 10332 KB Output is correct
7 Correct 6 ms 10388 KB Output is correct
8 Correct 6 ms 10328 KB Output is correct
9 Correct 7 ms 10332 KB Output is correct
10 Correct 6 ms 10332 KB Output is correct
11 Correct 7 ms 10332 KB Output is correct
12 Correct 6 ms 10332 KB Output is correct
13 Correct 8 ms 10332 KB Output is correct
14 Correct 8 ms 10332 KB Output is correct
15 Correct 9 ms 10584 KB Output is correct
16 Correct 5 ms 10332 KB Output is correct
17 Correct 6 ms 10468 KB Output is correct
18 Correct 6 ms 10332 KB Output is correct
19 Correct 7 ms 10332 KB Output is correct
20 Correct 6 ms 10588 KB Output is correct
21 Correct 6 ms 10392 KB Output is correct
22 Correct 6 ms 10328 KB Output is correct
23 Correct 7 ms 10328 KB Output is correct
24 Correct 6 ms 10332 KB Output is correct
25 Correct 6 ms 10196 KB Output is correct
26 Correct 6 ms 10332 KB Output is correct
27 Correct 13 ms 10420 KB Output is correct
28 Correct 8 ms 10328 KB Output is correct
29 Correct 8 ms 10332 KB Output is correct
30 Correct 8 ms 10332 KB Output is correct
31 Correct 6 ms 10328 KB Output is correct
32 Correct 6 ms 10380 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 31828 KB Output is correct
2 Correct 185 ms 46092 KB Output is correct
3 Correct 41 ms 17116 KB Output is correct
4 Correct 493 ms 48764 KB Output is correct
5 Correct 519 ms 73556 KB Output is correct
6 Correct 443 ms 61436 KB Output is correct
7 Correct 403 ms 48592 KB Output is correct
8 Correct 652 ms 51284 KB Output is correct
9 Correct 546 ms 50264 KB Output is correct
10 Correct 577 ms 50172 KB Output is correct
11 Correct 205 ms 49352 KB Output is correct
12 Execution timed out 2085 ms 56196 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 42596 KB Output is correct
2 Correct 407 ms 74116 KB Output is correct
3 Correct 54 ms 18256 KB Output is correct
4 Correct 506 ms 50268 KB Output is correct
5 Correct 428 ms 76816 KB Output is correct
6 Correct 464 ms 63692 KB Output is correct
7 Correct 452 ms 50260 KB Output is correct
8 Execution timed out 2047 ms 54724 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 6 ms 10072 KB Output is correct
3 Correct 4 ms 10076 KB Output is correct
4 Correct 5 ms 10332 KB Output is correct
5 Correct 6 ms 10328 KB Output is correct
6 Correct 5 ms 10332 KB Output is correct
7 Correct 6 ms 10388 KB Output is correct
8 Correct 6 ms 10328 KB Output is correct
9 Correct 7 ms 10332 KB Output is correct
10 Correct 6 ms 10332 KB Output is correct
11 Correct 7 ms 10332 KB Output is correct
12 Correct 6 ms 10332 KB Output is correct
13 Correct 8 ms 10332 KB Output is correct
14 Correct 8 ms 10332 KB Output is correct
15 Correct 9 ms 10584 KB Output is correct
16 Correct 5 ms 10332 KB Output is correct
17 Correct 6 ms 10468 KB Output is correct
18 Correct 6 ms 10332 KB Output is correct
19 Correct 7 ms 10332 KB Output is correct
20 Correct 6 ms 10588 KB Output is correct
21 Correct 6 ms 10392 KB Output is correct
22 Correct 6 ms 10328 KB Output is correct
23 Correct 7 ms 10328 KB Output is correct
24 Correct 6 ms 10332 KB Output is correct
25 Correct 6 ms 10196 KB Output is correct
26 Correct 6 ms 10332 KB Output is correct
27 Correct 13 ms 10420 KB Output is correct
28 Correct 8 ms 10328 KB Output is correct
29 Correct 8 ms 10332 KB Output is correct
30 Correct 8 ms 10332 KB Output is correct
31 Correct 6 ms 10328 KB Output is correct
32 Correct 6 ms 10380 KB Output is correct
33 Correct 223 ms 31828 KB Output is correct
34 Correct 185 ms 46092 KB Output is correct
35 Correct 41 ms 17116 KB Output is correct
36 Correct 493 ms 48764 KB Output is correct
37 Correct 519 ms 73556 KB Output is correct
38 Correct 443 ms 61436 KB Output is correct
39 Correct 403 ms 48592 KB Output is correct
40 Correct 652 ms 51284 KB Output is correct
41 Correct 546 ms 50264 KB Output is correct
42 Correct 577 ms 50172 KB Output is correct
43 Correct 205 ms 49352 KB Output is correct
44 Execution timed out 2085 ms 56196 KB Time limit exceeded
45 Halted 0 ms 0 KB -