oj.uz

Submission #88164

# Submission time Handle Problem Language Result Execution time Memory
88164 2018-12-04T07:39:39 Z Bodo171 Synchronization (JOI13_synchronization) C++14
100 / 100
 1259 ms 30420 KB 
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=100005;
vector<int> v[nmax];
int l[nmax],r[nmax],lev[nmax],aib[nmax],a[nmax],b[nmax],state[nmax],sub[nmax],old[nmax],know[nmax];
int tt[20][nmax];
int n,nr,m,q,i,j,x,y,L;
void dfs(int x)
{
    l[x]=++nr;
    for(int i=0;i<v[x].size();i++)
        if(!l[v[x][i]])
    {
        lev[v[x][i]]=lev[x]+1;
        tt[0][v[x][i]]=x;
        dfs(v[x][i]);
    }
    r[x]=nr;
}
inline int lbit(int x)
{
    return ((x^(x-1))&x);
}
void update(int poz,int val)
{
    for(int idx=poz;idx<=n;idx+=lbit(idx))
        aib[idx]+=val;
}
int compute(int poz)
{
    int ret=0;
    for(int idx=poz;idx>0;idx-=lbit(idx))
        ret+=aib[idx];
    return ret;
}
bool check(int x,int y)
{
    return (compute(l[y])-compute(l[x])==lev[y]-lev[x]);
}
int anc(int node)
{
    for(int p=17;p>=0;p--)
        if(tt[p][node]&&check(tt[p][node],node))
         node=tt[p][node];
    return node;
}
void bmw()
{
    for(i=1;i<=17;i++)
        for(j=1;j<=n;j++)
          tt[i][j]=tt[i-1][tt[i-1][j]];
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n>>m>>q;
    for(i=1;i<=n-1;i++)
    {
        cin>>x>>y;
        a[i]=x,b[i]=y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(i=1;i<=n;i++)
        know[i]=sub[i]=1;
    dfs(1);
    bmw();
    for(i=1;i<=m;i++)
    {
        cin>>nr;
        if(lev[a[nr]]<lev[b[nr]])
            swap(a[nr],b[nr]);
        x=a[nr];
        if(state[nr]==0)
        {
            update(l[x],1);update(r[x]+1,-1);
            L=anc(x);
            sub[L]+=(sub[x]-old[x]);
            know[L]+=(sub[x]-old[x]);
        }
        else
        {
            L=anc(x);
            update(l[x],-1);update(r[x]+1,1);
            know[x]=know[L];old[x]=sub[x];
        }
        state[nr]^=1;
    }
    for(i=1;i<=n;i++)
    {
        know[i]=know[anc(i)];
    }
    for(i=1;i<=q;i++)
    {
        cin>>x;
        cout<<know[x]<<'\n';
    }
    return 0;
}

Compilation message

synchronization.cpp: In function 'void dfs(int)':
synchronization.cpp:13:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 5 ms 2868 KB Output is correct
3 Correct 5 ms 2968 KB Output is correct
4 Correct 5 ms 3120 KB Output is correct
5 Correct 6 ms 3120 KB Output is correct
6 Correct 7 ms 3128 KB Output is correct
7 Correct 33 ms 4740 KB Output is correct
8 Correct 30 ms 4960 KB Output is correct
9 Correct 31 ms 4996 KB Output is correct
10 Correct 466 ms 20252 KB Output is correct
11 Correct 457 ms 22404 KB Output is correct
12 Correct 790 ms 29476 KB Output is correct
13 Correct 285 ms 29476 KB Output is correct
14 Correct 299 ms 29476 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 29476 KB Output is correct
2 Correct 207 ms 29476 KB Output is correct
3 Correct 245 ms 29604 KB Output is correct
4 Correct 242 ms 29660 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29660 KB Output is correct
2 Correct 4 ms 29660 KB Output is correct
3 Correct 4 ms 29660 KB Output is correct
4 Correct 5 ms 29660 KB Output is correct
5 Correct 5 ms 29660 KB Output is correct
6 Correct 10 ms 29660 KB Output is correct
7 Correct 60 ms 29660 KB Output is correct
8 Correct 1259 ms 30320 KB Output is correct
9 Correct 1211 ms 30320 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 980 ms 30320 KB Output is correct
2 Correct 447 ms 30320 KB Output is correct
3 Correct 450 ms 30320 KB Output is correct
4 Correct 448 ms 30420 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 30420 KB Output is correct
2 Correct 4 ms 30420 KB Output is correct
3 Correct 4 ms 30420 KB Output is correct
4 Correct 5 ms 30420 KB Output is correct
5 Correct 9 ms 30420 KB Output is correct
6 Correct 52 ms 30420 KB Output is correct
7 Correct 808 ms 30420 KB Output is correct
8 Correct 1235 ms 30420 KB Output is correct
9 Correct 560 ms 30420 KB Output is correct
10 Correct 591 ms 30420 KB Output is correct
11 Correct 432 ms 30420 KB Output is correct
12 Correct 421 ms 30420 KB Output is correct
13 Correct 457 ms 30420 KB Output is correct