oj.uz

Submission #1086325

# Submission time Handle Problem Language Result Execution time Memory
1086325 2024-09-10T07:47:38 Z modwwe Synchronization (JOI13_synchronization) C++17
100 / 100
 166 ms 22120 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()
{
    cin>>n>>m>>k;
    for(int i=1; i<n; i++)
        cin>>l>>r,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--)
    {
        cin>>l;
        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++)
    {
        cin>>l;
        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]);
            fen.upd(tin[l],ou[l]+1,-1);
        }
        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 2908 KB Output is correct
2 Correct 2 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2816 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 10 ms 4360 KB Output is correct
8 Correct 9 ms 4432 KB Output is correct
9 Correct 11 ms 4188 KB Output is correct
10 Correct 113 ms 18168 KB Output is correct
11 Correct 114 ms 18212 KB Output is correct
12 Correct 135 ms 21328 KB Output is correct
13 Correct 72 ms 18140 KB Output is correct
14 Correct 71 ms 17488 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 19284 KB Output is correct
2 Correct 57 ms 19280 KB Output is correct
3 Correct 64 ms 20728 KB Output is correct
4 Correct 64 ms 20560 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 2908 KB Output is correct
3 Correct 2 ms 2908 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 2820 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 12 ms 4700 KB Output is correct
8 Correct 161 ms 22120 KB Output is correct
9 Correct 166 ms 22052 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 22100 KB Output is correct
2 Correct 100 ms 21840 KB Output is correct
3 Correct 108 ms 22024 KB Output is correct
4 Correct 97 ms 22096 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 12 ms 4444 KB Output is correct
7 Correct 141 ms 19028 KB Output is correct
8 Correct 158 ms 22052 KB Output is correct
9 Correct 90 ms 19228 KB Output is correct
10 Correct 111 ms 18768 KB Output is correct
11 Correct 89 ms 20820 KB Output is correct
12 Correct 87 ms 20880 KB Output is correct
13 Correct 93 ms 21984 KB Output is correct