Submission #1271554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271554		tvgk	Jail (JOI22_jail)	C++20	100 / 100	782 ms	279920 KiB

jail

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define ll long long
#define fi first
#define se second
#define ii pair<ll, ll>
const int mxN = 12e4 + 7;

int n, in[4200000], h[mxN], par[mxN][20], id[mxN][20][2], num;
vector<int> topo[4200000], w[mxN];

void Add(int u, int v)
{
    topo[u].push_back(v);
    in[v]++;
}

void DFS(int j)
{
    id[j][0][0] = ++num;
    id[j][0][1] = ++num;
    for (int i = 1; i <= 17; i++)
    {
        if ((1 << i) > h[j])
        {
            par[j][i] = 0;
            continue;
        }

        par[j][i] = par[par[j][i - 1]][i - 1];
        id[j][i][0] = ++num;
        id[j][i][1] = ++num;

        Add(id[j][i][0], id[j][i - 1][0]);
        Add(id[j][i][0], id[par[j][i - 1]][i - 1][0]);
        Add(id[j][i - 1][1], id[j][i][1]);
        Add(id[par[j][i - 1]][i - 1][1], id[j][i][1]);
    }

    for (int i : w[j])
    {
        if (h[i])
            continue;

        h[i] = h[j] + 1;
        par[i][0] = j;
        DFS(i);
    }
}

int LCA(int u, int v)
{
    if (h[u] < h[v])
        swap(u, v);

    for (int i = 17; i >= 0; i--)
    {
        if (h[par[u][i]] >= h[v])
            u = par[u][i];
    }

    if (u == v)
        return u;

    for (int i = 17; i >= 0; i--)
    {
        if (par[u][i] != par[v][i])
        {
            u = par[u][i];
            v = par[v][i];
        }
    }

    return par[u][0];
}

void Walk(int j, int u, int root, int tt)
{
    for (int i = 17; i >= 0; i--)
    {
        if (h[u] < (1 << i))
            continue;

        if (h[par[u][i]] + 1 < root)
            continue;

        if (!tt)
            Add(j, id[u][i][0]);
        else
            Add(id[u][i][1], j);
        u = par[u][i];
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
//    freopen(task".INP", "r", stdin);
//    freopen(task".OUT", "w", stdout);

    int tst;
    cin >> tst;
    while (tst--)
    {
        cin >> n;
        for (int i = 1; i < n; i++)
        {
            int u, v;
            cin >> u >> v;
            w[u].push_back(v);
            w[v].push_back(u);
        }
        h[1] = 1;
        DFS(1);

        int m;
        cin >> m;
        for (int i = 1; i <= m; i++)
        {
            int u, v;
            cin >> u >> v;

            num++;
            Add(id[u][0][0], num);
            Add(num, id[v][0][1]);

            int root = LCA(u, v);
            Walk(num, par[u][0], h[root], 0);
            Walk(num, v, h[root] + 1, 0);
            Walk(num, par[v][0], h[root], 1);
            Walk(num, u, h[root] + 1, 1);
        }

        queue<int> q;
        for (int i = 1; i <= num; i++)
        {
            if (!in[i])
                q.push(i);
        }

        int cnt = 0;
        while (q.size())
        {
            int j = q.front();
            q.pop();
            cnt++;

            for (int i : topo[j])
            {
                --in[i];
                if (!in[i])
                    q.push(i);
            }
        }

        if (cnt != num)
            cout << "No\n";
        else
            cout << "Yes\n";

        for (int i = 1; i <= n; i++)
        {
            w[i].clear();
            h[i] = 0;
        }

        for (int i = 1; i <= num; i++)
        {
            in[i] = 0;
            topo[i].clear();
        }
        num = 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