Submission #729020

#	Time	Username	Problem	Language	Result	Execution time	Memory
729020		MilosMilutinovic	Tourism (JOI23_tourism)	C++14	100 / 100	875 ms	24912 KiB

tourism

#include <bits/stdc++.h>
using namespace std;

int n,m,q,c[100005],sz[100005],dep[100005];
vector<int> g[100005];
vector<pair<int,int>> qs[100005];
int son[100005],head[100005],pos[100005],pv,pr[100005];
int ans[100005];

void dfs(int x,int fa)
{
    sz[x]=1;pr[x]=fa;
    dep[x]=dep[fa]+1;
    int mx=0;
    for(int y:g[x])
    {
        if(y==fa) continue;
        dfs(y,x);sz[x]+=sz[y];
        if(sz[y]>mx)mx=sz[y],son[x]=y;
    }
}
void build(int x,int fa,int c)
{
    head[x]=c;pos[x]=++pv;
    if(son[x])build(son[x],x,c);
    for(int y:g[x])
        if(y!=fa&&y!=son[x])
            build(y,x,y);
}

int fenw[100005];
void update(int x,int f)
{
    for(int i=x;i<=100000;i+=i&-i)fenw[i]+=f;
}
int query(int x)
{
    int f=0;
    for(int i=x;i>0;i-=i&-i)f+=fenw[i];
    return f;
}

set<tuple<int,int,int>> st;
void change(int a,int b,int c)
{
    if(a>b)swap(a,b);
    while(true)
    {
        auto it=st.lower_bound({a,-1,-1});
        if(it==st.end()||get<1>(*it)>b||get<0>(*it)<a) break;
        st.erase(it);
        int l=get<1>(*it),r=get<0>(*it),v=get<2>(*it);
        int len=min(r,b)-max(l,a)+1;
        update(v,-len);
        if(l<a) st.emplace(a-1,l,v);
        if(b<r) st.emplace(r,b+1,v);
    }
    st.emplace(b,a,c);
    update(c,b-a+1);
}
void update(int a,int b,int c)
{
    for(;head[a]!=head[b];b=pr[head[b]])
    {
        if(dep[head[a]]>dep[head[b]]) swap(a,b);
        change(pos[head[b]],pos[b],c);
    }
    change(pos[a],pos[b],c);
}

signed main()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<n;i++)
    {
        int a,b;scanf("%d%d",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1,1);
    build(1,1,1);
    for(int i=1;i<=m;i++) scanf("%d",&c[i]);
    for(int i=1;i<=q;i++)
    {
        int l,r;scanf("%d%d",&l,&r);
        qs[r].push_back({l,i});
    }
    for(int i=1;i<=m;i++)
    {
        if(i>1) update(c[i-1],c[i],i-1);
        for(auto&p:qs[i]) ans[p.second]=query(100000)-query(p.first-1);
    }
    for(int i=1;i<=q;i++) printf("%d\n",max(1,ans[i]));
}

Compilation message (stderr)

tourism.cpp: In function 'int main()':
tourism.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%d%d%d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
tourism.cpp:76:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         int a,b;scanf("%d%d",&a,&b);
      |                 ~~~~~^~~~~~~~~~~~~~
tourism.cpp:82:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     for(int i=1;i<=m;i++) scanf("%d",&c[i]);
      |                           ~~~~~^~~~~~~~~~~~
tourism.cpp:85:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         int l,r;scanf("%d%d",&l,&r);
      |                 ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41