Submission #1020130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020130		alexdd	Jail (JOI22_jail)	C++17	72 / 100	5084 ms	924976 KiB

jail

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> tree[120005],con[120005];
vector<int> son[120005],ton[120005];
pair<int,int> drum[120005];
int depth[120005],parent[120005],pos[120005],curpos,head[120005],siz[120005],cine[120005];
bool visited[120005];
void resetare()
{
    curpos=0;
    for(int i=1;i<=n;i++)
    {
        con[i].clear();
        tree[i].clear();
        son[i].clear();
        ton[i].clear();
        visited[i]=0;
    }
}

void dfs_tree(int nod)
{
    siz[nod]=1;
    for(auto adj:tree[nod])
    {
        if(adj!=parent[nod])
        {
            parent[adj]=nod;
            depth[adj]=depth[nod]+1;
            dfs_tree(adj);
            siz[nod]+=siz[adj];
        }
    }
}
void decompose(int nod, int chead)
{
    pos[nod]=++curpos;
    cine[pos[nod]]=nod;
    head[nod]=chead;
    int maxc=-1,heavy=-1;
    for(auto adj:tree[nod])
        if(adj!=parent[nod] && siz[adj]>maxc)
            maxc=siz[adj], heavy=adj;
    if(heavy!=-1)
        decompose(heavy,chead);
    for(auto adj:tree[nod])
        if(adj!=parent[nod] && adj!=heavy)
            decompose(adj,adj);
}


void baga_aint(int nod, int st, int dr, int le, int ri, int from)
{
    for(int i=le;i<=ri;i++)
    {
        for(auto x:son[cine[i]])
            con[x].push_back(from);
        for(auto x:ton[cine[i]])
            con[from].push_back(x);
    }
}
void baga_hld(int a, int b, int from)
{
    for(;head[a]!=head[b];b=parent[head[b]])
    {
        if(depth[head[a]]>depth[head[b]])
            swap(a,b);
        baga_aint(1,1,n,pos[head[b]],pos[b],from);
    }
    if(pos[a]>pos[b])
        swap(a,b);
    baga_aint(1,1,n,pos[a],pos[b],from);
}

vector<int> topo;
int topo_pos[120005];
void dfs_graph(int nod)
{
    visited[nod]=1;
    for(auto adj:con[nod])
        if(!visited[adj])
            dfs_graph(adj);
    topo.push_back(nod);
}
bool has_cycle()
{
    topo.clear();
    for(int i=1;i<=n;i++)
        if(!visited[i])
            dfs_graph(i);
    reverse(topo.begin(),topo.end());
    for(int i=0;i<topo.size();i++)
        topo_pos[topo[i]]=i;
    for(int i=0;i<topo.size();i++)
        for(auto x:con[topo[i]])
            if(topo_pos[x]<i)
                return 1;
    return 0;
}

signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        resetare();
        int a,b;
        for(int i=1;i<n;i++)
        {
            cin>>a>>b;
            tree[a].push_back(b);
            tree[b].push_back(a);
        }
        cin>>m;
        for(int i=1;i<=m;i++)
        {
            cin>>a>>b;
            drum[i]={a,b};
            son[a].push_back(i);
            ton[b].push_back(i);
        }
        dfs_tree(1);
        decompose(1,1);
        for(int i=1;i<=m;i++)
        {
            baga_hld(drum[i].first,drum[i].second,i);
        }

        if(has_cycle()) cout<<"No\n";
        else cout<<"Yes\n";
    }
    return 0;
}

Compilation message (stderr)

jail.cpp: In function 'bool has_cycle()':
jail.cpp:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i=0;i<topo.size();i++)
      |                 ~^~~~~~~~~~~~
jail.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i=0;i<topo.size();i++)
      |                 ~^~~~~~~~~~~~

• 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