oj.uz

Submission #1033920

# Submission time Handle Problem Language Result Execution time Memory
1033920 2024-07-25T07:45:39 Z vjudge1 Jail (JOI22_jail) C++17
0 / 100
 13 ms 15004 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define int long long
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)

typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;


const int maxn=12e4+23;

int n,m;
int pos[maxn];
vector<int> ke[maxn],adj[maxn*4];
int Count,deg[maxn*4];
int heavy[maxn],par[maxn][21],in[maxn],out[maxn],dep[maxn],Time,head[maxn],rev[maxn];
void reset()
{
    for1(i,0,n+1)
    {
        ke[i].clear();
    }
    for1(i,0,max(n*4+1,Count+1))
    {
        deg[i]=0;
        adj[i].clear();
    }
    Time=0;
    Count=0;
}
void Build(int id=1,int l=1,int r=n)
{
//    cerr<<"skrt "<< id<<' '<<l<<' '<<r<<'\n';
    Count++;
    if (l==r)
    {
       pos[rev[l]]=id;
       return;
    }
    int mid=l+r>>1;
    Build(id*2,l,mid);
    Build(id*2+1,mid+1,r);
    adj[id].pb(id*2);
    adj[id].pb(id*2+1);
//    cerr<< id<<" -> "<<id*2<<'\n';
//    cerr<< id<<" -> "<<id*2+1<<'\n';
    deg[id*2]++;
    deg[id*2+1]++;
}
void Add(int node,int u,int v,int id=1,int l=1,int r=n)
{
    if (u>r || v<l) return;
    if (u<=l && r<=v)
    {
       adj[node].pb(id);
//       cerr<< node<<" -> "<<id<<'\n';
       deg[id]++;
       return;
    }
    int mid=l+r>>1;
    Add(node,u,v,id*2,l,mid);
    Add(node,u,v,id*2+1,mid+1,r);

}

int predfs(int u=1, int pre=1)
{
    int sz=1;
    int sz_mx=1;
    for(int v:ke[u])
    {
        if (v==pre) continue;
        dep[v]=dep[u]+1;
        int sz_v=predfs(v,u);
        if (sz_v >= sz_mx) heavy[u]=v;
        sz+=sz_v;
    }
    return sz;
}

void hld(int u=1,int pre=1,int hd=1)
{
//    cerr<< u<<" s\n";
    in[u]=++Time;
    rev[Time]=u;
    head[u]=hd;
    par[u][0]=pre;
    for1(i,1,20) par[u][i]=par[par[u][i-1]][i-1];
    if (heavy[u]!=-1) hld(heavy[u],u,hd);
    for(int v:ke[u])
    {
        if (v==pre || v==heavy[u]) continue;
        hld(v,u,v);
    }
    out[u]=Time;
}
bool is_ancestor(int u,int v) {return in[u]<=in[v] && out[v]<=out[u];}
int jump(int u,int v)
{
    for2(i,20,0) if (!is_ancestor(par[v][i],u)) v=par[v][i];
    return v;
}
void Update_hld(int node, int u, int v)
{
//    cerr<< " ru\n";
    while (head[u]!=head[v])
    {
        if (dep[head[u]]<dep[head[v]]) swap(u,v);
        Add(node, in[head[u]], in[u]);
//        cerr<< node<<' '<<head[u]<<' '<<u<<" ok\n";
        u=par[head[u]][0];
    }
    if (dep[u]> dep[v]) swap(u,v);
//    cerr<<node<<' '<<u<<' '<<v<< " ok\n";
    Add(node,in[u],in[v]);
}
void sol()
{
    cin >> n;
    reset();
    for1(i,1,n-1)
    {
        int u,v;cin >>u>>v;
        ke[u].pb(v);
        ke[v].pb(u);
    }
    for1(i,1,n) heavy[i]=-1;
    predfs();
//    cerr<< "mf\n";
//    cerr<< heavy[1]<<" q wd\n";
    hld();
    Build();
    cin >> m;
    for1(i,1,m)
    {
        int s,t;cin >> s>> t;
        if (is_ancestor(s,t))
        {
            int ss=jump(s,t);
//            cerr<<ss<< " sir?\n";
            Update_hld(pos[s],ss,t);
        }
        else
        {
            Update_hld(pos[s],par[s][0],t);
//            cerr<<"zz "<< par[s][0]<<' '<<t<<'\n';
        }
    }

//    for1(i,1,n)
//    {
//        cerr<<"zzz "<< i<<' '<<in[i]<<' '<<head[i]<<'\n';
//    }
//    cerr<< Count<<'\n';
    vector<int> L;
    if (deg[1]!=0)
    {
        cout << "No\n";
        return;
    }
    L.pb(1);
    int g=0;
    while (!L.empty())
    {
        int u=L.back();
//        cerr<<"wa "<< u<<' '<<deg[u]<<'\n';
        L.pop_back();
        g++;
        for(int v:adj[u])
        {
            --deg[v];
            if (deg[v]==0) L.pb(v);
//            if (u==1) cerr<<"as "<< v<<'\n';
        }
    }
    if (Count!=g) cout << "No\n";
    else cout << "Yes\n";
//    for1(i,1,Count) cout<<"za " << i<<' '<<deg[i]<<'\n';
//    cerr<< g<<'\n';


}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("jail.inp","r",stdin);
//    freopen("jail.out","w",stdout);
    int t=1;cin >> t;
    while (t--) sol();
}
/*
1
20
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
1
20 8
*/
/*
2
18
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
5
17 5
12 1
10 15
11 17
6 14
20
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
1
20 8
*/

Compilation message

jail.cpp: In function 'void Build(long long int, long long int, long long int)':
jail.cpp:45:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     int mid=l+r>>1;
      |             ~^~
jail.cpp: In function 'void Add(long long int, long long int, long long int, long long int, long long int, long long int)':
jail.cpp:65:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |     int mid=l+r>>1;
      |             ~^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14428 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 6 ms 14400 KB Output is correct
4 Incorrect 13 ms 15004 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14680 KB Output is correct
2 Correct 7 ms 14392 KB Output is correct
3 Incorrect 7 ms 14684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14680 KB Output is correct
2 Correct 7 ms 14392 KB Output is correct
3 Incorrect 7 ms 14684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14680 KB Output is correct
2 Correct 7 ms 14392 KB Output is correct
3 Incorrect 7 ms 14684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14680 KB Output is correct
2 Correct 7 ms 14392 KB Output is correct
3 Incorrect 7 ms 14684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 6 ms 14384 KB Output is correct
4 Correct 7 ms 14428 KB Output is correct
5 Incorrect 11 ms 14684 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14428 KB Output is correct
2 Correct 6 ms 14428 KB Output is correct
3 Correct 6 ms 14400 KB Output is correct
4 Incorrect 13 ms 15004 KB Output isn't correct
5 Halted 0 ms 0 KB -