oj.uz

Submission #876186

# Submission time Handle Problem Language Result Execution time Memory
876186 2023-11-21T11:30:57 Z simona1230 Jail (JOI22_jail) C++17
0 / 100
 89 ms 12124 KB 
#include <bits/stdc++.h>
using namespace std;
int q,n,m;
vector<int> v[120001];
int s[120001],f[120001];
int par[120001];
int nums[120001];
int numf[120001];
void read()
{
    memset(nums,0,sizeof(nums));
    memset(numf,0,sizeof(numf));
    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])
        {
            par[nb]=i;
            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 ver;
vector<int> p1,p2;
void backtr(int i,int idx)
{
    if(i==ver)return;
    if(idx==1)p1.push_back(i);
    else p2.push_back(i);
    backtr(par[i],idx);
}
void gen(int a,int b)
{
    p.clear();
    ver=lca(a,b);
    p1.clear();
    p2.clear();
    backtr(a,1);
    backtr(b,2);
    p=p1;
    p.push_back(ver);
    for(int i=p2.size()-1; i>=0; i--)
        p.push_back(p2[i]);
}
int in[1001][1001];
void solve()
{
    memset(in,0,sizeof(in));
    bool pos=1;
    for(int i=1;i<=m;i++)
    {
        gen(s[i],f[i]);
        //cout<<s[i]<<" - "<<f[i]<<endl;
        for(int j=0;j<p.size();j++)
        {
            int idx=p[j];
            //cout<<p[j]<<" "<<nums[idx]<<endl;
            if(in[f[nums[idx]]][s[i]])
            {
                //cout<<nums[idx]<<" "<<i<<" "<<f[nums[idx]]<<endl;
                pos=0;
            }
            in[i][p[j]]=1;
        }
        nums[s[i]]=i;
        numf[f[i]]=i;
        for(int j=1;j<i;j++)
        {
            if(in[j][s[i]]&&in[j][f[i]])
            {
                //cout<<i<<" "<<j<<endl;
                pos=0;
            }
        }
    }
    /*for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<in[i][j]<<" ";
        }
        cout<<endl;
    }*/
    if(pos)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}
void subt()
{
    for(int i=1;i<=n;i++)
    {
        cout<<nums[i]<<" "<<numf[i]<<endl;
    }
}
int main()
{
    cin>>q;
    while(q--)
    {
        memset(used,0,sizeof(used));
        read();
        dfs(1);
        prec();
        solve();
        //read();
        //subt();
    }
    return 0;
}

Compilation message

jail.cpp: In function 'void dfs(int)':
jail.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int j=0; j<v[i].size(); j++)
      |                  ~^~~~~~~~~~~~
jail.cpp: In function 'void solve()':
jail.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         for(int j=0;j<p.size();j++)
      |                     ~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11868 KB Output is correct
2 Correct 2 ms 11868 KB Output is correct
3 Correct 2 ms 12020 KB Output is correct
4 Incorrect 57 ms 12124 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11868 KB Output is correct
2 Correct 2 ms 12020 KB Output is correct
3 Incorrect 5 ms 12124 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11868 KB Output is correct
2 Correct 2 ms 12020 KB Output is correct
3 Incorrect 5 ms 12124 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11868 KB Output is correct
2 Correct 2 ms 12020 KB Output is correct
3 Incorrect 5 ms 12124 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11868 KB Output is correct
2 Correct 2 ms 12020 KB Output is correct
3 Incorrect 5 ms 12124 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12120 KB Output is correct
2 Correct 2 ms 11868 KB Output is correct
3 Correct 2 ms 11868 KB Output is correct
4 Correct 2 ms 12124 KB Output is correct
5 Incorrect 89 ms 11868 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11868 KB Output is correct
2 Correct 2 ms 11868 KB Output is correct
3 Correct 2 ms 12020 KB Output is correct
4 Incorrect 57 ms 12124 KB Output isn't correct
5 Halted 0 ms 0 KB -