Submission #1135295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135295		ace5	Jail (JOI22_jail)	C++20	72 / 100	3302 ms	1114112 KiB

jail

#include <bits/stdc++.h>

using namespace std;

const int maxn = 120001;

int en[maxn];
int st[maxn];
vector<int> g[maxn];
vector<int> ng[maxn];
int par[maxn];
int tin[maxn],tout[maxn];
int times = 0;
bool isc = 0;
int vis[maxn];

void dfs1(int v,int p)
{
    par[v] = p;
    tin[v] = times++;
    for(auto u:g[v])
    {
        if(u != p)
        {
            dfs1(u,v);
        }
    }
    tout[v] = times++;
    return ;
}

void dfs2(int v,int p)
{
    vis[v] = 1;
    for(auto u:ng[v])
    {
        if(!vis[u])
        {
            dfs2(u,v);
        }
        else if(vis[u] == 1)
        {
            isc = 1;
        }

    }
    vis[v] = 2;
    return ;
}

bool isP(int u,int v)
{
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int q;
    cin >> q;
    while(q--)
    {
        int n;
        cin >> n;
        times = 0;
        isc = 0;
        for(int i = 0;i < n;++i)
        {
            en[i] = -1;
            st[i] = -1;
            g[i].clear();
        }
        for(int i = 0;i < n-1;++i)
        {
            int u,v;
            cin >> u >> v;
            u--;
            v--;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs1(0,-1);
        int m;
        cin >> m;
        vector<pair<int,int>> ps;
        for(int i  =0;i < m;++i)
        {
            ng[i].clear();
        }
        for(int i = 0;i < m;++i)
        {
            int u,v;
            cin >> u >> v;
            u--;
            v--;
            ps.push_back({u,v});
            en[v] = i;
            st[u] = i;
        }
        for(int i = 0;i < m;++i)
        {
            int ui = ps[i].first,vi = ps[i].second;
            int u = ps[i].first,v = ps[i].second;
            while(!isP(u,v))
            {
                u = par[u];
              //  cout << u << endl;
                if(st[u] != -1 && u != vi)
                {
                    ng[i].push_back(st[u]);
                }
                if(en[u] != -1 && u != vi)
                {
                    ng[en[u]].push_back(i);
                }
            }
            if(st[v] != -1)
                ng[i].push_back(st[v]);
            while(!isP(v,u))
            {
                v = par[v];
                //cout << v << endl;
                if(st[v] != -1 && v != ui)
                {
                    ng[i].push_back(st[v]);
                }
                if(en[v] != -1 && v != ui)
                {
                    ng[en[v]].push_back(i);
                }
            }
        }
        for(int i = 0;i < m;++i)
        {
            vis[i] = 0;
        }
        for(int i = 0;i < m;++i)
        {
            if(!vis[i])
            {
                dfs2(i,-1);
            }
        }
        cout << (isc ? "No\n" : "Yes\n");
    }
}

• 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