Submission #1264598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264598		M_W_13	Jail (JOI22_jail)	C++20	100 / 100	806 ms	69080 KiB

jail

#include <bits/stdc++.h>

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
#define pb push_back
#define st first
#define nd second
const int MAXN = 1 << 18;
const int MAXK = 20;
vector<int> graf[MAXN];
vector<pair<int, int>> przedzialy;
int kt = 0;
pair<int, int> seg[2 * MAXN];
int suma[2 * MAXN];
vector<int> bazy[2 * MAXN];
int konczy[MAXN];
int kop[MAXN];
int skok[MAXN][MAXK];
bool czy[MAXN];
int ilena[MAXN];
int ilekon[MAXN];
int ojc[MAXN];
int depth[MAXN];
int odejm[MAXN];
int ile_pod[MAXN];
int preorder[MAXN];
int jaki[MAXN];
int jakipre[MAXN];
const int INF = 1e9;
int N = 1;
int kt2 = 1;
pair<int, int> pyt[MAXN];
queue<int> jakie;

void kopnij(int v) {
    kop[2 * v] += kop[v];
    seg[2 * v].st += kop[v];
    kop[2 * v + 1] += kop[v];
    seg[2 * v + 1].st += kop[v];
    kop[v] = 0;
}

void upd(int v, int l, int r, int p, int k, int x) {
    // cout << "v = " << v << " p = " << p << " k = " << k << " x = " << x << endl;
    // cout << "seg = " << seg[v].st << " val = " << seg[v].nd << '\n';
    if ((p <= l && r <= k)) {
        // cout << "DOOOOOOOOOOOOOODAAAAAAAAAJ = " << v << '\n';
        seg[v].st += x;
        kop[v] += x;
    }
    else if (r < p || l > k) {

    }
    else {
        kopnij(v);
        int sr = (l + r)/2;
        upd(2 * v, l, sr, p, k, x);
        upd(2 * v + 1, sr + 1, r, p, k, x);
        seg[v] = min(seg[2 * v], seg[2 * v + 1]);
        // cout << "v = " << v << " jakie = " << seg[2 * v].st << " jakie2 = " << seg[2 * v + 1].st << " j = " << seg[2 * v + 1].nd <<'\n';
    }
}

void anal() {
    // cout << "ANNNNNNNNNNNNNNNNNNNNAAAAAAAAAALLLLLLLLLLLLLLLLLL" << endl;
    while (seg[1].st == 0) {
        int v = seg[1].nd;
        // cout << "VAL = " << seg[1].st << '\n';
        v = jakipre[v];
        int i = konczy[v];
        // cout << "ZEEROOOOOOOOOOOOOOOoo v = " << v << " i = " << i << endl;
        if (i > 0) {
            ilekon[i] = 0;
            // cout << "ILENAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA = " << ilena[i] << '\n';
            if (ilena[i] == 0 && ilekon[i] == 0) {
                // cout << "PUSSSSSSSSSSSHHHHHHHHHHHHHHHHHHHHHANAL = " << i << '\n';
                ilekon[i] = INF;
                jakie.push(i);
            }
            konczy[v] = 0;
        }
        upd(1, 0, N - 1, preorder[v], preorder[v], INF);
    }
    // cout << "SEGGGGGGG = " << seg[1].st << " GDZIEEE = " << seg[1].nd << '\n';
}

void podziel(int l, int r, int i) {
    l += N;
    r += N;
    while (l < r) {
        if ((l % 2) == 1) {
            bazy[l].pb(i);
            l++;
        }
        if (r % 2 == 0) {
            bazy[r].pb(i);
            r--;
        }
        l /= 2;
        r /= 2;
    }
    if (l == r) {
        bazy[l].pb(i);
    }
}

void upd2(int v, int x) {
    v += N;
    while (v > 0) {
        suma[v] += x;
        if (x > 0) {
            odejm[v] += x;
        }
        if (suma[v] == 0) {
            // cout << "TUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK = " << v << endl;
            for (auto i: bazy[v]) {
                // cout << "i = " << i << '\n';
                ilena[i] -= odejm[v];
                if (ilena[i] == 0 && ilekon[i] == 0) {
                    // cout << "PUSSSSSSSSSSSHHHHHHHHHHHHHHHHHHHHHBAAAAAAAAAAAAAAAZYYYYYYYYYYYY = " << i << '\n';
                    jakie.push(i);
                }
            }
        }
        v /= 2;
    }
}

void dfs(int v, int last) {
    ile_pod[v] = 1;
    depth[v] = depth[last] + 1;
    ojc[v] = last;
    skok[v][0] = last;
    for (int k = 1; k < MAXK; k++) {
        skok[v][k] = skok[skok[v][k - 1]][k - 1];
    }
    for (auto syn: graf[v]) {
        if (syn == last) continue;
        dfs(syn, v);
        ile_pod[v] += ile_pod[syn];
    }
}

void dfs2(int v, int last, int nr, bool c) {
    // cout << "v = " << v << endl;
    preorder[v] = kt2;
    jakipre[kt2] = v;
    kt2++;
    if (c) {
        przedzialy[nr].nd = v;
    }
    else {
        nr = kt;
        przedzialy.pb({v, v});
        kt++;
    }
    jaki[v] = nr;
    pair<int, int> maks = {-1, -1};
    for (auto syn: graf[v]) {
        if (syn == last) continue;
        maks = max(maks, {ile_pod[syn], syn});
    }
    if (maks.nd != -1) {
        dfs2(maks.nd, v, nr, true);
        for (auto syn: graf[v]) {
            if (syn == last || syn == maks.nd) continue;
            dfs2(syn, v, -1, false);
        }
    }
}

int lca(int a, int b) {
    if (depth[a] > depth[b]) {
        swap(a, b);
    }
    int k = MAXK - 1;
    // cout << "XD" << endl;
    while (depth[a] != depth[b]) {
        // cout << "a = " << a << " b = " << b << " k = " << k << endl;
        if ((depth[b] - (1 << k)) >= depth[a]) {
            b = skok[b][k];
        }
        k--;
    }
    // cout << "PLS" << endl;
    if (a == b) return a;
    // cout << "BRUH" << endl;
    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 rob(int v, int oj, int x) {
    bool c = true;
    while (v != oj) {
        // cout << "v = " << v << endl;
        int nr = jaki[v];
        int w = przedzialy[nr].st;
        if (depth[oj] >= depth[w]) {
            w = oj;
            c = false;
        }
        upd(1, 0, N - 1, preorder[w], preorder[v], x);
        // cout << "UPDDDDDDDDDDDDDDDDDDDDDDDDDD w = " << w << " v = " << v << " x = " << x << endl;
        if (w != oj) {
            v = ojc[w];
        }
        else {
            break;
        }
    }
    if (c) {
        // cout << "UPDDDDDDDDDDDDDDDDDDDDD = oj = " << oj << " x = " << x <<  endl;
        upd(1, 0, N - 1, preorder[oj], preorder[oj], x);
    }
}

void rob2(int v, int oj, int i) {
    bool c = true;
    while (v != oj) {
        int nr = jaki[v];
        int w = przedzialy[nr].st;
        if (depth[oj] >= depth[w]) {
            w = oj;
            c = false;
        }
        podziel(preorder[w], preorder[v], i);
        if (w != oj) {
            v = ojc[w];
        }
        else { 
            break;
        }
    }
    if (c) {
        podziel(preorder[oj], preorder[oj], i);
    }
}

void usun(int i) {
    int a = pyt[i].st;
    int b = pyt[i].nd;
    upd2(preorder[a], -1);
    int oj = lca(a, b);
    // cout << "UPDDDDDDDDDDDDDDDDDDDDD2222 = oj = " << oj << " x = " << 1 <<  endl;
    upd(1, 0, N - 1, preorder[oj], preorder[oj], 1);
    if (b != oj) {
        b = ojc[b];
        rob(b, oj, -1);
    }
    rob(a, oj, -1);
    anal();
}

void dod(int i) {
    int a = pyt[i].st;
    int b = pyt[i].nd;
    // cout << "a = " << a << endl;
    upd2(preorder[a], 1);
    // cout << "b = " << b << endl;
    int oj = lca(a, b);
    // cout << "UPDDDDDDDDDDDDDDDDDDDDD3333333 = oj = " << oj << " x = " << -1 <<  endl;
    upd(1, 0, N - 1, preorder[oj], preorder[oj], -1);
    // cout << "G" << endl;
    if (b != oj) {
        b = ojc[b];
        // cout << "b = " << b << " ojc = " << oj << endl;
        rob(b, oj, 1);
    }
    // cout << "SPK" << endl;
    rob(a, oj, 1);
}

int szuk(int a, int oj) {
    int k = MAXK - 1;
    while (skok[a][0] != oj) {
        if ((depth[a] - (1 << k)) > depth[oj]) {
            a = skok[a][k];
        }
        k--;
    }
    return a;
}

void dziel(int i) {
    int a = pyt[i].st;
    int b = pyt[i].nd;
    // cout << "a = " << a << " b = " << b << endl;
    int oj = lca(a, b);
    // cout << "oj = " << oj << endl << '\n';
    // cout << "a = " << a << " b = " << b << " oj = " << oj << endl;
    if (oj != a) {
        a = ojc[a];
        rob2(a, oj, i);
    }
    // cout << "G" << endl;
    if (oj != b) {
        rob2(b, szuk(b, oj), i);
    }
    // cout << "KONIEC" << endl;
}

void solve() {
    int n;
    cin >> n;
    N = 1;
    kt2 = 1;
    kt = 0;
    przedzialy.clear();
    while (N <= n) N *= 2;
    // cout << "N = " << N << '\n';
    rep(i, N) {
        seg[i + N] = {0, i};
        jakipre[i] = i;
        preorder[i] = i;
    }
    for (int i = N - 1; i >= 1; i--) {
        seg[i] = min(seg[2 * i], seg[2 * i + 1]);
    }
    rep(i, n - 1) {
        int a, b;
        cin >> a >> b;
        graf[a].pb(b);
        graf[b].pb(a);
    }
    depth[1] = 0;
    dfs(1, 1);
    dfs2(1, 1, 0, false);
    // cout << "XD" << endl;
    // rep(i, n) {
    //     cout << "v = " << i + 1 << " jaki = " << jaki[i + 1] << " przedzial = " << " l = " << przedzialy[jaki[i + 1]].st << " r = " << przedzialy[jaki[i + 1]].nd << '\n';
    // }
    int m;
    cin >> m;
    rep(i, m) {
        ilena[i + 1] = 0;
        ilekon[i + 1] = 0;
    }
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        pyt[i + 1] = {a, b};
        // cout << "i = " << i << endl;
        dziel(i + 1);
        konczy[b] = i + 1;
        ilekon[i + 1] = INF;
        czy[a] = true;
    }
    // cout << "SKULL" << endl;
    rep(i, m) {
        // cout << "i = " << i << endl;
        dod(i + 1);
    }
    rep(i, 2 * N) {
        for (auto j: bazy[i]) {
            ilena[j] += odejm[i];
        }
    }
    // cout << "FR" << endl;
    anal();
    // cout << "PLS" << endl;
    int s = 0;
    while (!jakie.empty()) {
        int i = jakie.front();
        jakie.pop();
        // cout << "PEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEETLAAAAAAA i = " << i << '\n';
        s++;
        usun(i);
    }
    rep(i, 2 * N) {
        czy[i] = false;
        graf[i].clear();
        konczy[i] = 0;
        odejm[i] = 0;
        depth[i] = 0;
        ile_pod[i] = 0;
        seg[i] = {0, 0};
        bazy[i].clear();
        suma[i] = 0;
        ilena[i] = 0;
        ilekon[i] = 0;
        ojc[i] = 0;
        preorder[i] = 0;
        jaki[i] = 0;
        kop[i] = 0;
    }
    if (s == m) {
        cout << "Yes" << '\n';
        return ;
    }
    cout << "No" << '\n';
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
	cin >> t;
	while(t--) {
		solve();
	}
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23