oj.uz

Submission #1094629

# Submission time Handle Problem Language Result Execution time Memory
1094629 2024-09-30T07:19:03 Z _8_8_ Tourism (JOI23_tourism) C++17
18 / 100
 197 ms 30040 KB 
#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
const int  N = 1e5 + 12, MOD = (int)1e9 + 7;

const int L = 19;
vector<int> g[N];
int n, m, q, c[N], tin[N], tout[N], timer, s[N], head[N], ver[N];
int up[N][19], dep[N];
void bb(int v, int pr = -1) {
    s[v] = 1;
    for(int i = 0; i < (int)g[v].size(); i++) {
        int to = g[v][i];
        if(to == pr) continue;
        bb(to, v);
        s[v] += s[to];
        if(s[to] > s[g[v][0]] || g[v][0] == pr) {
            swap(g[v][i], g[v][0]);
        }
    }
}
void hld(int v, int pr = -1) {
    tin[v] = ++timer;
    ver[timer] = v;
    for(int to:g[v]) {
        if(to == pr) continue;
        if(to == g[v][0]) {
            head[to] = head[v];
        } else {
            head[to] = to;
        }
        hld(to, v);
    }
    tout[v] = timer;
}
vector<pair<int,int>> qr[N];

void dfs(int v, int pr = 1) {
    up[v][0] = pr;
    for(int i = 1; i < L; ++i) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for(int to:g[v]) {
        if(to != pr) {
            dep[to] = dep[v] + 1;
            dfs(to, v);
        }
    }
}
bool is(int v, int u) {
    return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}
int lca(int v, int u) {
    if(is(v, u)) return v;
    if(is(u, v)) return u;
    for(int i = L - 1; i >= 0; i--) {
        if(!is(up[v][i], u)) {
            v = up[v][i];
        }
    }
    return up[v][0];
}
pair<int, int> t[N * 4];
void build(int v = 1, int tl = 1, int tr = m - 1) {
    if(tl == tr) {
        int x = lca(c[tl], c[tl + 1]);
        // cout << c[tl] << ' ' << c[tl + 1] << ' ' << x << '\n';
        t[v] = {dep[x], x};
    } else {
        int tm = (tl + tr) >> 1;
        build(v + v, tl, tm);
        build(v + v + 1, tm + 1, tr);
        t[v] = min(t[v + v], t[v + v + 1]);
    }
}
const int inf = 1e9;
pair<int, int> get(int l, int r, int v = 1, int tl = 1, int tr = m - 1) {
    if(l > r || tl > r || l > tr) return {inf, inf};
    if(tl >= l && tr <= r) return t[v];
    int tm = (tl + tr) >> 1;
    return min(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
}

int mn[N * 4], mod[N * 4], mx[N * 4];

void make(int v, int val) {
    mod[v] = mx[v] = mn[v] = val;
}
void push(int v) {
    if(mod[v]) {
        make(v + v, mod[v]);
        make(v + v + 1, mod[v]);
        mod[v] = 0;
    }
}
void upd(int l, int r, int val, int v = 1, int tl = 1, int tr = n) {
    if(l > r|| tl > r || l > tr) return;
    if(tl >= l && tr <= r) {
        make(v, val);
    } else {
        push(v);
        int tm = (tl + tr) >> 1;
        upd(l, r, val, v + v, tl, tm);
        upd(l, r, val, v + v + 1, tm + 1, tr);
        mx[v] = max(mx[v + v], mx[v + v + 1]);
        mn[v] = min(mn[v + v], mn[v + v + 1]);
    }
}
int find(int val, int v = 1, int tl = 1, int tr = n) { 
    if(mn[v] >= val) {
        return (tr - tl + 1);
    } 
    if(mx[v] < val) {
        return 0;
    }
    push(v);
    int tm = (tl + tr) >> 1;
    return find(val,v + v, tl, tm) + find(val, v + v + 1, tm + 1, tr);
}
void nv(int v, int i) {
    while(v != 1) {
        upd(tin[head[v]], tin[v], i);
        // cout << tin[head[v]] << ' ' << tin[v] << '\n';
        v = up[head[v]][0];
    }
}
int res[N];
void out(int v = 1, int tl = 1, int tr = n) {
    if(tl == tr) {
        // cout << mx[v] << " ";
    } else {
        push(v);
        int tm = (tl + tr) >> 1;
        out(v + v, tl, tm);
        out(v + v + 1, tm + 1, tr);
    }
}
void test() {
    cin >> n >> m >> q;
    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 <= m; i++) {
        cin >> c[i];
    }
    dep[1] = 1;
    bb(1);
    head[1] = 1;
    hld(1);

    dfs(1);
    build();
    for(int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        if(l == r) {
            res[i] = 1;
            continue;
        }
        qr[r].push_back({l, i});
    }
    for(int i = 1; i <= m; i++) {
        nv(c[i], i);
        if(i == 3) {
            // out();
            // cout << find(1) << '\n';
            // return;
        }
        for(auto [l, id]:qr[i]) {
            int x = get(l, i - 1).second;
            // cout << x << '\n';
            res[id] = find(l) - dep[x] + 1;
        }
    }

    for(int i = 1; i <= q; i++) {
        cout << res[i] << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    
    int t = 1; 
    // cin >> t;
    
    while(t--) 
        test();
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16988 KB Output is correct
2 Correct 2 ms 19036 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 2 ms 17244 KB Output is correct
5 Correct 3 ms 17072 KB Output is correct
6 Correct 2 ms 17244 KB Output is correct
7 Correct 2 ms 17244 KB Output is correct
8 Correct 2 ms 17244 KB Output is correct
9 Correct 3 ms 17244 KB Output is correct
10 Correct 2 ms 17244 KB Output is correct
11 Correct 3 ms 17244 KB Output is correct
12 Correct 3 ms 17244 KB Output is correct
13 Correct 2 ms 17244 KB Output is correct
14 Correct 3 ms 17244 KB Output is correct
15 Correct 2 ms 17248 KB Output is correct
16 Correct 2 ms 17244 KB Output is correct
17 Correct 2 ms 17244 KB Output is correct
18 Correct 3 ms 17240 KB Output is correct
19 Correct 3 ms 17052 KB Output is correct
20 Correct 2 ms 17244 KB Output is correct
21 Correct 2 ms 17244 KB Output is correct
22 Correct 3 ms 17244 KB Output is correct
23 Correct 3 ms 17240 KB Output is correct
24 Correct 2 ms 17216 KB Output is correct
25 Correct 3 ms 17244 KB Output is correct
26 Correct 2 ms 17256 KB Output is correct
27 Incorrect 2 ms 14952 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16988 KB Output is correct
2 Correct 2 ms 19036 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 2 ms 17244 KB Output is correct
5 Correct 3 ms 17072 KB Output is correct
6 Correct 2 ms 17244 KB Output is correct
7 Correct 2 ms 17244 KB Output is correct
8 Correct 2 ms 17244 KB Output is correct
9 Correct 3 ms 17244 KB Output is correct
10 Correct 2 ms 17244 KB Output is correct
11 Correct 3 ms 17244 KB Output is correct
12 Correct 3 ms 17244 KB Output is correct
13 Correct 2 ms 17244 KB Output is correct
14 Correct 3 ms 17244 KB Output is correct
15 Correct 2 ms 17248 KB Output is correct
16 Correct 2 ms 17244 KB Output is correct
17 Correct 2 ms 17244 KB Output is correct
18 Correct 3 ms 17240 KB Output is correct
19 Correct 3 ms 17052 KB Output is correct
20 Correct 2 ms 17244 KB Output is correct
21 Correct 2 ms 17244 KB Output is correct
22 Correct 3 ms 17244 KB Output is correct
23 Correct 3 ms 17240 KB Output is correct
24 Correct 2 ms 17216 KB Output is correct
25 Correct 3 ms 17244 KB Output is correct
26 Correct 2 ms 17256 KB Output is correct
27 Incorrect 2 ms 14952 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 19048 KB Output is correct
2 Incorrect 2 ms 15176 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17000 KB Output is correct
2 Correct 96 ms 24672 KB Output is correct
3 Correct 145 ms 25192 KB Output is correct
4 Correct 126 ms 25952 KB Output is correct
5 Correct 162 ms 26976 KB Output is correct
6 Correct 160 ms 27488 KB Output is correct
7 Correct 167 ms 26784 KB Output is correct
8 Correct 164 ms 27472 KB Output is correct
9 Correct 197 ms 26780 KB Output is correct
10 Correct 187 ms 27472 KB Output is correct
11 Correct 194 ms 26832 KB Output is correct
12 Correct 196 ms 26952 KB Output is correct
13 Correct 197 ms 27984 KB Output is correct
14 Correct 197 ms 28752 KB Output is correct
15 Correct 176 ms 29780 KB Output is correct
16 Correct 173 ms 27972 KB Output is correct
17 Correct 180 ms 28012 KB Output is correct
18 Correct 172 ms 28032 KB Output is correct
19 Correct 137 ms 27096 KB Output is correct
20 Correct 140 ms 27080 KB Output is correct
21 Correct 152 ms 27476 KB Output is correct
22 Correct 136 ms 26960 KB Output is correct
23 Correct 151 ms 26960 KB Output is correct
24 Correct 140 ms 27476 KB Output is correct
25 Correct 158 ms 27568 KB Output is correct
26 Correct 159 ms 27472 KB Output is correct
27 Correct 156 ms 27440 KB Output is correct
28 Correct 161 ms 27588 KB Output is correct
29 Correct 170 ms 26968 KB Output is correct
30 Correct 177 ms 27220 KB Output is correct
31 Correct 172 ms 27476 KB Output is correct
32 Correct 184 ms 28004 KB Output is correct
33 Correct 186 ms 30040 KB Output is correct
34 Correct 150 ms 29380 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17244 KB Output is correct
2 Incorrect 2 ms 14940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16988 KB Output is correct
2 Correct 2 ms 19036 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 2 ms 17244 KB Output is correct
5 Correct 3 ms 17072 KB Output is correct
6 Correct 2 ms 17244 KB Output is correct
7 Correct 2 ms 17244 KB Output is correct
8 Correct 2 ms 17244 KB Output is correct
9 Correct 3 ms 17244 KB Output is correct
10 Correct 2 ms 17244 KB Output is correct
11 Correct 3 ms 17244 KB Output is correct
12 Correct 3 ms 17244 KB Output is correct
13 Correct 2 ms 17244 KB Output is correct
14 Correct 3 ms 17244 KB Output is correct
15 Correct 2 ms 17248 KB Output is correct
16 Correct 2 ms 17244 KB Output is correct
17 Correct 2 ms 17244 KB Output is correct
18 Correct 3 ms 17240 KB Output is correct
19 Correct 3 ms 17052 KB Output is correct
20 Correct 2 ms 17244 KB Output is correct
21 Correct 2 ms 17244 KB Output is correct
22 Correct 3 ms 17244 KB Output is correct
23 Correct 3 ms 17240 KB Output is correct
24 Correct 2 ms 17216 KB Output is correct
25 Correct 3 ms 17244 KB Output is correct
26 Correct 2 ms 17256 KB Output is correct
27 Incorrect 2 ms 14952 KB Output isn't correct
28 Halted 0 ms 0 KB -