Submission #1168429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168429		cpismylifeOwO	Jail (JOI22_jail)	C++20	100 / 100	895 ms	259696 KiB

jail

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 2e6 + 5;

int n, m;
vector<int> graph[MaxN];
pair<int, int> arr[MaxN];

void Inp()
{
    cin >> n;
    for (int x = 1; x <= n; x++)
    {
        graph[x].clear();
    }
    for (int x = 1; x < n; x++)
    {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    cin >> m;
    for (int x = 1; x <= m; x++)
    {
        cin >> arr[x].first >> arr[x].second;
    }
}

int h[MaxN];
int par[MaxN];
int sz[MaxN];
int nxt[MaxN];

void PreDFS(int u, int p)
{
    sz[u] = 1;
    nxt[u] = -1;
    for (int x : graph[u])
    {
        if (x != p)
        {
            h[x] = h[u] + 1;
            par[x] = u;
            PreDFS(x, u);
            sz[u] += sz[x];
            if (nxt[u] == -1 || sz[nxt[u]] < sz[x])
            {
                nxt[u] = x;
            }
        }
    }
}

int curChain, curPos;
int ChainHead[MaxN];
int ChainID[MaxN];
int Pos[MaxN];
int Arr[MaxN];

void HLD(int u, int p)
{
    if (ChainHead[curChain] == 0)
    {
        ChainHead[curChain] = u;
    }
    ChainID[u] = curChain;
    Pos[u] = curPos;
    Arr[curPos] = u;
    curPos++;
    if (nxt[u] != -1)
    {
        HLD(nxt[u], u);
    }
    for (int x : graph[u])
    {
        if (x != nxt[u] && x != p)
        {
            curChain++;
            HLD(x, u);
        }
    }
}

int LCA(int u, int v)
{
    while (ChainID[u] != ChainID[v])
    {
        if (ChainID[u] < ChainID[v])
        {
            v = par[ChainHead[ChainID[v]]];
        }
        else
        {
            u = par[ChainHead[ChainID[u]]];
        }
    }
    if (h[u] < h[v])
    {
        return u;
    }
    return v;
}

vector<int> marks[MaxN];
vector<int> markt[MaxN];
vector<int> newgraph[MaxN];

void Build(int id, int l, int r)
{
    if (l == r)
    {
        for (int x : marks[Arr[l]])
        {
            newgraph[id].push_back(8 * n + x);
        }
        for (int x : markt[Arr[r]])
        {
            newgraph[8 * n + x].push_back(4 * n + id);
        }
        return;
    }
    int mid = (l + r) >> 1;
    Build(id << 1, l, mid);
    Build(id << 1 | 1, mid + 1, r);
    newgraph[id].push_back(id << 1);
    newgraph[id].push_back(id << 1 | 1);
    newgraph[(id << 1) + 4 * n].push_back(id + 4 * n);
    newgraph[(id << 1 | 1) + 4 * n].push_back(id + 4 * n);
}

void AddEdgeS(int id, int l, int r, int i, int j, int v)
{
    if (j < l || r < i)
    {
        return;
    }
    if (i <= l && r <= j)
    {
        newgraph[v].push_back(id);
        return;
    }
    int mid = (l + r) >> 1;
    AddEdgeS(id << 1, l, mid, i, j, v);
    AddEdgeS(id << 1 | 1, mid + 1, r, i, j, v);
}

void AddEdgeT(int id, int l, int r, int i, int j, int v)
{
    if (j < l || r < i)
    {
        return;
    }
    if (i <= l && r <= j)
    {
        newgraph[4 * n + id].push_back(v);
        return;
    }
    int mid = (l + r) >> 1;
    AddEdgeT(id << 1, l, mid, i, j, v);
    AddEdgeT(id << 1 | 1, mid + 1, r, i, j, v);
}


int visited[MaxN];
bool isgood;

void DFS(int u)
{
    visited[u] = 1;
    for (int x : newgraph[u])
    {
        if (visited[x] == 1)
        {
            isgood = false;
            return;
        }
        if (visited[x] == 0)
        {
            DFS(x);
            if (!isgood)
            {
                return;
            }
        }
    }
    visited[u] = 2;
}

int jump(int u, int v, int lca)
{
    if (u == lca)
    {
        int pre = -1;
        while (ChainID[v] > ChainID[u])
        {
            pre = ChainHead[ChainID[v]];
            v = par[pre];
        }
        if (v == u)
        {
            return pre;
        }
        return nxt[u];
    }
    return par[u];
}

void Exc()
{
    for (int x = 1; x <= n; x++)
    {
        marks[x].clear();
        markt[x].clear();
        ChainHead[x] = ChainID[x] = Pos[x] = Arr[x] = h[x] = par[x] = sz[x] = nxt[x] = 0;
    }
    for (int x = 1; x <= 8 * n + m; x++)
    {
        newgraph[x].clear();
    }
    PreDFS(1, -1);
    curChain = curPos = 1;
    HLD(1, -1);
    for (int x = 1; x <= m; x++)
    {
        marks[arr[x].first].push_back(x);
        markt[arr[x].second].push_back(x);
    }
    Build(1, 1, n);
    for (int x = 1; x <= m; x++)
    {
        int lca = LCA(arr[x].first, arr[x].second);
        int u = arr[x].first, v = arr[x].second;
        if (u == v)
        {
            continue;
        }
        int u1 = jump(u, v, lca);
        int v1 = jump(v, u, lca);
        while (ChainID[u1] != ChainID[v])
        {
            if (ChainID[u1] > ChainID[v])
            {
                AddEdgeS(1, 1, n, Pos[ChainHead[ChainID[u1]]], Pos[u1], 8 * n + x);
                u1 = par[ChainHead[ChainID[u1]]];
            }
            else
            {
                AddEdgeS(1, 1, n, Pos[ChainHead[ChainID[v]]], Pos[v], 8 * n + x);
                v = par[ChainHead[ChainID[v]]];
            }
        }
        if (h[u1] > h[v])
        {
            swap(u1, v);
        }
        AddEdgeS(1, 1, n, Pos[u1], Pos[v], 8 * n + x);
        while (ChainID[u] != ChainID[v1])
        {
            if (ChainID[u] > ChainID[v1])
            {
                AddEdgeT(1, 1, n, Pos[ChainHead[ChainID[u]]], Pos[u], 8 * n + x);
                u = par[ChainHead[ChainID[u]]];
            }
            else
            {
                AddEdgeT(1, 1, n, Pos[ChainHead[ChainID[v1]]], Pos[v1], 8 * n + x);
                v1 = par[ChainHead[ChainID[v1]]];
            }
        }
        if (h[u] > h[v1])
        {
            swap(u, v1);
        }
        AddEdgeT(1, 1, n, Pos[u], Pos[v1], 8 * n + x);
    }
    /*
    for (int x = 1; x <= 8 * n + m; x++)
    {
        cout << x << ": ";
        for (int y : newgraph[x])
        {
            cout << y << " ";
        }
        cout << "\n";
    }
    */
    for (int x = 1; x <= 8 * n + m; x++)
    {
        visited[x] = 0;
    }
    isgood = true;
    for (int x = 1; x <= 8 * n + m; x++)
    {
        if (visited[x] == 0)
        {
            DFS(x);
            if (!isgood)
            {
                cout << "No" << "\n";
                return;
            }
        }
    }
    cout << "Yes" << "\n";
}

int main()
{
    //freopen("C.INP", "r", stdin);
    //freopen("C.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    cin >> test;
    for (int w = 1; w <= test; w++)
    {
        Inp();
        Exc();
    }
    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