Submission #1261769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261769		Szymon_Pilipczuk	Tourism (JOI23_tourism)	C++20	100 / 100	1151 ms	34124 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
#define rep(a,b) for(int a = 0;a<b;a++)
const int inf = 1e9;
const ll infl = 1e18;
vector<int> gr[100000];
int pr[100000];
int rpr[100000];
int cpr = 0;
int ps[100000];
int cps = 0;
bool vis[100000];
int jp[100000][20];
int d[100000];
int c[100000];
void dfs(int v,int cd)
{
    vis[v] = true;
    pr[v] = cpr;
    rpr[cpr] = v;
    cpr++;
    d[v] = cd;
    for(int i : gr[v])
    {
        if(!vis[i])
        {
            jp[i][0] = v;
            dfs(i,cd+1);
        }
    }
    ps[v] = cps;
    cps++;
}
int lca(int a,int b)
{
    if(d[a] < d[b]) swap(a,b);
    for(int i = 19;i>=0;i--)
    {
        if(d[a] - (1<<i) >= d[b])
        {
            a = jp[a][i];
        }
    }
    for(int i = 19;i>=0;i--)
    {
        if(jp[a][i] != jp[b][i])
        {
            a = jp[a][i];
            b = jp[b][i];
        }
    }
    if(a==b)return a;
    return jp[a][0];
}
bool intr(int a,int b)
{
    return (pr[a] <= pr[b] && ps[a] >= ps[b]);
}
vector<pair<pair<int,int>,int>> cu;
vector<pair<pair<int,int>,int>> nx;
vector<pair<int,int>> cp;
vector<pair<int,int>> nxp;
int last;
int trize;
vector<int> tr;
int tans[100000];
void add(int p,int v)
{
    if(p >= inf) return;
    p+=trize;
    tr[p] += v;
    p/=2;
    while(p > 0)
    {
        tr[p] = tr[p*2] + tr[p*2+1];
        p/=2;
    }
}
int check(int l,int r)
{
    l+=trize;
    r+=trize;
    int ans = tr[l];
    if(l!=r)ans+=tr[r];
    while(l/2 != r/2)
    {
        if(l%2==0)ans+=tr[l+1];
        if(r%2==1)ans+=tr[r-1];
        l/=2;r/=2;
    }
    return ans;
}
void solve(int l,int r)
{
    if(l > r) return;
    unordered_map<int,int> conv;
    int ize = r-l+1;
    vector<int> vtr;
    int root = (l+r)/2;
    vector<pair<pair<int,int>,int>> cc;
    while(last < cu.size() && cu[last].st.st <= root)
    {
        if(cu[last].st.nd >= root)
        {
            cc.pb(cu[last]);
        }
        else
        {
            nx.pb(cu[last]);
        }
        last++;
    }
    unordered_set<int> used;
    for(int i = l;i<=r;i++)
    {
        if(!used.contains(c[i]))
        {
            vtr.pb(pr[c[i]]);
            used.insert(c[i]);
        }
    }
    sort(all(vtr));
    rep(i,vtr.size()-1)
    {
        int cv = lca(rpr[vtr[i]],rpr[vtr[i+1]]);
        //cerr<<cv<<"\n";
        if(!used.contains(cv))
        {
            vtr.pb(pr[cv]);
            used.insert(cv);
        }
    }
    //cerr<<"\n";
    sort(all(vtr));
    rep(i,vtr.size())
    {
        vtr[i] = rpr[vtr[i]];
        //cerr<<vtr[i]<<"\n";
        conv[vtr[i]] = i;
    }
    vector<pair<int,int>> o(vtr.size());
    o[0] = {-1,-1};
    for(int i = 1;i<vtr.size();i++)
    {
        int cv = i-1;
        while(!intr(vtr[cv],vtr[i]))
        {
            cv = o[cv].st;
        }
        o[i] = {cv,d[vtr[i]]-d[vtr[cv]]};
        //cerr<<o[i].st<<" "<<o[i].nd<<"\n";
    }
    int troot = conv[c[root]];
    int cw = troot;
    int prev = -1;
    int nxv = o[cw].st;
    int pv = -1;
    int nv = o[cw].nd;
    while(true)
    {
        o[cw] = {prev,pv};
        prev = cw;
        pv = nv;
        cw = nxv;
        if(cw == -1) break;
        nxv = o[cw].st;
        nv = o[cw].nd;
    }
    vector<pair<int,int>> kr(vtr.size(),{inf,inf});
    kr[troot] = {0,0};
    for(int i = root-1;i>=l;i--)
    {
        int cv = conv[c[i]];
        while(kr[cv].st == inf)
        {
            kr[cv].st = root-i;
            cv = o[cv].st;
        }
    }
    /*cerr<<"\n";
    for(int i = 0;i<vtr.size();i++)
    {
        cerr<<kr[i].st<<" "<<kr[i].nd<<"\n";
    }
    cerr<<"\n";*/
    vector<pair<pair<int,int>,int>> am;
    for(int i = root+1;i<=r;i++)
    {
        int cv = conv[c[i]];
        while(kr[cv].nd == inf)
        {
            kr[cv].nd = i-root;
            //am.pb({kr[cv],o[cv].nd});
            cv = o[cv].st;
        }
    }
    rep(i,vtr.size())
    {
        if(kr[i].st != 0)
        {
            am.pb({kr[i],o[i].nd});
        }
    }
    /*cerr<<"\n";
    for(int i = 0;i<vtr.size();i++)
    {
        cerr<<kr[i].st<<" "<<kr[i].nd<<" "<<o[i].nd<<"\n";
    }
    cerr<<"\n";*/
    sort(all(am));
    sort(all(cc));
    reverse(all(cc));
    tr.clear();
    trize = (r-root+1);
    tr.resize(2*trize);
    rep(i,am.size())
    {
        add(am[i].st.nd,am[i].nd);
        //cerr<<am[i].st.st<<" "<<am[i].st.nd<<" "<<am[i].nd<<"\n";
    }
    int ans = 0;
    int j = 0;
    rep(i,cc.size())
    {
        while(j < am.size() && root-cc[i].st.st >= am[j].st.st)
        {
            ans += am[j].nd;
            add(am[j].st.nd,-am[j].nd);
            j++;
        }
        //cerr<<ans<<" "<<check(0,cc[i].st.nd-root)<<" "<<root<<" "<<cc[i].nd<<"\n";
        tans[cc[i].nd] = ans + check(0,cc[i].st.nd-root) + 1;
    }
    nxp.pb({l,root-1});
    nxp.pb({root+1,r});
}
int main()
{
    int n,m,q;
    cin>>n>>m>>q;
    rep(i,n-1)
    {
        int a,b;
        cin>>a>>b;
        a--;b--;
        gr[a].pb(b);
        gr[b].pb(a);
    }
    dfs(0,0);
    jp[0][0] = 0;
    for(int i = 1;i<20;i++)
    {
        rep(j,n)
        {
            jp[j][i] = jp[jp[j][i-1]][i-1];
        }
    }
    rep(i,m)
    {
        cin>>c[i];
        c[i]--;
    }
    rep(i,q)
    {
        int a,b;
        cin>>a>>b;
        a--;b--;
        nx.pb({{a,b},i});
    }
    nxp.pb({0,m-1});
    sort(all(nx));
    while(!nx.empty())
    {
        cu = nx;
        last = 0;
        cp = nxp;
        nxp.clear();
        nx.clear();
        for(pair<int,int> i : cp)
        {
            solve(i.st,i.nd);
        }
        while(last < cu.size())
        {
            nx.pb(cu[last]);
            last++;
        }
    }
    rep(i,q)
    {
        cout<<tans[i]<<"\n";
    }

}

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