Submission #1156567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156567		AHOKA	Jail (JOI22_jail)	C++20	0 / 100	5095 ms	584 KiB

jail

#pragma GCC optimize("O3") 
#pragma GCC target("sse4")

#include <bits/stdc++.h>

using namespace std;
 
#define threesum cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
#define all(a) a.begin(), a.end()
#define F first
#define S second
//#define int long long
#define pii pair<int, int>
#define ppp pair<int, pii>
#define dout cout << fixed << setprecision(15)
#define mid ((l + r) / 2)
#define lc (2 * id)
#define rc (lc + 1)

const int maxn = 1e3 + 10, maxm = 7e2 + 10, oo = 1e9 + 10, lg = 33, sq = 350, mod = 998244353;

int n, m, h[maxn], par[maxn], a[maxn], b[maxn], st[maxn], ft[maxn], s[maxn], f[maxn], tim;

bool seen[maxn];

vector<int> adj[maxn], out[maxn], topol;

bool in(int v, int p){
    return (st[p] <= st[v] && ft[v] <= ft[p]);
}

void pre_dfs(int v, int p){
    st[v] = ++tim;

    par[v] = p;
    for(auto u : adj[v])
        if(u != p)
            pre_dfs(u, v);

    ft[v] = tim;
}

void dfs(int v){
    seen[v] = 1;

    for (auto u : out[v])
        if(!seen[u])
            dfs(u);
            
    topol.push_back(v);
}

void cl(){
    topol.clear();

    for (int i = 1; i <= n; i++)
    {
        adj[i].clear();
        s[i] = f[i] = 0;
    }

    for (int i = 1; i <= m;i++){
        out[i].clear();
        seen[i] = 0;
    }
}

void solve()
{
    cin >> n;
    for (int i = 1; i < n;i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    pre_dfs(1, 0);

    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i] >> b[i];
        s[a[i]] = i;
        f[b[i]] = i;
    }

    for (int i = 1; i <= m;i++){
        int j;
        int u = a[i];
        int v = b[i];

        while(!in(u, v)){
            j = s[v];
            if (j && j != i)
                out[j].push_back(i);

            j = f[v];
            if (j && j != i)
                out[i].push_back(j);

            v = par[v];
        }

        u = b[i];
        v = a[i];
        while (!in(u, v))
        {
            j = s[v];
            if (j && j != i)
                out[j].push_back(i);

            j = f[v];
            if (j && j != i)
                out[i].push_back(j);

            v = par[v];
        }

        j = s[v];
        if (j && j != i)
            out[j].push_back(i);

        j = f[v];
        if (j && j != i)
            out[i].push_back(j);
    }

    for (int i = 1; i <= m;i++)
        if(!seen[i])
            dfs(i);

    reverse(all(topol));

    bool ok = 1;
    for (auto v : topol){
        for(auto u : out[v])
            ok &= seen[u];
        seen[v] = 0;
    }

    cout << (ok ? "Yes" : "No") << "\n";

    cl();
}

signed main()
{
    threesum;
    int t;
    cin >> t;
    while(t--)
        solve();
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23