제출 #1271545

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271545		tvgk	Jail (JOI22_jail)	C++20	0 / 100	261 ms	215224 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[3000007], h[mxN], par[mxN][25], id[mxN][25][2], num;
vector<int> topo[3000007], 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 <= __lg(h[j]); i++)
    {
        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 = 20; i >= 0; i--)
    {
        if (h[par[u][i]] >= h[v])
            u = par[u][i];
    }

    if (u == v)
        return u;

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

        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);

            //cout << num << " " << root << '\n';
        }

//        for (int i = 1; i <= num; i++)
//        {
//            cout << i << " : ";
//            for (int j : topo[i])
//                cout << j << " ";
//            cout << '\n';
//        }

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

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