Submission #876223

#	Time	Username	Problem	Language	Result	Execution time	Memory
876223		simona1230	Jail (JOI22_jail)	C++17	61 / 100	5045 ms	35472 KiB

jail

#include <bits/stdc++.h>
using namespace std;
int q,n,m;
vector<int> v[120001];
vector<int> g[120001],o[120001];
int s[120001],f[120001];
void read()
{
    cin>>n;
    for(int i=1; i<=n; i++)
        v[i].clear();
    for(int i=1; i<n; i++)
    {
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    cin>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>s[i]>>f[i];
    }
}
vector<int> p;
int jump[120001][21];
int used[120001];
int lvl[120001];
void dfs(int i)
{
    used[i]=1;
    for(int j=0; j<v[i].size(); j++)
    {
        int nb=v[i][j];
        if(!used[nb])
        {
            lvl[nb]=lvl[i]+1;
            jump[nb][0]=i;
            dfs(nb);
        }
    }
}
void prec()
{
    for(int j=1; j<=20; j++)
        for(int i=1; i<=n; i++)
            jump[i][j]=jump[jump[i][j-1]][j-1];
}
int make_jump(int x,int k)
{
    for(int i=20; i>=0; i--)
        if(k&(1<<i))
            x=jump[x][i];
    return x;
}
int lca(int x,int y)
{
    if(lvl[x]>lvl[y])swap(x,y);
    y=make_jump(y,abs(lvl[y]-lvl[x]));
    if(x==y)return x;
    for(int i=20; i>=0; i--)
    {
        if(jump[x][i]!=jump[y][i])
        {
            x=jump[x][i];
            y=jump[y][i];
        }
    }
    return jump[x][0];
}
int used1[120001];
stack<int> st;
void dfs1(int i)
{
    used1[i]=1;
    for(int j=0;j<g[i].size();j++)
    {
        int nb=g[i][j];
        if(!used1[nb])
        {
            dfs1(nb);
        }
    }
    st.push(i);
}
int used2[120001];
void dfs2(int i)
{
    used2[i]=1;
    for(int j=0;j<o[i].size();j++)
    {
        int nb=o[i][j];
        if(!used2[nb])
        {
            dfs2(nb);
        }
    }
}
void solve()
{
    bool pos=1;
    for(int i=1;i<=m;i++)
    {
        o[i].clear();
        g[i].clear();
    }
    memset(used1,0,sizeof(used1));
    memset(used2,0,sizeof(used2));
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int l=lca(s[i],f[i]);
            int l1=lca(s[i],s[j]);
            int l2=lca(f[i],s[j]);
            //cout<<l<<" "<<l1<<" "<<l2<<endl;
            if(l1==s[j]&&l2==l||l1==l&&l2==s[j])
            {
                g[j].push_back(i);
                //cout<<i<<" "<<j<<endl;
                o[i].push_back(j);
            }
            l1=lca(s[i],f[j]);
            l2=lca(f[i],f[j]);
            if(l1==f[j]&&l2==l||l1==l&&l2==f[j])
            {
                g[i].push_back(j);
                //cout<<j<<" "<<i<<endl;
                o[j].push_back(i);
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        if(!used1[i])dfs1(i);
    }
    int cnt=0;
    while(st.size())
    {
        int vr=st.top();
        st.pop();
        if(!used2[vr])
        {
            cnt++;
            dfs2(vr);
        }
    }
    if(cnt==m)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}
int main()
{
    cin>>q;
    while(q--)
    {
        memset(used,0,sizeof(used));
        read();
        dfs(1);
        prec();
        solve();
    }
    return 0;
}

Compilation message (stderr)

jail.cpp: In function 'void dfs(int)':
jail.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int j=0; j<v[i].size(); j++)
      |                  ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs1(int)':
jail.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int j=0;j<g[i].size();j++)
      |                 ~^~~~~~~~~~~~
jail.cpp: In function 'void dfs2(int)':
jail.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int j=0;j<o[i].size();j++)
      |                 ~^~~~~~~~~~~~
jail.cpp: In function 'void solve()':
jail.cpp:117:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  117 |             if(l1==s[j]&&l2==l||l1==l&&l2==s[j])
      |                ~~~~~~~~^~~~~~~
jail.cpp:125:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  125 |             if(l1==f[j]&&l2==l||l1==l&&l2==f[j])
      |                ~~~~~~~~^~~~~~~
jail.cpp:101:10: warning: unused variable 'pos' [-Wunused-variable]
  101 |     bool pos=1;
      |          ^~~

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