oj.uz

Submission #1086333

# Submission time Handle Problem Language Result Execution time Memory
1086333 2024-09-10T07:55:04 Z modwwe Synchronization (JOI13_synchronization) C++17
100 / 100
 127 ms 19796 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;
#define getchar_unlocked getchar

inline int scan()
{
    char c = getchar_unlocked();
    int x = 0;
    while(c<'0'||c>'9')
    {
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar_unlocked();
    }
    return x;
}

void phongbeo();
const int inf=1e9;
const int mod2=1e9+9;
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,l2,r2,center;
int  i,s10,s12;
int kk;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
   // fin(task),fou(task);
#endif
    NHP
    /// cin>>s1;
///modwwe
    phongbeo();
//checktime
}
int st[17][100001];
int tin[100001];
int ou[100001];
int depth[100001];
bool c[100001];
bool b[100001];
int d[100001];
vector<int> v[100001];
ib a[100001];
int f[100001];
void dfs(int x,int y)
{
    st[0][x]=y;
    tin[x]=++dem;
    depth[x]=depth[y]+1;
    s9=max(s9,depth[x]);
    for(auto f:v[x])
        if(f!=y)
            dfs(f,x);
    ou[x]=dem;
}
struct fenwick
{
    int bit[100001];
    void upd(int x,int y,int z)
    {
        for(x; x<=n; x+=x&-x)
            bit[x]+=z;
        x=y;
        z=-z;
        for(x; x<=n; x+=x&-x)
            bit[x]+=z;
    }
    int get(int x)
    {
        int s=0;
        for(x; x; x-=x&-x) s+=bit[x];
        return s;
    }
} fen;
void phongbeo()
{
  n=scan();
  m=scan();
  k=scan();
    for(int i=1; i<n; i++)
        l=scan(),r=scan(),v[l].pb(r),v[r].pb(l),a[i]= {l,r};
    dfs(1,0);
        s9=log2(s9)+1;
    for(int i=1; i<s9; i++)
        for(int j=1; j<=n; j++)
            st[i][j]=st[i-1][st[i-1][j]];
    for(int i=1; i<n; i++)
        if(st[0][a[i].a]!=a[i].b) swap(a[i].a,a[i].b);
    while(m--)
    {
        l=scan();
        l=a[l].a;
        b[l]=1-b[l];
        if(b[l])
        {
            s2=l;
            fen.upd(tin[l],ou[l]+1,1);
            s8=fen.get(tin[l]);
            for(int i=s9-1; i>=0; --i)
                if(s8-fen.get(tin[st[i][s2]])==depth[l]-depth[st[i][s2]])
                    s2=st[i][s2];
            if(!c[l])
                d[s2]++,f[s2]++,c[l]=1;
            d[s2]+=f[l];
            f[s2]+=f[l];
            f[l]=0;

        }
        else
        {
            s2=l;
            s8=fen.get(tin[l]);
            for(int i=s9-1; i>=0; --i)
                if(s8-fen.get(tin[st[i][s2]])==depth[l]-depth[st[i][s2]])
                    s2=st[i][s2];
            fen.upd(tin[l],ou[l]+1,-1);
            d[l]=max(d[l],d[s2]);
        }
    }
    for(int i=1; i<=k; i++)
    {
       l=scan();
        if(b[l])
        {
            s2=l;
            s8=fen.get(tin[l]);
            for(int i=s9-1; i>=0; --i)
                if(s8-fen.get(tin[st[i][s2]])==depth[l]-depth[st[i][s2]])
                    s2=st[i][s2];
            d[l]=max(d[l],d[s2]);
        }
        cout<<d[l]+1,down
    }
}

Compilation message

synchronization.cpp:67:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   67 | main()
      | ^~~~
synchronization.cpp: In member function 'void fenwick::upd(int, int, int)':
synchronization.cpp:104:13: warning: statement has no effect [-Wunused-value]
  104 |         for(x; x<=n; x+=x&-x)
      |             ^
synchronization.cpp:108:13: warning: statement has no effect [-Wunused-value]
  108 |         for(x; x<=n; x+=x&-x)
      |             ^
synchronization.cpp: In member function 'int fenwick::get(int)':
synchronization.cpp:114:13: warning: statement has no effect [-Wunused-value]
  114 |         for(x; x; x-=x&-x) s+=bit[x];
      |             ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 3 ms 2652 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 6 ms 3676 KB Output is correct
8 Correct 6 ms 3680 KB Output is correct
9 Correct 6 ms 3676 KB Output is correct
10 Correct 68 ms 11540 KB Output is correct
11 Correct 69 ms 11684 KB Output is correct
12 Correct 101 ms 19032 KB Output is correct
13 Correct 31 ms 10448 KB Output is correct
14 Correct 47 ms 11608 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 16976 KB Output is correct
2 Correct 40 ms 16980 KB Output is correct
3 Correct 42 ms 19028 KB Output is correct
4 Correct 40 ms 18924 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 9 ms 4432 KB Output is correct
8 Correct 118 ms 19208 KB Output is correct
9 Correct 125 ms 19284 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 19284 KB Output is correct
2 Correct 69 ms 19536 KB Output is correct
3 Correct 66 ms 19792 KB Output is correct
4 Correct 63 ms 19624 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2876 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 8 ms 3676 KB Output is correct
7 Correct 81 ms 11956 KB Output is correct
8 Correct 118 ms 19188 KB Output is correct
9 Correct 37 ms 10952 KB Output is correct
10 Correct 53 ms 12368 KB Output is correct
11 Correct 44 ms 17748 KB Output is correct
12 Correct 44 ms 17748 KB Output is correct
13 Correct 65 ms 19796 KB Output is correct