oj.uz

Submission #1115927

# Submission time Handle Problem Language Result Execution time Memory
1115927 2024-11-21T05:13:28 Z _8_8_ Unique Cities (JOI19_ho_t5) C++17
36 / 100
 838 ms 274432 KB 
#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;

const int  N = 2e5 + 12, MOD = (int)1e9 + 7;

int n, m, a[N];
bool vis[N], timer;
vector<int> g[N];
vector<vector<int>> dist;
bool zap;
int f(int d) {
    vector<int> D(n + 1, 0);
    timer = 1;
    for(int i = 1; i <= n; i++) {
        vis[i] = 0;
    }
    vis[d] = timer;
    int lst = d;
    queue<int> q;
    q.push(d);
    while(!q.empty()) {
        int v = q.front();
        lst = v;
        q.pop();
        for(int to : g[v]) {
            if(vis[to] != timer) {
                D[to] = D[v] + 1;
                q.push(to);
                vis[to] = timer;
            }
        }
    }
    dist.push_back(D);
    return lst;
}
int dep[N], mxd[N], res[N], d, d1, o, cr;
void dfs(int v, int pr = -1) {
    mxd[v] = dep[v];
    for(int to:g[v]) if(to != pr) {
        dep[to] = dep[v] + 1;
        dfs(to, v);
        mxd[v] = max(mxd[v], mxd[to]);
    }
    for(int i = 0; i < (int)g[v].size(); i++) {
        if(g[v][i] == pr) {
            swap(g[v][(int)g[v].size() - 1], g[v][i]);
            break;
        }
    }
    for(int i = 0; i < (int)g[v].size() - 1; i++) {
        if(mxd[g[v][i]] == mxd[v]) {
            swap(g[v][0], g[v][i]);
        }
    }
    // for(int i = 0; i < (int))
}
int b = 17, it = 0, cur = 0, ver[N];
int up[N][18];
struct node{
    node *l = 0, *r = 0;
    int sum = 0;
    node(){};
    node(int v) {
        sum = v;
    }
    node (node *L, node *R) {
        l = L;
        r = R;
        sum = l->sum + r->sum;
    }
};
using pnode = node *;
pnode tr[N];    
pnode build(int tl = 1, int tr = m) {
    if(tl == tr) {
        return new node();
    }
    int tm = (tl + tr) >> 1;
    return new node(build(tl, tm), build(tm + 1, tr));
}
pnode upd(int pos, pnode v, int tl = 1, int tr = m) {
    if(tl == tr) {
        return new node(1);
    }
    int tm = (tl + tr) >> 1;
    if(pos <= tm) 
        return new node(upd(pos, v->l, tl, tm), v->r);
    return new node(v->l, upd(pos, v->r, tm + 1, tr));
}
int rt;
void go(int v) {
    if(dist[cr][v] > dist[o][v] || (dist[cr][v] == dist[o][v] && zap)) {
        int f = cur, val = -mxd[v] + dep[v] * 2;
        set<int> r;
        if(dep[ver[f]] >= val) {
            for(int i = b - 1; i >= 0; i--) {
                int nv = ver[up[f][i]];
                if(dep[nv] >= val) {
                    f = up[f][i];
                }
            }
            f = up[f][0];
        }
        res[v] += tr[f]->sum;
    }
    int sz = (int)g[v].size() - (rt != v), mx1 = dep[v];
    if(!sz) return;
    for(int i = 1; i < sz; i++) {
        mx1 = max(mx1, mxd[g[v][i]]);
    }
    int bf = cur;
    for(int i = 0; i < sz; i++) {
        int to = g[v][i];
        int mx = dep[v];
        if(i) mx = mxd[g[v][0]];
        if(i < sz - 1) mx = max(mx, mx1);
        mx -= dep[v];
        if(i == 1) {
            cur = up[cur][0];
        }
        if(i <= 1 && dep[v] - dep[ver[cur]] <= mx) {
            for(int i = b - 1; i >= 0; i--) {
                int nv = up[cur][i];
                if(dep[v] - dep[ver[nv]] <= mx) {
                    cur = nv;
                }
            }
            cur = up[cur][0];
        }
        if(i <= 1) {
            it++;
            ver[it] = v;
            up[it][0] = cur;
            tr[it] = upd(a[v], tr[cur]);
            for(int i = 1; i < b; i++) {
                up[it][i] = up[up[it][i - 1]][i - 1];
            }
            cur = it;
        }
        go(to);
    }
    cur = bf;
}
void solve(int root) {
    it = cur = 0;
    ver[0] = 0;
    dep[0] = -(int)1e9;
    tr[0] = build();
    rt = root;
    dep[root] = 1;
    dfs(root);

    go(root);

}
void test() {
    cin >> n >> m;
    for(int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    d = f(1), d1 = f(d);
    f(d1);
    o = 2;cr = 1;
    solve(d);
    zap = 1;
    o = 1;cr = 2;
    solve(d1);
    for(int i = 1; i <= n; i++) {
        cout << res[i] << '\n';
    }

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

    int t = 1; 
    // cin >> t;

    while(t--) 
        test();
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11344 KB Output is correct
2 Correct 5 ms 12624 KB Output is correct
3 Correct 4 ms 12368 KB Output is correct
4 Correct 5 ms 12624 KB Output is correct
5 Correct 5 ms 11856 KB Output is correct
6 Correct 5 ms 11996 KB Output is correct
7 Correct 5 ms 11872 KB Output is correct
8 Correct 4 ms 11856 KB Output is correct
9 Correct 5 ms 11856 KB Output is correct
10 Correct 4 ms 11760 KB Output is correct
11 Correct 4 ms 11856 KB Output is correct
12 Correct 4 ms 11600 KB Output is correct
13 Correct 5 ms 12112 KB Output is correct
14 Correct 5 ms 11748 KB Output is correct
15 Correct 5 ms 11856 KB Output is correct
16 Correct 4 ms 11512 KB Output is correct
17 Correct 4 ms 12028 KB Output is correct
18 Correct 4 ms 11856 KB Output is correct
19 Correct 6 ms 12624 KB Output is correct
20 Correct 9 ms 13392 KB Output is correct
21 Correct 7 ms 13136 KB Output is correct
22 Correct 5 ms 12368 KB Output is correct
23 Correct 6 ms 12880 KB Output is correct
24 Correct 6 ms 12624 KB Output is correct
25 Correct 6 ms 12792 KB Output is correct
26 Correct 3 ms 11616 KB Output is correct
27 Correct 7 ms 13392 KB Output is correct
28 Correct 5 ms 12624 KB Output is correct
29 Correct 6 ms 12880 KB Output is correct
30 Correct 3 ms 11600 KB Output is correct
31 Correct 5 ms 12368 KB Output is correct
32 Correct 8 ms 12880 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 31876 KB Output is correct
2 Correct 166 ms 43396 KB Output is correct
3 Correct 29 ms 18076 KB Output is correct
4 Correct 274 ms 44864 KB Output is correct
5 Correct 436 ms 65080 KB Output is correct
6 Correct 416 ms 55352 KB Output is correct
7 Correct 192 ms 41140 KB Output is correct
8 Correct 230 ms 46648 KB Output is correct
9 Correct 213 ms 45852 KB Output is correct
10 Correct 196 ms 45628 KB Output is correct
11 Correct 82 ms 25724 KB Output is correct
12 Correct 324 ms 57404 KB Output is correct
13 Correct 246 ms 50168 KB Output is correct
14 Correct 235 ms 50100 KB Output is correct
15 Correct 73 ms 23724 KB Output is correct
16 Correct 250 ms 52796 KB Output is correct
17 Correct 223 ms 50612 KB Output is correct

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 206492 KB Output is correct
2 Runtime error 838 ms 274432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11344 KB Output is correct
2 Correct 5 ms 12624 KB Output is correct
3 Correct 4 ms 12368 KB Output is correct
4 Correct 5 ms 12624 KB Output is correct
5 Correct 5 ms 11856 KB Output is correct
6 Correct 5 ms 11996 KB Output is correct
7 Correct 5 ms 11872 KB Output is correct
8 Correct 4 ms 11856 KB Output is correct
9 Correct 5 ms 11856 KB Output is correct
10 Correct 4 ms 11760 KB Output is correct
11 Correct 4 ms 11856 KB Output is correct
12 Correct 4 ms 11600 KB Output is correct
13 Correct 5 ms 12112 KB Output is correct
14 Correct 5 ms 11748 KB Output is correct
15 Correct 5 ms 11856 KB Output is correct
16 Correct 4 ms 11512 KB Output is correct
17 Correct 4 ms 12028 KB Output is correct
18 Correct 4 ms 11856 KB Output is correct
19 Correct 6 ms 12624 KB Output is correct
20 Correct 9 ms 13392 KB Output is correct
21 Correct 7 ms 13136 KB Output is correct
22 Correct 5 ms 12368 KB Output is correct
23 Correct 6 ms 12880 KB Output is correct
24 Correct 6 ms 12624 KB Output is correct
25 Correct 6 ms 12792 KB Output is correct
26 Correct 3 ms 11616 KB Output is correct
27 Correct 7 ms 13392 KB Output is correct
28 Correct 5 ms 12624 KB Output is correct
29 Correct 6 ms 12880 KB Output is correct
30 Correct 3 ms 11600 KB Output is correct
31 Correct 5 ms 12368 KB Output is correct
32 Correct 8 ms 12880 KB Output is correct
33 Correct 114 ms 31876 KB Output is correct
34 Correct 166 ms 43396 KB Output is correct
35 Correct 29 ms 18076 KB Output is correct
36 Correct 274 ms 44864 KB Output is correct
37 Correct 436 ms 65080 KB Output is correct
38 Correct 416 ms 55352 KB Output is correct
39 Correct 192 ms 41140 KB Output is correct
40 Correct 230 ms 46648 KB Output is correct
41 Correct 213 ms 45852 KB Output is correct
42 Correct 196 ms 45628 KB Output is correct
43 Correct 82 ms 25724 KB Output is correct
44 Correct 324 ms 57404 KB Output is correct
45 Correct 246 ms 50168 KB Output is correct
46 Correct 235 ms 50100 KB Output is correct
47 Correct 73 ms 23724 KB Output is correct
48 Correct 250 ms 52796 KB Output is correct
49 Correct 223 ms 50612 KB Output is correct
50 Correct 435 ms 206492 KB Output is correct
51 Runtime error 838 ms 274432 KB Execution killed with signal 9
52 Halted 0 ms 0 KB -