제출 #1337005

#제출 시각아이디문제언어결과실행 시간메모리
1337005chikien2009Jail (JOI22_jail)C++20
100 / 100
1461 ms326496 KiB
#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int q, n, m, a, b;  
int s[18][120000], t[18][120000], sp[18][120000];
int depth[120000], state[4320000];
bool found;
pair<int, int> p[120000];
vector<int> g[120000], h[4320000];

inline void DFS(int node, int par)
{
    sp[0][node] = par;
    for (int i = 1; i < 18; ++i)
    {
        sp[i][node] = sp[i - 1][sp[i - 1][node]];
        h[s[i - 1][node]].push_back(s[i][node]);
        h[s[i - 1][sp[i - 1][node]]].push_back(s[i][node]);
        h[t[i][node]].push_back(t[i - 1][node]);
        h[t[i][node]].push_back(t[i - 1][sp[i - 1][node]]);
    }
    for (auto & i : g[node])
    {
        if (i != par)
        {
            depth[i] = depth[node] + 1;
            DFS(i, node);
        }
    }
}

inline int LCA(int ina, int inb)
{
    if (depth[ina] < depth[inb])
    {
        swap(ina, inb);
    }
    for (int i = 17; i >= 0; --i)
    {
        if (depth[sp[i][ina]] >= depth[inb])
        {
            ina = sp[i][ina];
        }
    }
    if (ina == inb)
    {
        return ina;
    }
    for (int i = 17; i >= 0; --i)
    {
        if (sp[i][ina] != sp[i][inb])
        {
            ina = sp[i][ina];
            inb = sp[i][inb];
        }
    }
    return sp[0][ina];
}

inline int Prev(int ina, int inb)
{
    for (int i = 17; i >= 0; --i)
    {
        if (depth[sp[i][ina]] > depth[inb])
        {
            ina = sp[i][ina];
        }
    }
    return ina;
}

inline void ScanS(int ina, int inb, int ind)
{
    for (int i = 17; i >= 0; --i)
    {
        if (depth[sp[i][ina]] >= depth[inb])
        {        
            h[s[i][ina]].push_back(ind);
            ina = sp[i][ina];
        }
    }
    h[s[0][ina]].push_back(ind);
}

inline void ScanT(int ina, int inb, int ind)
{
    for (int i = 17; i >= 0; --i)
    {
        if (depth[sp[i][ina]] >= depth[inb])
        {
            h[ind].push_back(t[i][ina]);
            ina = sp[i][ina];
        }
    }
    h[ind].push_back(t[0][ina]);
}

inline void DFS1(int node)
{
    state[node] = 1;
    for (auto & i : h[node])
    {
        if (found)
        {
            return;
        }
        if (state[i] == 0)
        {
            DFS1(i);
        }
        else if (state[i] == 1)
        {
            found = true;
            return;
        }
    }
    state[node] = 2;
}

int main()
{
    setup();

    cin >> q;
    while (q--)
    {
        cin >> n;
        found = false;
        fill_n(g, n, vector<int>());
        for (int i = 0; i < 18; ++i)
        {
            fill_n(s[i], n, -1);
            fill_n(t[i], n, -1);
        }
        for (int i = 0; i < n - 1; ++i)
        {
            cin >> a >> b;
            g[a - 1].push_back(b - 1);
            g[b - 1].push_back(a - 1);
        }
        cin >> m;
        for (int i = 0; i < m; ++i)
        {
            cin >> a >> b;
            p[i] = {a - 1, b - 1};
            s[0][a - 1] = i;
            t[0][b - 1] = i;
        }
        a = m;
        for (int i = 0; i < 18; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (s[i][j] == -1)
                {
                    s[i][j] = a++;
                }
                if (t[i][j] == -1)
                {
                    t[i][j] = a++;
                }
            }
        }
        fill_n(h, a, vector<int>());
        fill_n(state, a, 0);
        b = a;
        DFS(0, 0);
        for (int i = 0; i < m; ++i)
        {
            a = LCA(p[i].first, p[i].second);
            if (p[i].first == a)
            {
                ScanS(p[i].second, Prev(p[i].second, p[i].first), i);
                ScanT(sp[0][p[i].second], p[i].first, i);
            }
            else if (p[i].second == a)
            {
                ScanS(sp[0][p[i].first], p[i].second, i);
                ScanT(p[i].first, Prev(p[i].first, p[i].second), i);
            }
            else
            {
                ScanS(sp[0][p[i].first], a, i);
                ScanS(p[i].second, a, i);
                ScanT(p[i].first, a, i);
                ScanT(sp[0][p[i].second], a, i);
            }
        }
        for (int i = 0; i < b && !found; ++i)
        {
            if (state[i] == 0)
            {
                DFS1(i);
            }
        }
        cout << (found ? "No" : "Yes") << "\n";
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...