oj.uz

Submission #1086330

# Submission time Handle Problem Language Result Execution time Memory
1086330 2024-09-10T07:52:09 Z modwwe Synchronization (JOI13_synchronization) C++17
100 / 100
 149 ms 19792 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);

            for(int i=s9-1; i>=0; --i)
                if(fen.get(tin[l])-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;
            for(int i=s9-1; i>=0; --i)
                if(fen.get(tin[l])-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;
            for(int i=s9-1; i>=0; --i)
                if(fen.get(tin[l])-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 2648 KB Output is correct
2 Correct 3 ms 2648 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 2712 KB Output is correct
7 Correct 7 ms 3676 KB Output is correct
8 Correct 6 ms 3676 KB Output is correct
9 Correct 7 ms 3676 KB Output is correct
10 Correct 79 ms 11604 KB Output is correct
11 Correct 105 ms 11700 KB Output is correct
12 Correct 131 ms 19032 KB Output is correct
13 Correct 39 ms 10452 KB Output is correct
14 Correct 58 ms 11488 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 17012 KB Output is correct
2 Correct 45 ms 16980 KB Output is correct
3 Correct 61 ms 19028 KB Output is correct
4 Correct 56 ms 18808 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2680 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 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 14 ms 4428 KB Output is correct
8 Correct 140 ms 19200 KB Output is correct
9 Correct 149 ms 19204 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 19280 KB Output is correct
2 Correct 86 ms 19540 KB Output is correct
3 Correct 86 ms 19792 KB Output is correct
4 Correct 95 ms 19688 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 8 ms 3764 KB Output is correct
7 Correct 100 ms 11860 KB Output is correct
8 Correct 140 ms 19284 KB Output is correct
9 Correct 41 ms 10952 KB Output is correct
10 Correct 63 ms 12372 KB Output is correct
11 Correct 57 ms 17744 KB Output is correct
12 Correct 70 ms 17748 KB Output is correct
13 Correct 76 ms 19792 KB Output is correct