oj.uz

Submission #793765

# Submission time Handle Problem Language Result Execution time Memory
793765 2023-07-26T06:24:28 Z vjudge1 Tourism (JOI23_tourism) C++17
18 / 100
 367 ms 24452 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e5 + 10;
const int M = (1 << 18);
// segment Sum + update in pos
int segSum[2 * M];
void update(int pos, int val) {
    for(segSum[pos += M] += val; pos > 1; pos >>= 1) {
        segSum[pos >> 1] = segSum[pos] + segSum[(pos ^ 1)];
    }
}
int get(int ql, int qr) {
    int res = 0;
    for(ql += M, qr += M + 1; ql < qr; ql >>= 1, qr >>= 1) {
        if(ql & 1) res += segSum[ql++];
        if(qr & 1) res += segSum[--qr];
    }
    return res;
}



int n, m, q;

vector<int> g[N];
vector<pair<int, int>> e;
int sm[N];
int tin[N], tout[N], anc[N][17], depth[N], T;
void calc(int s, int p) {
    for(int to : g[s]) {
        if(to == p) continue;
        calc(to, s);
        sm[s] += sm[to];
    }
}

void precalc(int s, int p) {
    tin[s] = T++;
    anc[s][0] = p;
    for(int i = 1; i < 17; i++)
        anc[s][i] = anc[anc[s][i - 1]][i - 1];
    for(int to : g[s]) {
        if(to == p) continue;
        depth[to] = depth[s] + 1;
        precalc(to, s);
    }
    tout[s] = T++;
}
bool up(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v) {
    if(up(u, v)) return u;
    if(up(v, u)) return v;
    for(int i = 16; i >= 0; i--) {
        if(!up(anc[u][i], v)) u = anc[u][i];
    }
    return anc[u][0];
}
struct query {
    int l, r, i;
};
template<typename T> 
struct SprarseTable {
    int len;
    vector<vector<T>> st;
    void init(vector<T> &a) {
        len = (int)a.size();
        int mxpw = 32 - __builtin_clz(len);
        st.resize(mxpw);
        st[0] = a;
        for(int k = 1; k < mxpw; k++) {
            st[k].resize(len - (1 << k) + 1);
            for(int i = 0; i < (int)st[k].size(); i++) {
                st[k][i] = lca(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
            }
        }
    }
    T get(int l, int r) {
        int mxpw = 31 - __builtin_clz(r - l + 1);
        return lca(st[mxpw][l], st[mxpw][r - (1 << mxpw) + 1]);
    }
};

int curAns;
void add(int ver) {
    if(get(tin[ver], tout[ver]) == 0) curAns++;
    int u = ver;
    for(int i = 16; i >= 0; i--) {
        if(get(tin[ anc[u][i] ], tout[ anc[u][i] ]) == 0) 
            u = anc[u][i];
    }
    curAns += depth[ver] - depth[u];

    update(tin[ver], +1);
}
void del(int ver) {
    update(tin[ver], -1);
    int u = ver;
    for(int i = 16; i >= 0; i--) {
        if(get(tin[ anc[u][i] ], tout[ anc[u][i] ]) == 0) 
            u = anc[u][i];
    }
    curAns -= depth[ver] - depth[u];
    if(get(tin[ver], tout[ver]) == 0) curAns--;
}

vector<query> qr;
int ans[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        e.push_back({u, v});
    }
    vector<int> ver(m + 1);
    for(int i = 1; i <= m; i++) 
        cin >> ver[i];
    precalc(1, 1);
    for(int i = 0; i < q; i++) {
        query c;
        cin >> c.l >> c.r; c.i = i;
        qr.push_back(c);
    }
    SprarseTable<int> lc;
    lc.init(ver);

    // sort(qr.begin(), qr.end(), [](query a, query b) {return (a.l < b.l);});
    int curL = 1, curR = 0;
    for(query c : qr) {
        while(curR < c.r) {
            add(ver[++curR]);
        }
        while(curL < c.l) {
            del(ver[curL++]);
        }
        // cout << lc.get(c.l, c.r) << '\n';
        ans[c.i] = curAns - depth[lc.get(c.l, c.r)];
    }
    for(int i = 0; i < q; i++) 
        cout << ans[i] << '\n';
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 104 ms 13480 KB Output is correct
3 Correct 163 ms 16536 KB Output is correct
4 Correct 134 ms 16064 KB Output is correct
5 Correct 131 ms 22600 KB Output is correct
6 Correct 248 ms 22624 KB Output is correct
7 Correct 198 ms 22648 KB Output is correct
8 Correct 205 ms 22644 KB Output is correct
9 Correct 219 ms 22656 KB Output is correct
10 Correct 222 ms 22664 KB Output is correct
11 Correct 225 ms 22616 KB Output is correct
12 Correct 222 ms 22744 KB Output is correct
13 Correct 203 ms 22844 KB Output is correct
14 Correct 217 ms 23208 KB Output is correct
15 Correct 213 ms 24452 KB Output is correct
16 Correct 223 ms 22828 KB Output is correct
17 Correct 221 ms 22832 KB Output is correct
18 Correct 222 ms 22972 KB Output is correct
19 Correct 228 ms 22672 KB Output is correct
20 Correct 255 ms 22656 KB Output is correct
21 Correct 281 ms 22640 KB Output is correct
22 Correct 316 ms 22656 KB Output is correct
23 Correct 303 ms 22648 KB Output is correct
24 Correct 326 ms 22648 KB Output is correct
25 Correct 309 ms 22608 KB Output is correct
26 Correct 329 ms 22692 KB Output is correct
27 Correct 353 ms 22680 KB Output is correct
28 Correct 344 ms 22656 KB Output is correct
29 Correct 350 ms 22704 KB Output is correct
30 Correct 367 ms 22848 KB Output is correct
31 Correct 360 ms 22840 KB Output is correct
32 Correct 332 ms 22992 KB Output is correct
33 Correct 363 ms 23516 KB Output is correct
34 Correct 358 ms 24376 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Incorrect 150 ms 17864 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

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