Submission #1034084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034084		vjudge1	Jail (JOI22_jail)	C++17	0 / 100	517 ms	627796 KiB

jail

#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];
vector<pii> el;
int dd[maxn*4];
void lca(int u,int v)
{
    while (u!=v)
    {
        if (u<v) swap(u,v);
        u/=2;
    }
    while(u!=1)
    {
        dd[u]++;
//        cerr<< u<<'\n';
        u/=2;
    }
    dd[u]++;
}
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);
        el.pb({node,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';
        }
    }
//    cerr<< el.size()<<'\n';
    for(auto [u,v]: el)
    {
//        int uu;
//        if (is_ancestor(u,v)) uu=jump(u,v);
//        else uu=par[u][0];
        lca(u,v);
//        cerr<< u<<' '<<v<<" gg\n";
    }
    for(auto [u,v]: el)
    {
        if (dd[v])
        {
            cout << "No\n";
            return;
        }
        adj[u].pb(v);
    }
//    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();
}
/*
2
3
1 2
1 3
2
1 1
1 2
7
1 2
1 3
3 4
4 5
3 6
6 7
2
3 4
5 6
*/
/*
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 (stderr)

jail.cpp: In function 'void Build(long long int, long long int, long long int)':
jail.cpp:62:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |     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:83:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |     int mid=l+r>>1;
      |             ~^~
jail.cpp: In function 'int32_t main()':
jail.cpp:228:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  228 |     freopen("jail.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
jail.cpp:229:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  229 |     freopen("jail.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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