제출 #624217

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
624217		boris_mihov	Jail (JOI22_jail)	C++14	72 / 100	5034 ms	586544 KiB

jail

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

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

int n, q;
int parent[MAXN];
int in[MAXN], out[MAXN], timer;
int begin[MAXN], end[MAXN];
std::vector <int> g[MAXN];
std::vector <int> v[MAXN];
int from[MAXN], to[MAXN];

void initDFS(int node, int p)
{
    parent[node] = p;
    in[node] = ++timer;
    for (const int &i : g[node])
    {
        if (i == p) continue;
        initDFS(i, node);
    }

    out[node] = ++timer;
}

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

void cyclePath(int start, int finish, int num)
{
    if (inSubtree(start, finish))
    {
        if (begin[start] != 0 && begin[start] != num)
        {
            v[num].push_back(begin[start]);
        }

        if (end[start] != 0 && end[start] != num)
        {
            v[end[start]].push_back(num);
        }

        if (start != finish) cyclePath(parent[start], finish, num);
    } else
    {
        if (begin[finish] != 0 && begin[finish] != num)
        {
            v[num].push_back(begin[finish]);
        }

        if (end[finish] != 0 && end[finish] != num)
        {
            v[end[finish]].push_back(num);
        }

        cyclePath(start, parent[finish], num);
    }
}

int vis[MAXN];
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()
{
    initDFS(1, 0);
    for (int i = 1 ; i <= q ; ++i)
    {
        if (from[i] == to[i]) continue;
        cyclePath(from[i], to[i], i);
    }

    for (int i = 1 ; i <= q ; ++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];
        begin[from[i]] = i;
        end[to[i]] = i;
    }
}

void reset()
{
    for (int i = 1 ; i <= std::max(n, q) ; ++i)
    {
        g[i].clear();
        v[i].clear();
        begin[i] = 0;
        end[i] = 0;
        vis[i] = 0;
        timer = 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: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 0 / 23