oj.uz

Submission #88165

# Submission time Handle Problem Language Result Execution time Memory
88165 2018-12-04T07:42:30 Z Bodo171 Synchronization (JOI13_synchronization) C++14
100 / 100
 963 ms 21708 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=16;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);
    ios_base::sync_with_stdio(false);
    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 4 ms 2808 KB Output is correct
2 Correct 4 ms 2932 KB Output is correct
3 Correct 5 ms 2932 KB Output is correct
4 Correct 4 ms 2932 KB Output is correct
5 Correct 3 ms 2976 KB Output is correct
6 Correct 5 ms 3232 KB Output is correct
7 Correct 21 ms 4404 KB Output is correct
8 Correct 22 ms 4540 KB Output is correct
9 Correct 21 ms 4540 KB Output is correct
10 Correct 365 ms 16964 KB Output is correct
11 Correct 455 ms 16976 KB Output is correct
12 Correct 890 ms 21340 KB Output is correct
13 Correct 235 ms 21340 KB Output is correct
14 Correct 277 ms 21340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 21340 KB Output is correct
2 Correct 126 ms 21340 KB Output is correct
3 Correct 170 ms 21340 KB Output is correct
4 Correct 183 ms 21340 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21340 KB Output is correct
2 Correct 4 ms 21340 KB Output is correct
3 Correct 5 ms 21340 KB Output is correct
4 Correct 5 ms 21340 KB Output is correct
5 Correct 5 ms 21340 KB Output is correct
6 Correct 7 ms 21340 KB Output is correct
7 Correct 45 ms 21340 KB Output is correct
8 Correct 818 ms 21616 KB Output is correct
9 Correct 846 ms 21676 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 963 ms 21676 KB Output is correct
2 Correct 345 ms 21676 KB Output is correct
3 Correct 350 ms 21676 KB Output is correct
4 Correct 343 ms 21676 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21676 KB Output is correct
2 Correct 4 ms 21676 KB Output is correct
3 Correct 5 ms 21676 KB Output is correct
4 Correct 5 ms 21676 KB Output is correct
5 Correct 7 ms 21676 KB Output is correct
6 Correct 41 ms 21676 KB Output is correct
7 Correct 525 ms 21676 KB Output is correct
8 Correct 820 ms 21708 KB Output is correct
9 Correct 355 ms 21708 KB Output is correct
10 Correct 368 ms 21708 KB Output is correct
11 Correct 299 ms 21708 KB Output is correct
12 Correct 301 ms 21708 KB Output is correct
13 Correct 340 ms 21708 KB Output is correct