Submission #624860

#	Time	Username	Problem	Language	Result	Execution time	Memory
624860		boris_mihov	Jail (JOI22_jail)	C++14	100 / 100	1028 ms	82740 KiB

jail

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 120000 + 10;
const int INF  = 2e9;

int n, q;
int vis[10 * MAXN];
int sz[MAXN], head[MAXN];
int from[MAXN], to[MAXN];
int depth[MAXN], inS[MAXN], inE[MAXN];
int parent[MAXN], heavy[MAXN];
int start[MAXN], end[MAXN];
int in[MAXN], out[MAXN], timer;
std::vector <int> g[MAXN];
std::vector <int> v[10 * MAXN];
std::vector <int> chainS, chainE;

inline bool inSubtree(int x, int y)
{
    return in[y] <= in[x] && in[x] <= out[y];
}

void dfs(int node, int p)
{
    in[node] = ++timer;
    parent[node] = p;
    depth[node] = depth[p] + 1;
    sz[node] = 1;

    for (const int &i : g[node])
    {
        if (i == p) continue;
        dfs(i, node);
        sz[node] += sz[i];
        if (sz[i] > sz[heavy[node]])
        {
            heavy[node] = i;
        }
    }

    out[node] = ++timer;
}

void decompose(int node, int h)
{
    head[node] = h;
    if (start[node] != 0) chainS.push_back(start[node]);
    if (end[node] != 0) chainE.push_back(end[node]);
    inS[node] = chainS.size() - 1;
    inE[node] = chainE.size() - 1;
    if (heavy[node] != 0) decompose(heavy[node], h);

    for (const int &i : g[node])
    {
        if (i == parent[node] || i == heavy[node]) continue;
        decompose(i, i);
    }
}

int treeS[4 * MAXN];
int treeE[4 * MAXN];
int cnt;

void buildS(int l, int r, int node)
{
    if (l == r)
    {
        treeS[node] = chainS[l];
        return;
    }

    treeS[node] = ++cnt;
    int mid = (l + r) / 2;
    buildS(l, mid, 2*node);
    buildS(mid + 1, r, 2*node + 1);
    v[treeS[2*node]].push_back(treeS[node]);
    v[treeS[2*node + 1]].push_back(treeS[node]);
}

void buildE(int l, int r, int node)
{
    if (l == r)
    {
        treeE[node] = chainE[l];
        return;
    }

    treeE[node] = ++cnt;
    int mid = (l + r) / 2;
    buildE(l, mid, 2*node);
    buildE(mid + 1, r, 2*node + 1);
    v[treeE[node]].push_back(treeE[2*node]);
    v[treeE[node]].push_back(treeE[2*node + 1]);
}

void addEdgesS(int l, int r, int node, int queryL, int queryR, int fromNode)
{
    if (queryL <= l && r <= queryR)
    {
        v[treeS[node]].push_back(fromNode);
        return;
    }

    int mid = (l + r) / 2;
    if (queryL <= mid) addEdgesS(l, mid, 2*node, queryL, queryR, fromNode);
    if (mid + 1 <= queryR) addEdgesS(mid + 1, r, 2*node + 1, queryL, queryR, fromNode);
}

void addEdgesE(int l, int r, int node, int queryL, int queryR, int fromNode)
{
    if (queryL <= l && r <= queryR)
    {
        v[fromNode].push_back(treeE[node]);
        return;
    }

    int mid = (l + r) / 2;
    if (queryL <= mid) addEdgesE(l, mid, 2*node, queryL, queryR, fromNode);
    if (mid + 1 <= queryR) addEdgesE(mid + 1, r, 2*node + 1, queryL, queryR, fromNode);
}

void hldAddS(int x, int y, int node)
{
    while (head[x] != head[y])
    {
        if (depth[head[x]] <= depth[head[y]]) std::swap(x, y);
        int addFrom = inS[head[x]];
        int addTo = inS[x];
        if (start[head[x]] == 0) ++addFrom;
        if (addFrom >= 0 && addFrom <= addTo) addEdgesS(0, chainS.size()-1, 1, addFrom, addTo, node);
        x = parent[head[x]];
    }

    if (depth[x] > depth[y]) std::swap(x, y);
    int addFrom = inS[x];
    int addTo = inS[y];
    if (start[x] == 0) ++addFrom;
    if (addFrom >= 0 && addFrom <= addTo) addEdgesS(0, chainS.size()-1, 1, addFrom, addTo, node);
}

void hldAddE(int x, int y, int node)
{
    while (head[x] != head[y])
    {
        if (depth[head[x]] <= depth[head[y]]) std::swap(x, y);
        int addFrom = inE[head[x]];
        int addTo = inE[x];
        if (end[head[x]] == 0) ++addFrom;
        if (addFrom >= 0 && addFrom <= addTo) addEdgesE(0, chainE.size()-1, 1, addFrom, addTo, node);
        x = parent[head[x]];
    }

    if (depth[x] > depth[y]) std::swap(x, y);
    int addFrom = inE[x];
    int addTo = inE[y];
    if (end[x] == 0) ++addFrom;
    if (addFrom >= 0 && addFrom <= addTo) addEdgesE(0, chainE.size()-1, 1, addFrom, addTo, node);
}

bool findCycle(int node)
{
    vis[node] = 1;
    for (const int &i : v[node])
    {
        if (vis[i] == 2) continue;
        if (vis[i] == 1) return true;
        if (findCycle(i)) return true;
    }

    vis[node] = 2;
    return false;
}

void solve()
{
    dfs(1, 0);
    decompose(1, 1); cnt = q;
    buildS(0, chainS.size()-1, 1);
    buildE(0, chainE.size()-1, 1);

    for (int i = 1 ; i <= q ; ++i)
    {
        if (from[i] == to[i]) continue;
        if (!inSubtree(to[i], from[i])) 
        {
            hldAddS(parent[from[i]], to[i], i);
        }
        else
        {
            for (const int &neigh : g[from[i]])
            {
                if (neigh == parent[from[i]]) continue;
                if (inSubtree(to[i], neigh))
                {
                    hldAddS(neigh, to[i], i);
                    break;
                }
            }
        }

        if (!inSubtree(from[i], to[i])) 
        {
            hldAddE(from[i], parent[to[i]], i);
        }
        else
        {
            for (const int &neigh : g[to[i]])
            {
                if (neigh == parent[to[i]]) continue;
                if (inSubtree(from[i], neigh))
                {
                    hldAddE(from[i], neigh, i);
                    break;
                }
            }
        }
    }

    for (int i = 1 ; i <= cnt ; ++i)
    {
        if (vis[i] == 2) continue;
        if (findCycle(i))
        {
            std::cout << "No\n";
            return;
        }
    }

    std::cout << "Yes\n";
}

void read()
{
    int x, y;
    std::cin >> n;
    for (int i = 2 ; i <= n ; ++i)
    {
        std::cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    std::cin >> q;
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cin >> from[i] >> to[i];
        start[from[i]] = i;
        end[to[i]] = i;
    }
}

void reset()
{
    for (int i = 1 ; i <= cnt ; ++i)
    {
        v[i].clear();
        vis[i] = 0;
    }

    timer = 0;
    chainS.clear();
    chainE.clear();
    for (int i = 1 ; i <= n ; ++i)
    {
        in[i] = 0;
        out[i] = 0;
        g[i].clear();
        start[i] = 0;
        end[i] = 0;
        sz[i] = 0;
        head[i] = 0;
        from[i] = 0;
        to[i] = 0;
        depth[i] = 0;
        inS[i] = 0;
        inE[i] = 0;
        parent[i] = 0;
        heavy[i] = 0;
        start[i] = 0;
        end[i] = 0;
        in[i] = 0;
        out[i] = 0;
    }
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int tests;
int main()
{
    fastIO();
    std::cin >> tests;

    while (tests--)
    {
        reset();
        read();
        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