oj.uz

Submission #1086327

# Submission time Handle Problem Language Result Execution time Memory
1086327 2024-09-10T07:50:40 Z modwwe Synchronization (JOI13_synchronization) C++17
100 / 100
 155 ms 21172 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;
    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);
    for(int i=1; i<17; 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=16; 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=16; 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=16; 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:103:13: warning: statement has no effect [-Wunused-value]
  103 |         for(x; x<=n; x+=x&-x)
      |             ^
synchronization.cpp:107:13: warning: statement has no effect [-Wunused-value]
  107 |         for(x; x<=n; x+=x&-x)
      |             ^
synchronization.cpp: In member function 'int fenwick::get(int)':
synchronization.cpp:113:13: warning: statement has no effect [-Wunused-value]
  113 |         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 2904 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 2 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 9 ms 4188 KB Output is correct
8 Correct 9 ms 4440 KB Output is correct
9 Correct 8 ms 4432 KB Output is correct
10 Correct 97 ms 17248 KB Output is correct
11 Correct 103 ms 17184 KB Output is correct
12 Correct 124 ms 20308 KB Output is correct
13 Correct 63 ms 17400 KB Output is correct
14 Correct 58 ms 16976 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 18636 KB Output is correct
2 Correct 43 ms 18804 KB Output is correct
3 Correct 52 ms 20052 KB Output is correct
4 Correct 50 ms 20048 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2916 KB Output is correct
3 Correct 2 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 11 ms 4700 KB Output is correct
8 Correct 155 ms 21072 KB Output is correct
9 Correct 149 ms 21072 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 21076 KB Output is correct
2 Correct 83 ms 20800 KB Output is correct
3 Correct 81 ms 21072 KB Output is correct
4 Correct 78 ms 21064 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 2 ms 2908 KB Output is correct
3 Correct 2 ms 2908 KB Output is correct
4 Correct 2 ms 3160 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 11 ms 4476 KB Output is correct
7 Correct 131 ms 17872 KB Output is correct
8 Correct 152 ms 21172 KB Output is correct
9 Correct 102 ms 18376 KB Output is correct
10 Correct 80 ms 17776 KB Output is correct
11 Correct 97 ms 19736 KB Output is correct
12 Correct 60 ms 19704 KB Output is correct
13 Correct 85 ms 20992 KB Output is correct