Submission #1243209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243209		Sam_arvandi	Jail (JOI22_jail)	C++20	100 / 100	618 ms	151412 KiB

jail

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define FOR(i, j, n) for (int i = j; i<= n; i++)
#define ROF(i, n, j) for (int i = n; i>= j; i--)
#define pb push_back
#define mp make_pair
#define S second
#define F first
#define IOS ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)

/*
#pragma GCC optimization("Ofast, unroll-loops")
#pragma GCC target("avx2")
#pragma GCC target("bmi")
#pragma GCC target("bmi2")
#pragma GCC target("lzcnt")
*/

const int mn = 12e4 + 5, mlg = 22;
int root[mn], siz[mn], h[mn], f1[mn], f2[mn], Siz[mn], go[mn*16];
vector<int> a[mn], A[mn*16];
vector<pii> a2[mn];
bool mark[mn], MARK[mn*16];
int lift[mn][mlg],alaki1[mn], alaki2[mn], par[mn];
int beg1[mn], beg2[mn], g[mn];
pii qu[mn];
vector<int> topol;

struct Seg_tree
{
        struct Node
        {
                int lc = -1, rc = -1;
        }tmp;
        vector<Node> node;
        int n = 0;

        void init(int id, int L, int R, bool flag)
        {
                if (L+1 == R)
                {
                        if (flag)
                        {
                                if (alaki1[L] != 0)
                                {
                                        A[id].pb(alaki1[L]);
                                }
                        }
                        else
                        {
                                if (alaki2[L] != 0)
                                {
                                        A[alaki2[L]].pb(id);
                                }
                        }
                        return;
                }
                n++;
                node.pb(tmp);
                node[id].rc = n;
                if (flag) 
                {
                        A[id].pb(n);
                }
                else
                {
                        A[n].pb(id);
                }
                
                n++;
                node.pb(tmp);
                node[id].lc = n;
                if (flag) 
                {
                        A[id].pb(n);
                }
                else
                {
                        A[n].pb(id);
                }
                int mid = (L+R)/2;
                init(node[id].lc, L, mid, flag);
                init(node[id].rc, mid, R, flag);
                return;
        }

        void yal1(int id, int L, int R, int l, int r, int x)
        {
                if (L == l and R == r)
                {
                        A[x].pb(id);
                        return;
                }
                int mid = (L+R)/2;
                if (l >= mid) yal1(node[id].rc, mid, R, l, r, x);
                else if (r <= mid) yal1(node[id].lc, L, mid, l, r, x);
                else
                {
                        yal1(node[id].lc, L, mid, l, mid, x);
                        yal1(node[id].rc, mid, R, mid, r, x);
                }
        }

        void yal2(int id, int L, int R, int l, int r, int x)
        {
                if (L == l and R == r)
                {
                        A[id].pb(x);
                        return;
                }
                int mid = (L+R)/2;
                if (l >= mid) yal2(node[id].rc, mid, R, l, r, x);
                else if (r <= mid) yal2(node[id].lc, L, mid, l, r, x);
                else
                {
                        yal2(node[id].lc, L, mid, l, mid, x);
                        yal2(node[id].rc, mid, R, mid, r, x);
                }
        }
}seg;

void cle(int n)
{
        FOR(i, 1, n)
        {
                root[i] = siz[i] = h[i] = f1[i] = f2[i] = Siz[i] = alaki1[i] = alaki2[i] = par[i] = beg1[i] = beg2[i] = g[i] = 0;
                a[i].clear();
                a2[i].clear();
                mark[i] = 0;
                FOR(j, 0, 20) lift[i][j] = 0;
                qu[i] = mp(0, 0);
        }
        FOR(i, 1, n+seg.n)
        {
                go[i] = 0;
                MARK[i] = 0;
                A[i].clear();
        }
        seg.node.clear();
        topol.clear();
        seg.n = 0;
}
void dfs(int u)
{
        for(auto p: a2[u])
        {
                int v = p.S;
                if (v == a2[u][0].S)
                {
                        root[v] = root[u];
                }
                else root[v] = v;
                dfs(v);
        }
        return;
}

void dfs1(int u)
{
        mark[u] = 1;
        for(auto v: a[u])
        {
                if (mark[v])
                {
                        lift[u][0] = v;
                        par[u] = v;
                        continue;
                }
                h[v] = h[u]+1;
                dfs1(v);
                siz[u] += siz[v];
        }
        siz[u]++;
        for(auto v: a[u])
        {
                if (v == par[u]) continue;
                a2[u].pb(mp(siz[v], v));
        }
        return;
}



void initi(int n)
{
        FOR(i, 1, n)
        {
                if (a2[i].size() != 0) continue;
                int t = 0, u = i;
                while (root[u] != u)
                {
                        t++;
                        g[u] = t;
                        if (f1[u] > 0) alaki1[t] = f1[u];
                        if (f2[u] > 0) alaki2[t] = f2[u];
                        u = par[u];
                }
                t++;
                g[u] = t;
                if (f1[u] > 0) alaki1[t] = f1[u];
                if (f2[u] > 0) alaki2[t] = f2[u];
                Siz[root[i]] = t;
                seg.n++;
                u = seg.n;
                beg1[root[i]] = u;
                seg.node.pb(seg.tmp);
                seg.init(u, 1, t+1, 1);

                seg.n++;
                u = seg.n;
                beg2[root[i]] = u;
                seg.node.pb(seg.tmp);
                seg.init(u, 1, t+1, 0);
                FOR(j, 1, t)
                {
                        alaki1[j] = alaki2[j] = 0;
                }
        }
}

void yal(int u, int v, int x, bool flag)
{
        if (flag)
        {
                if (h[v] < h[root[u]])
                {
                        seg.yal1(beg1[root[u]], 1, Siz[root[u]]+1, g[u], Siz[root[u]]+1, x);
                        u = root[u];
                        u = par[u];
                        yal(u, v, x, flag);
                        return;
                }
                else
                {
                        seg.yal1(beg1[root[u]], 1, Siz[root[u]]+1, g[u], g[v]+1, x);
                        return;
                }
        }
        else
        {
                if (h[v] < h[root[u]])
                {
                        seg.yal2(beg2[root[u]], 1, Siz[root[u]]+1, g[u], Siz[root[u]]+1, x);
                        u = root[u];
                        u = par[u];
                        yal(u, v, x, flag);
                        return;
                }
                else
                {
                        seg.yal2(beg2[root[u]], 1, Siz[root[u]]+1, g[u], g[v]+1, x);
                        return;
                }
        }
}
void DFS(int u)
{
        MARK[u] = 1;
        for(auto v: A[u])
        {
                if (MARK[v]) continue;
                DFS(v);
        }
        topol.pb(u);
}


signed main()
{
        IOS;
        int T;
        cin >> T;
        while (T--)
        {
                seg.node.pb(seg.tmp);
                int u, v, n, m, ro;
                cin >> n;
                FOR(i, 1, n-1)
                {
                        cin >> u >> v;
                        a[u].pb(v);
                        a[v].pb(u);
                }
                if (n == 2)
                {
                        cin >> m;
                        FOR(i, 1, m) cin >> u >> v;
                        if (m <= 1) cout << "Yes" << "\n";
                        else cout << "No" << "\n";
                        cle(n);
                        continue;
                }
                FOR(i,1 , n)
                {
                        seg.node.pb(seg.tmp);
                        seg.n++;
                }
                cin >> m;
                FOR(i, 1, m)
                {
                        cin >> u >> v;
                        f1[u] = i;
                        f2[v] = i;
                        qu[i] = mp(u, v);
                }
                FOR(i,1 , n)
                {
                        if (a[i].size() != 1) ro = i;
                }
                h[ro] = 1;
                root[ro] = ro;
                dfs1(ro);
                FOR(j, 1, 20)
                {
                        FOR(i, 1, n)
                        {
                                lift[i][j] = lift[lift[i][j-1]][j-1];
                        }
                }
                FOR(i, 1,n)
                {
                        sort(a2[i].begin(), a2[i].end());
                        reverse(a2[i].begin(), a2[i].end());
                }
                dfs(ro);
                initi(n);
                FOR(i, 1, m)
                {
                        u = qu[i].F, v = qu[i].S;
                        if (f2[u] != 0)
                        {
                                yal(u, u, i, 0);
                        }
                        if (f1[v] != 0)
                        {
                                yal(v, v, i, 1);
                        }
                        if (h[u] < h[v]) swap(u, v);
                        if (u == v or par[u] == v) continue;
                        int u2 = u, v2 = v;
                        ROF(i, 20, 0)
                        {
                                if (h[lift[u][i]] > h[v]) u = lift[u][i];
                        }
                        if (par[u] == v)
                        {
                                yal(par[u2], u, i, 1);
                                yal(par[u2], u, i, 0);
                                continue;
                        }
                        if (h[u] != h[v]) u = par[u];
                        ROF(i, 20, 0)
                        {
                                if (lift[u][i] != lift[v][i])
                                {
                                        u = lift[u][i];
                                        v = lift[v][i];
                                }
                        }
                        int lca = par[u];
                        yal(par[u2], lca, i, 0);
                        yal(par[u2], lca, i, 1);
                        yal(par[v2], lca, i, 1);
                        yal(par[v2], lca, i, 0);

                }
                int N = seg.n;
                FOR(i, 1, N)
                {
                        if (!MARK[i]) DFS(i);
                }
                FOR(i, 0, N-1)
                {
                        go[topol[i]] = i;
                }
                bool flag = 0;
                FOR(i,1 , N)
                {
                        for(auto v: A[i])
                        {
                                if (go[i] <= go[v])
                                {
                                        flag = 1;
                                }
                        }
                }
                if (flag)
                {
                        cout << "No" << "\n";
                }
                else cout << "Yes" << "\n";
                cle(n);
        }
}

• 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