oj.uz

Submission #1076636

# Submission time Handle Problem Language Result Execution time Memory
1076636 2024-08-26T15:10:30 Z modwwe Jail (JOI22_jail) C++17
61 / 100
 308 ms 63828 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int long long
//#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void phongbeo();
const int inf=1e9;
const int mod2=1e9+7;
const int  mod1=998244353;
struct icd
{
    long double a;
    int b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c,d,e;

};

int n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,dem4,l,r,mid;
int  i,s10,s12;
int kk;
int el=29;

main()
{
#ifndef ONLINE_JUDGE
     // fin(task),fou(task);
#endif
    NHP
    /// cin>>s1;
    modwwe
    phongbeo(),down
//checktime
}
int st[17][120001];
int depth[120001];
int head[120001];
int pos[120001];
vector<int> v[120001];
int heavy[120001];
ib a[120001];
int b[120001];
int c[120001];
stack<int> s;
int vitri[120001];
vector<int> v2[480001];
int f[120001];
int dfs(int x,int y)
{
    int sz=1;
    int mxz=0;
    st[0][x]=y;
    depth[x]=depth[y]+1;
    for(auto f:v[x])
    {
        if(f!=y)
        {
            s2=dfs(f,x);
            sz+=s2;
            if(s2>mxz)
                heavy[x]=f,mxz=s2;
        }
    }
    return sz;
}
int lca2(int x,int y)
{
    if(depth[x]<depth[y]) swap(x,y);
    int ss=depth[x]-depth[y]-1;
    if(ss>=0)
        for(int j=0; j<17; ++j)
            if(bit(ss,j))
                x=st[j][x];
    if(st[0][x]==y) return x;
    if(ss!=-1)  x=st[0][x];
    for(int j=16; j>=0; --j)
        if(st[j][x]!=st[j][y])
            x=st[j][x],y=st[j][y];
    return x;
}
int lca(int x,int y)
{
    if(depth[x]<depth[y]) swap(x,y);
    int ss=depth[x]-depth[y];
    for(int j=0; j<17; ++j)
        if(bit(ss,j))
            x=st[j][x];
    if(x==y) return x;
    for(int j=16; j>=0; --j)
        if(st[j][x]!=st[j][y])
            x=st[j][x],y=st[j][y];
    return st[0][x];
}
void des(int x,int y)
{
    head[x]=y;
    pos[x]=++dem;
    if(heavy[x]!=0)
        des(heavy[x],y);
    for(auto f:v[x])
        if(pos[f]==0)
            des(f,f);
}
struct IT
{
    int t[480000];
    int t2[480000];
    void ff(int x)
    {
        for(int i=x*2; i<=x*2+1; i++)
            t2[i]+=t2[x];
        t2[x]=0;
    }
    void upd_in(int node,int l,int r,int l1,int r1)
    {
        if(l>r1||r<l1) return;
        if(l>=l1&&r<=r1)
        {
            t[node]=1;
            return;
        }
        int mid=l+r>>1;
        upd_in(node<<1,l,mid,l1,r1);
        upd_in(node<<1|1,mid+1,r,l1,r1);
        t[node]=t[node<<1]+t[node<<1|1];
    }
    int get(int node,int l,int r,int l1,int r1,int x)
    {
        if(l>r1||r<l1) return 0;
        if(l>=l1&&r<=r1)
        {
            v2[node].pb(x);
            t2[node]++;
            //   cout<<t2[node]<<" "<<node<<" "<<l<<" "<<r<<" "<<l1<<" "<<r1,down
            return t[node];
        }
        int mid=l+r>>1;
        return get(node<<1,l,mid,l1,r1,x)+get(node<<1|1,mid+1,r,l1,r1,x);
    }
    int get2(int node,int l,int r,int l1,int r1)
    {
        if(l>r1||r<l1) return 0;
        if(l>=l1&&r<=r1) return t2[node];
        ff(node);
        int mid=l+r>>1;
        return get2(node<<1,l,mid,l1,r1)+get2(node<<1|1,mid+1,r,l1,r1);

    }
    void setup(int node,int l,int r)
    {
        t[node]=0;
        if(l==r)
        {
            t2[node]--;
            if(t2[node]<=0)t2[node]=inf;
            f[l]=node;
            return;
        }
        ff(node);
        int mid=l+r>>1;
        setup(node<<1,l,mid);
        setup(node<<1|1,mid+1,r);
        t2[node]=min(t2[node<<1],t2[node<<1|1]);
    }
    void ff2(int x)
    {
        for(int i=x*2; i<=x*2+1; i++)
            t[i]+=t[x],
                  t2[i]-=t[x];
        t[x]=0;
    }
    void upd_out2(int node,int l,int r)
    {
        if(t2[node]!=0)return;
        if(l==r)
        {
            t2[node]=inf;
            c[vitri[l]]=0;
            if(b[vitri[l]]==1) s.push(vitri[l]);
            return;
        }
        ff2(node);
        int mid=l+r>>1;
        upd_out2(node<<1,l,mid);
        upd_out2(node<<1|1,mid+1,r);
        t2[node]=min(t2[node<<1],t2[node<<1|1]);
    }
    void upd_out(int node,int l,int r,int l1,int r1)
    {
        if(l>r1||r<l1) return;
        if(l>=l1&&r<=r1)
        {
            t2[node]--;
            t[node]++;
            if(t2[node]==0)ff2(node),upd_out2(node,l,r);
            return;
        }
        ff2(node);
        int mid=l+r>>1;
        upd_out(node<<1,l,mid,l1,r1);
        upd_out(node<<1|1,mid+1,r,l1,r1);
        t2[node]=min(t2[node<<1],t2[node<<1|1]);
    }
    int get_hld(int x,int y,int z)
    {
        if(pos[head[x]]<=pos[y]) return get(1,1,n,pos[y],pos[x],z);
        return get(1,1,n,pos[head[x]],pos[x],z)+get_hld(st[0][head[x]],y,z);
    }
    int get_namgiua(int x,int y,int z)
    {
        if(depth[x]>depth[y]) swap(x,y);
        s2=lca(x,y);
        s3=lca2(y,s2);
        return get_hld(x,s2,z)+get_hld(y,s3,z);
    }
    void ou(int x,int y)
    {
        if(pos[head[x]]<=pos[y])  upd_out(1,1,n,pos[y],pos[x]);
        else    upd_out(1,1,n,pos[head[x]],pos[x]),ou(st[0][head[x]],y);
    }
    void upd_out_out(int x,int y)
    {
        if(depth[x]>depth[y]) swap(x,y);
        s2=lca(x,y);
        s3=lca2(y,s2);
        ou(x,s2);
        ou(y,s3);
    }
    void upd_out_in(int x)
    {
        x=f[pos[x]];
        while(x!=0)
        {
            for(auto f:v2[x])
            {
                b[f]--;
                if(b[f]==1&&c[f]==0)s.push(f);
            }
            x/=2;
        }
    }
} stt;
void out(int x)
{
    stt.upd_out_out(a[x].a,a[x].b);
    stt.upd_out_in(a[x].a);
}
void phongbeo()
{
    cin>>n;
    /// cach 1
    dem=0;
    for(int i=1; i<=n; i++)
        v[i].clear(),b[i]=0,c[i]=0,f[i]=0,heavy[i]=0,pos[i]=0,head[i]=0,depth[i]=0,vitri[i]=0;
    for(int i=1; i<=n*4; i++)
        v2[i].clear(),stt.t[i]=0,stt.t2[i]=0;
    for(int i=1; i<n; i++)
        cin>>l>>r,v[l].pb(r),v[r].pb(l);
    dfs(1,0);
    des(1,0);
    for(int i=1; i<17; i++)
        for(int j=1; j<=n; j++)
            st[i][j]=st[i-1][st[i-1][j]];

    cin>>m;
    for(int i=1; i<=m; i++)
        cin>>a[i].a>>a[i].b,stt.upd_in(1,1,n,pos[a[i].a],pos[a[i].a]);
//       cout<<1;
    for(int i=1; i<=m; i++)
        b[i]=stt.get_namgiua(a[i].a,a[i].b,i);
    for(int i=1; i<=m; i++)
    {
        c[i]=stt.get2(1,1,n,pos[a[i].b],pos[a[i].b])-1;
        vitri[pos[a[i].b]]=i;
        if(b[i]==1&&c[i]==0)
        {
            s.push(i);
        }
    }
    b[0]=inf;
    stt.setup(1,1,n);
    dem4=0;
    while(!s.empty())
    {
        int  x=s.top();
        s.pop();
        out(x);
        dem4++;
    }
    if(dem4!=m) cout<<"No";
    else cout<<"Yes";
}

/**
7
1 2
2 3
3 4
4 5
3 6
6 7
2
4 1
5 7
*/

Compilation message

jail.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main()
      | ^~~~
jail.cpp: In member function 'void IT::upd_in(int, int, int, int, int)':
jail.cpp:148:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  148 |         int mid=l+r>>1;
      |                 ~^~
jail.cpp: In member function 'int IT::get(int, int, int, int, int, int)':
jail.cpp:163:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  163 |         int mid=l+r>>1;
      |                 ~^~
jail.cpp: In member function 'int IT::get2(int, int, int, int, int)':
jail.cpp:171:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  171 |         int mid=l+r>>1;
      |                 ~^~
jail.cpp: In member function 'void IT::setup(int, int, int)':
jail.cpp:186:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  186 |         int mid=l+r>>1;
      |                 ~^~
jail.cpp: In member function 'void IT::upd_out2(int, int, int)':
jail.cpp:209:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  209 |         int mid=l+r>>1;
      |                 ~^~
jail.cpp: In member function 'void IT::upd_out(int, int, int, int, int)':
jail.cpp:225:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  225 |         int mid=l+r>>1;
      |                 ~^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24920 KB Output is correct
2 Correct 5 ms 22876 KB Output is correct
3 Correct 4 ms 22876 KB Output is correct
4 Correct 11 ms 23156 KB Output is correct
5 Correct 19 ms 23132 KB Output is correct
6 Correct 5 ms 23132 KB Output is correct
7 Correct 5 ms 23132 KB Output is correct
8 Correct 6 ms 23132 KB Output is correct
9 Correct 33 ms 25300 KB Output is correct
10 Correct 54 ms 57172 KB Output is correct
11 Correct 9 ms 22876 KB Output is correct
12 Correct 44 ms 25184 KB Output is correct
13 Incorrect 103 ms 63828 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Correct 4 ms 22968 KB Output is correct
3 Correct 5 ms 23132 KB Output is correct
4 Correct 6 ms 23132 KB Output is correct
5 Correct 5 ms 23132 KB Output is correct
6 Correct 5 ms 23132 KB Output is correct
7 Correct 6 ms 23132 KB Output is correct
8 Correct 6 ms 25180 KB Output is correct
9 Correct 5 ms 22996 KB Output is correct
10 Correct 6 ms 23128 KB Output is correct
11 Correct 6 ms 25180 KB Output is correct
12 Correct 5 ms 23048 KB Output is correct
13 Correct 5 ms 23128 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Correct 4 ms 22968 KB Output is correct
3 Correct 5 ms 23132 KB Output is correct
4 Correct 6 ms 23132 KB Output is correct
5 Correct 5 ms 23132 KB Output is correct
6 Correct 5 ms 23132 KB Output is correct
7 Correct 6 ms 23132 KB Output is correct
8 Correct 6 ms 25180 KB Output is correct
9 Correct 5 ms 22996 KB Output is correct
10 Correct 6 ms 23128 KB Output is correct
11 Correct 6 ms 25180 KB Output is correct
12 Correct 5 ms 23048 KB Output is correct
13 Correct 5 ms 23128 KB Output is correct
14 Correct 5 ms 26968 KB Output is correct
15 Correct 5 ms 22876 KB Output is correct
16 Correct 7 ms 22980 KB Output is correct
17 Correct 6 ms 25092 KB Output is correct
18 Correct 6 ms 23132 KB Output is correct
19 Correct 5 ms 22876 KB Output is correct
20 Correct 6 ms 23132 KB Output is correct
21 Correct 6 ms 23212 KB Output is correct
22 Correct 5 ms 23132 KB Output is correct
23 Correct 5 ms 25176 KB Output is correct
24 Correct 5 ms 23132 KB Output is correct
25 Correct 6 ms 22992 KB Output is correct
26 Correct 6 ms 23132 KB Output is correct
27 Correct 5 ms 23132 KB Output is correct
28 Correct 5 ms 25152 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Correct 4 ms 22968 KB Output is correct
3 Correct 5 ms 23132 KB Output is correct
4 Correct 6 ms 23132 KB Output is correct
5 Correct 5 ms 23132 KB Output is correct
6 Correct 5 ms 23132 KB Output is correct
7 Correct 6 ms 23132 KB Output is correct
8 Correct 6 ms 25180 KB Output is correct
9 Correct 5 ms 22996 KB Output is correct
10 Correct 6 ms 23128 KB Output is correct
11 Correct 6 ms 25180 KB Output is correct
12 Correct 5 ms 23048 KB Output is correct
13 Correct 5 ms 23128 KB Output is correct
14 Correct 5 ms 26968 KB Output is correct
15 Correct 5 ms 22876 KB Output is correct
16 Correct 7 ms 22980 KB Output is correct
17 Correct 6 ms 25092 KB Output is correct
18 Correct 6 ms 23132 KB Output is correct
19 Correct 5 ms 22876 KB Output is correct
20 Correct 6 ms 23132 KB Output is correct
21 Correct 6 ms 23212 KB Output is correct
22 Correct 5 ms 23132 KB Output is correct
23 Correct 5 ms 25176 KB Output is correct
24 Correct 5 ms 23132 KB Output is correct
25 Correct 6 ms 22992 KB Output is correct
26 Correct 6 ms 23132 KB Output is correct
27 Correct 5 ms 23132 KB Output is correct
28 Correct 5 ms 25152 KB Output is correct
29 Correct 8 ms 25180 KB Output is correct
30 Correct 7 ms 23132 KB Output is correct
31 Correct 6 ms 27228 KB Output is correct
32 Correct 7 ms 25248 KB Output is correct
33 Correct 7 ms 27228 KB Output is correct
34 Correct 7 ms 23132 KB Output is correct
35 Correct 6 ms 23052 KB Output is correct
36 Correct 7 ms 23132 KB Output is correct
37 Correct 6 ms 23132 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Correct 4 ms 22968 KB Output is correct
3 Correct 5 ms 23132 KB Output is correct
4 Correct 6 ms 23132 KB Output is correct
5 Correct 5 ms 23132 KB Output is correct
6 Correct 5 ms 23132 KB Output is correct
7 Correct 6 ms 23132 KB Output is correct
8 Correct 6 ms 25180 KB Output is correct
9 Correct 5 ms 22996 KB Output is correct
10 Correct 6 ms 23128 KB Output is correct
11 Correct 6 ms 25180 KB Output is correct
12 Correct 5 ms 23048 KB Output is correct
13 Correct 5 ms 23128 KB Output is correct
14 Correct 5 ms 26968 KB Output is correct
15 Correct 5 ms 22876 KB Output is correct
16 Correct 7 ms 22980 KB Output is correct
17 Correct 6 ms 25092 KB Output is correct
18 Correct 6 ms 23132 KB Output is correct
19 Correct 5 ms 22876 KB Output is correct
20 Correct 6 ms 23132 KB Output is correct
21 Correct 6 ms 23212 KB Output is correct
22 Correct 5 ms 23132 KB Output is correct
23 Correct 5 ms 25176 KB Output is correct
24 Correct 5 ms 23132 KB Output is correct
25 Correct 6 ms 22992 KB Output is correct
26 Correct 6 ms 23132 KB Output is correct
27 Correct 5 ms 23132 KB Output is correct
28 Correct 5 ms 25152 KB Output is correct
29 Correct 8 ms 25180 KB Output is correct
30 Correct 7 ms 23132 KB Output is correct
31 Correct 6 ms 27228 KB Output is correct
32 Correct 7 ms 25248 KB Output is correct
33 Correct 7 ms 27228 KB Output is correct
34 Correct 7 ms 23132 KB Output is correct
35 Correct 6 ms 23052 KB Output is correct
36 Correct 7 ms 23132 KB Output is correct
37 Correct 6 ms 23132 KB Output is correct
38 Correct 33 ms 28496 KB Output is correct
39 Correct 50 ms 58708 KB Output is correct
40 Correct 45 ms 25744 KB Output is correct
41 Correct 48 ms 27472 KB Output is correct
42 Correct 33 ms 25944 KB Output is correct
43 Correct 25 ms 25432 KB Output is correct
44 Correct 18 ms 23644 KB Output is correct
45 Correct 46 ms 36332 KB Output is correct
46 Correct 55 ms 36200 KB Output is correct
47 Correct 45 ms 47444 KB Output is correct
48 Correct 38 ms 47436 KB Output is correct
49 Correct 39 ms 36692 KB Output is correct
50 Correct 42 ms 36692 KB Output is correct
51 Correct 42 ms 40160 KB Output is correct
52 Correct 35 ms 39772 KB Output is correct
53 Correct 19 ms 26200 KB Output is correct
54 Correct 45 ms 36336 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 5 ms 24924 KB Output is correct
3 Correct 4 ms 22876 KB Output is correct
4 Correct 4 ms 22876 KB Output is correct
5 Correct 12 ms 25012 KB Output is correct
6 Correct 7 ms 23132 KB Output is correct
7 Correct 5 ms 22972 KB Output is correct
8 Correct 5 ms 22876 KB Output is correct
9 Correct 5 ms 24924 KB Output is correct
10 Correct 5 ms 23132 KB Output is correct
11 Correct 4 ms 22872 KB Output is correct
12 Correct 6 ms 23192 KB Output is correct
13 Correct 24 ms 25692 KB Output is correct
14 Correct 46 ms 25940 KB Output is correct
15 Correct 33 ms 25692 KB Output is correct
16 Correct 87 ms 37744 KB Output is correct
17 Correct 191 ms 43176 KB Output is correct
18 Correct 308 ms 47948 KB Output is correct
19 Incorrect 132 ms 39296 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24920 KB Output is correct
2 Correct 5 ms 22876 KB Output is correct
3 Correct 4 ms 22876 KB Output is correct
4 Correct 11 ms 23156 KB Output is correct
5 Correct 19 ms 23132 KB Output is correct
6 Correct 5 ms 23132 KB Output is correct
7 Correct 5 ms 23132 KB Output is correct
8 Correct 6 ms 23132 KB Output is correct
9 Correct 33 ms 25300 KB Output is correct
10 Correct 54 ms 57172 KB Output is correct
11 Correct 9 ms 22876 KB Output is correct
12 Correct 44 ms 25184 KB Output is correct
13 Incorrect 103 ms 63828 KB Output isn't correct
14 Halted 0 ms 0 KB -