oj.uz

Submission #1091743

# Submission time Handle Problem Language Result Execution time Memory
1091743 2024-09-22T02:28:56 Z DucNguyen2007 Tourism (JOI23_tourism) C++14
0 / 100
 5000 ms 13744 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=1e5+5,LG=__lg(maxN)+1,BLOCK=321;
const ll inf=2e18;
int n,m,q,h[maxN+1],up[maxN+1][LG+1],num[maxN+1],timer=0,sl=0,a[maxN+1],tour[maxN+1];
vector<int> adj[maxN+1];
void dfs(ll u)
{
    tour[++timer]=u;
    num[u]=timer;
    for(auto v:adj[u])
    {
        if(v==up[u][0])
        {
            continue;
        }
        h[v]=h[u]+1;
        up[v][0]=u;
        for(int j=1;j<=LG;j++)
        {
            up[v][j]=up[up[v][j-1]][j-1];
        }
        dfs(v);
    }
}
int lca(int u,int v)
{
    if(h[u]<h[v])
    {
        swap(u,v);
    }
    for(int j=LG;j>=0;j--)
    {
        if(h[up[u][j]]>=h[v])
        {
            u=up[u][j];
        }
    }
    for(int j=LG;j>=0;j--)
    {
        if(up[u][j]!=up[v][j])
        {
            u=up[u][j];
            v=up[v][j];
        }
    }
    if(u==v)
    {
        return u;
    }
    else return up[u][0];
}
int dist(int u,int v)
{
    int p=lca(u,v);
    return h[u]+h[v]-2*h[p];
}
struct fenwick
{
    int bit[maxN+1];
    fenwick()
    {
        memset(bit,0,sizeof(bit));
    }
    void update(int u,int val)
    {
        for(int i=u;i<=n;i+=(i&(-i)))
        {
            bit[i]+=val;
        }
    }
    int get(int u)
    {
        int ans=0;
        for(int i=u;i>0;i-=(i&(-i)))
        {
            ans+=bit[i];
        }
        return ans;
    }
    int get_first()
    {
        int i=0;
        for(int j=LG;j>=0;j--)
        {
            if(i+(1LL<<j)<n&&get(i+(1LL<<j))==0)
            {
                i+=(1LL<<j);
            }
        }
        return i+1;
    }
    int get_last()
    {
        int i=n+1;
        for(int j=LG;j>=0;j--)
        {
            if(i-(1LL<<j)>1&&get(n)-get(i-(1LL<<j)-1)==0)
            {
                i-=(1LL<<j);
            }
        }
        return i-1;
    }
    int lower(int u)
    {
        int pos=num[u],i=0;
        int tmp=get(pos);
        for(int j=LG;j>=0;j--)
        {
            if(i+(1LL<<j)<pos&&tmp-get(i+(1LL<<j)-1)>0)
            {
                i+=(1LL<<j);
            }
        }
        if(i==0)
        {
            return get_last();
        }
        return i;
    }
    int upper(int u)
    {
        int pos=num[u],i=n+1;
        int tmp=get(pos);
        for(int j=LG;j>=0;j--)
        {
            if(i-(1LL<<j)>pos&&get(i+(1LL<<j))-tmp>0)
            {
                i-=(1LL<<j);
            }
        }
        if(i==n+1)
        {
            return get_first();
        }
        return i;
    }
}f;
void add(int u)
{
    if(f.get(n)==0)
    {
        f.update(num[u],1);
        return;
    }
    int l=tour[f.lower(u)],r=tour[f.upper(u)];
    sl-=dist(l,r);
    sl+=(dist(l,u)+dist(u,r));
    //cout<<l<<" "<<r<<" "<<sl<<'\n';
    f.update(num[u],1);
}
void del(int u)
{
    if(f.get(n)==1)
    {
        f.update(num[u],-1);
        return;
    }
    int l=f.lower(u),r=f.upper(u);
    sl+=dist(l,r);
    sl-=(dist(l,u)+dist(u,r));
    f.update(num[u],-1);
}
struct query
{
    int l,r,id;
}p[maxN+1];
int ans[maxN+1],cnt[maxN+1];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    h[1]=1;
    dfs(1);
    for(int i=1;i<=m;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=q;i++)
    {
        cin>>p[i].l>>p[i].r;
        p[i].id=i;
    }
    sort(p+1,p+q+1,[&](query x,query y)
    {
        if(x.r/BLOCK==y.r/BLOCK)
        {
            return x.l<y.l;
        }
        return x.r/BLOCK<y.r/BLOCK;
    });
    int lc=1,rc=0;
    for(int i=1;i<=q;i++)
    {
        int l=p[i].l,r=p[i].r,id=p[i].id;
        while(rc<r)
        {
            rc++;
            if(!cnt[a[rc]])
            {
                add(a[rc]);
            }
            cnt[a[rc]]++;
        }
        while(lc>l)
        {
            lc--;
            if(!cnt[a[lc]])
            {
                add(a[lc]);
            }
            cnt[a[lc]]++;
        }
        while(rc>r)
        {
            cnt[a[rc]]--;
            if(!cnt[a[rc]])
            {
                del(a[rc]);
            }
            rc--;
        }
        while(lc<l)
        {
            cnt[a[lc]]--;
            if(!cnt[a[lc]])
            {
                del(a[lc]);
            }
            lc++;
        }
        ans[id]=sl/2;
    }
    for(int i=1;i<=q;i++)
    {
        cout<<ans[i]+1<<'\n';
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Incorrect 1 ms 3228 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Incorrect 1 ms 3228 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Incorrect 133 ms 10792 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3164 KB Output is correct
2 Correct 2 ms 3164 KB Output is correct
3 Correct 2 ms 3164 KB Output is correct
4 Execution timed out 5091 ms 13744 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Incorrect 1 ms 3228 KB Output isn't correct
3 Halted 0 ms 0 KB -