oj.uz

Submission #1091662

# Submission time Handle Problem Language Result Execution time Memory
1091662 2024-09-21T17:41:32 Z DucNguyen2007 Tourism (JOI23_tourism) C++14
0 / 100
 5000 ms 18332 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];
vector<int> adj[maxN+1];
struct cmp
{
    bool operator () (const int &x,const int &y)const
    {
        return num[x]<num[y];
    }
};
multiset<int,cmp> se;
void dfs(ll 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];
}
pii Find(int u)
{
    int l=0,r=0;
    if(se.find(u)!=se.end())
    {
        auto it=se.find(u);
        if(it==se.begin())
        {
            auto it1=se.rbegin();
            l=(*it1);
        }
        else
        {
            it--;
            l=(*it);
        }
        it=se.find(u);
        it++;
        if(it==se.end())
        {
            auto it1=se.begin();
            r=(*it1);
        }
        else r=(*it);
    }
    else
    {
        auto it1=se.lower_bound(u);
        if(it1==se.end())
        {
            auto it=se.begin();
            r=(*it);
        }
        else r=(*it1);
        if(it1!=se.begin())
        {
            it1--;
            l=(*it1);
        }
        else
        {
            auto it=se.rbegin();
            l=(*it);
        }
    }
    return {l,r};
}
void add(int u)
{
    if(se.empty())
    {
        se.insert(u);
        return;
    }
    pii tmp=Find(u);
    int l=tmp.fi,r=tmp.se;
    sl-=dist(l,r);
    sl+=(dist(l,u)+dist(u,r));
    se.insert(u);
}
void del(int u)
{
    if(se.size()==1)
    {
        se.erase(se.find(u));
        return;
    }
    pii tmp=Find(u);
    int l=tmp.fi,r=tmp.se;
    sl+=dist(l,r);
    sl-=(dist(l,u)+dist(u,r));
    se.erase(se.find(u));
}
struct query
{
    int l,r,id;
}p[maxN+1];
int ans[maxN+1];
int main()
{
    //freopen("TOURISM.INP","r",stdin);
    //freopen("TOURISM.OUT","w",stdout);
    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++;
            add(a[rc]);
        }
        while(lc>l)
        {
            lc--;
            add(a[lc]);
        }
        while(rc>r)
        {
            del(a[rc]);
            rc--;
        }
        while(lc<l)
        {
            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 2652 KB Output is correct
2 Correct 2 ms 2824 KB Output is correct
3 Incorrect 1 ms 2652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 11 ms 2840 KB Output is correct
3 Correct 105 ms 2924 KB Output is correct
4 Execution timed out 5022 ms 18332 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 11 ms 2652 KB Output is correct
3 Correct 105 ms 2908 KB Output is correct
4 Execution timed out 5061 ms 14592 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 2652 KB Output is correct
2 Correct 2 ms 2824 KB Output is correct
3 Incorrect 1 ms 2652 KB Output isn't correct
4 Halted 0 ms 0 KB -