Submission #609671

#	Time	Username	Problem	Language	Result	Execution time	Memory
609671		Mher	Jail (JOI22_jail)	C++14	72 / 100	5094 ms	851420 KiB

jail

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9 + 7;

int n, m;
vector<vector<int>> g, p;
vector<int> tin, tout;
vector<int> s, f;
vector<int> col;
vector<int> parent;
vector<int> st, ft;
int cnt = 0;

void dfs(int v, int pr)
{
    tin[v] = cnt++;
    parent[v] = pr;
    for (int to : g[v])
    {
        if (to == pr)
            continue;

        dfs(to, v);
    }
    tout[v] = cnt;
}

bool child(int a, int b)
{
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

void build(int v)
{
    //cout << v << endl;
    int pnt = s[v];
    while (!child(pnt, f[v]))
    {
        //cout << '-' << pnt << endl;
        if (st[pnt] >= 0)
        {
            p[v].push_back(st[pnt]);
        }
        if (ft[pnt] >= 0)
        {
            p[ft[pnt]].push_back(v);
        }
        pnt = parent[pnt];
    }
    pnt = f[v];
    while (!child(pnt, s[v]))
    {
        //cout << '-' << pnt << endl;
        if (st[pnt] >= 0)
        {
            p[v].push_back(st[pnt]);
        }
        if (ft[pnt] >= 0)
        {
            p[ft[pnt]].push_back(v);
        }
        pnt = parent[pnt];
    }
    if (st[pnt] >= 0)
    {
        p[v].push_back(st[pnt]);
    }
    if (ft[pnt] >= 0)
    {
        p[ft[pnt]].push_back(v);
    }
}

bool cicle(int v)
{
    col[v] = 1;
    bool ans = true;
    for (int to : p[v])
    {
        if (to == v)
            continue;
        if (col[to] == 1)
            return false;
        if (col[to] == 0)
            ans &= cicle(to);
    }
    col[v] = 2;
    return ans;
}

void solve()
{
    cin >> n;
    g.resize(n + 1);
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    cin >> m;
    p.resize(m);
    s.resize(m);
    f.resize(m);
    st.resize(n + 1, -1);
    ft.resize(n + 1, -1);
    for (int i = 0; i < m; i++)
    {
        cin >> s[i] >> f[i];
        st[s[i]] = i;
        ft[f[i]] = i;
    }
    tin.resize(n + 1);
    tout.resize(n + 1);
    parent.resize(n + 1);
    dfs(1, 0);
    col.resize(m, 0);
    for (int i = 0; i < m; i++)
    {
        build(i);
    }
    bool ans = true;
    for (int i = 0; i < m; i++)
    {
        if (col[i] == 0)
            ans &= cicle(i);
    }
    cout << (ans ? "Yes" : "No") << endl;
    g.clear();
    p.clear();
    tin.clear();
    tout.clear();
    s.clear();
    f.clear();
    col.clear();
    parent.clear();
    st.clear();
    ft.clear();
}

int main()
{
    int q;
    cin >> q;
    while (q--)
        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