Submission #1261315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261315		M_W_13	Tourism (JOI23_tourism)	C++20	100 / 100	1002 ms	43512 KiB

tourism

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
const int MAXN = 1 << 18;
const int MAXK = 20;
int n, m, q;
vector<pair<int, int>> graf[MAXN];
bool pomczy[MAXN];
int skok[MAXN][MAXK];
int depth[MAXN];
int pot2[MAXK];
int gleb[MAXN];
int preorder[MAXN];
int postorder[MAXN];
int seg[2 * MAXN];
pair<int, int> gdzie[MAXN];
pair<int, int> policz[MAXN];
int odp[MAXN];
int ojc[MAXN];
int C[MAXN];
bool pierw = true;
int kt = 1;
int kt2 = 1;

struct pytaj {
    int l, r, nr, typ;
};

vector<pytaj> dodaj;

void upd(int v, int x) {
    v += MAXN;
    while (v > 0) {
        seg[v] += x;
        v /= 2;
    }
}

int query(int l, int r) {
    l += MAXN;
    r += MAXN;
    int ans = 0;
    while (l < r) {
        if ((l % 2) == 1) {
            ans += seg[l];
            l++;
        }
        if ((r % 2) == 0) {
            ans += seg[r];
            r--;
        }
        l /= 2;
        r /= 2;
    }
    if (l == r) {
        ans += seg[l];
    }
    return ans;
}

void dfs(int v, int last, int dl) {
    // cout << "last = " << last << " v = " << v << " dl = " << dl << '\n';
    policz[v] = gdzie[v];
    depth[v] = depth[last] + dl;
    if (pierw) {
        gleb[v] = gleb[last] + 1;
        skok[v][0] = last;
        for (int k = 1; k < MAXK; k++) {
            skok[v][k] = skok[skok[v][k - 1]][k - 1];
        }
        preorder[v] = kt;
        kt++;
    }
    for (auto syn: graf[v]) {
        if (syn.st == last) continue;
        dfs(syn.st, v, syn.nd);
        policz[v].st = max(policz[v].st, policz[syn.st].st);
        policz[v].nd = min(policz[v].nd, policz[syn.st].nd);
    }
    if (v != last) {
        dodaj.pb({policz[v].st, policz[v].nd, dl, 0});
    }
    // cout << "w = " << v << " policz = " << policz[v].st << " " << policz[v].nd << " dl = " << dl << '\n';
    if (pierw) {
        postorder[v] = kt2;
        kt2++;
    }
    if (v == last) {
        pierw = false;
        kt = 1;
        kt2 = 1;
    }
}

int lca(int a, int b) {
    if (gleb[a] > gleb[b]) {
        swap(a, b);
    }
    int k = MAXK - 1;
    while (gleb[b] > gleb[a]) {
        if ((gleb[b] - pot2[k]) >= gleb[a]) {
            b = skok[b][k];
        }
        k--;
    }
    if (a == b) {
        return a;
    }
    k = MAXK - 1;
    while (skok[a][0] != skok[b][0]) {
        if (skok[a][k] != skok[b][k]) {
            a = skok[a][k];
            b = skok[b][k];
        }
        k--;
    }
    return skok[a][0];
}

void znajdz(int l, int r, int sr) {
    for (int i = l; i < sr; i++) {
        gdzie[C[i]].st = i;
    }
    for (int i = r; i > sr; i--) {
        gdzie[C[i]].nd = i;
    }
}

void prepot2() {
    pot2[0] = 1;
    for (int k = 1; k < MAXK; k++) {
        pot2[k] = pot2[k - 1] * 2;
    }
}

bool por1(int a, int b) {
    return preorder[a] < preorder[b];
}

void stworznowe(vector<int> &vec) {
    sort(vec.begin(), vec.end(), por1);
    for (auto x: vec) {
        pomczy[x] = true;
    }
    int sz = vec.size();
    rep(i, sz - 1) {
        int v = lca(vec[i], vec[i + 1]);
        // cout << "lca = " << v << " a = " << vec[i] << " b = " << vec[i + 1] << endl;
        if (pomczy[v]) continue;
        pomczy[v] = true;
        vec.pb(v);
    }
    for (auto v: vec) {
        pomczy[v] = false;
    }
    sort(vec.begin(), vec.end(), por1);
    int last = vec[0];
    sz = vec.size();
    ojc[last] = last;
    for (int i = 1; i < sz; i++) {
        // cout << (int)vec.size() << endl;
        // cout << "PLS" << endl;
        // cout << "i = " << i << endl;
        // cout << "vec = " << vec[i] << endl;
        // cout << "XD" << endl;
        int v = vec[i];
        // cout << "last = " << last << " v = " << v << endl;
        while (postorder[v] > postorder[last]) {
            last = ojc[last];
        }
        // cout << "KONIEC" << endl;
        // cout << "tworzysz = " << " v = " << v << " last = " << last << " gl v = " << gleb[v] << " gl last = " << gleb[last] << endl;
        graf[v].pb({last, gleb[v] - gleb[last]});
        // cout << (int)vec.size() << endl;
        graf[last].pb({v, gleb[v] - gleb[last]});
        // cout << (int)vec.size() << endl;
        ojc[v] = last;
        // cout << (int)vec.size() << endl;
        last = v;
        // cout << (int)vec.size() << endl;
        // cout << (int)vec.size() << endl;
        // cout << "REL" << endl;
        // cout << (int)vec.size() << endl;
    }
}

vector<pytaj> pyt;

bool por2(pytaj a, pytaj b) {
    pair<int, int> a2 = {a.r, a.typ};
    pair<int, int> b2 = {b.r, b.typ};
    return (a2 < b2);
}

void rob(int l, int r) {
    dodaj.clear();
    // cout << "l = " << l << " r = " << r << endl;
    if (l == r) {
        for (auto p: pyt) {
            odp[p.nr] = 0;
        }
        return ;
    }
    int sr = (l + r)/2;
    vector<pytaj> pom1;
    vector<pytaj> pom2;
    vector<pytaj> ter;
    // cout << "CH1" << endl;
    for (auto p: pyt) {
        if (p.l <= sr && p.r >= sr) {
            ter.pb(p);
        }
        else if (p.r < sr) {
            pom1.pb(p);
        }
        else {
            pom2.pb(p);
        }
    }
    // cout << "CH2" << endl;
    pyt.clear();
    vector<int> vec;
    for (int i = l; i <= r; i++) {
        int v = C[i];
        // cout << "i = " << i << " v = " << v << endl;
        if (pomczy[v]) continue;
        pomczy[v] = true;
        vec.pb(v);
    }
    // cout << "CH3" << endl;
    stworznowe(vec);
    // cout << "CH4" << endl;
    for (auto v: vec) {
        gdzie[v] = {-1, m + 1};
        policz[v] = {-1, m + 1};
    }
    znajdz(l, r, sr);
    // for (auto v: vec) {
        // cout << "v = " << v << " l = " << gdzie[v].st << " r = " << gdzie[v].nd << '\n';
    // }
    // cout << "CH5" << endl;
    int w = C[sr];
    // cout << "w = " << w << endl;
    depth[w] = 0;
    // cout << "START" << endl;
    // for (auto v: vec) {
    //     cout << "v = " << v << " l = " << gdzie[v].st << " r = " << gdzie[v].nd << '\n';
    // }
    dfs(w, w, 0);
    // for (auto v: vec) {
    //     cout << "v = " << v << " l = " << policz[v].st << " r = " << policz[v].nd << '\n';
    // }
    // cout << "XD" << endl;
    for (auto p: dodaj) {
        ter.pb(p);
        // cout << "L = " << p.l << " R = " << p.r << " liczba = " << p.nr << endl;
    }
    // cout << "CH6" << endl;
    sort(ter.begin(), ter.end(), por2);
    for (auto p: ter) {
        if (p.typ == 0) {
            if (p.l >= 0) {
                upd(p.l, p.nr);   
            }
        }
    }
    // cout << "CH7" << endl;
    int pomoc = 0;
    for (auto p: ter) {
        if (p.typ == 0) {
            if (p.l >= 0) {
                upd(p.l, -p.nr);
            }
            pomoc += p.nr;
        }
        else {
            // cout << "PYYYYTAAAAAANIEEEE = " << p.l << " " << p.r << '\n';
            int ile = query(p.l, sr);
            odp[p.nr] = pomoc + ile;
        }
    }
    // cout << "CH8" << endl;
    ter.clear();
    for (auto v: vec) {
        graf[v].clear();
    }
    vec.clear();
    pyt.clear();
    for (auto p: pom1) {
        pyt.pb(p);
    }
    pom1.clear();
    rob(l, sr);
    pyt.clear();
    for (auto p: pom2) {
        pyt.pb(p);
    }
    rob(sr + 1, r);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    prepot2();
    cin >> n >> m >> q;
    rep(i, n - 1) {
        int a, b;
        cin >> a >> b;
        graf[a].pb({b, 1});
        graf[b].pb({a, 1});
    }
    dfs(1, 1, 0);
    for (int v = 1; v <= n; v++) {
        graf[v].clear();
    }
    rep(i, m) {
        cin >> C[i];
    }
    rep(i, q) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        pyt.pb({l, r, i, 1});
    }
    // for (auto p: pyt) {
    //     cout << p.l << " " << p.r << '\n';
    // }
    rob(0, m - 1);
    rep(i, q) {
        odp[i]++;
        cout << odp[i] << '\n';
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41