Submission #1161144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161144		ace5	Tourism (JOI23_tourism)	C++20	28 / 100	5095 ms	19152 KiB

tourism

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const int maxlog = 17;
const int sqr = 317;

vector<int> g[maxn];
int la[maxlog][maxn];
int tin[maxn],tout[maxn];
int dep[maxn];
int lv[maxn];
int times = 0;
int ans = 0;
multiset<pair<int,int>> vert;
int L = 0,R = -1;

void dfs(int v,int p,int d)
{
    tin[v] = times++;
    for(int j = 0;j < maxlog;++j)
    {
        la[j][v] = (j == 0 ? p : la[j-1][la[j-1][v]]);
    }
    dep[v] = d;
    for(auto u:g[v])
    {
        if(u != p)
            dfs(u,v,d+1);
    }
    tout[v] = times;
}
bool isP(int u,int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u,int v)
{
    for(int j = maxlog-1;j >= 0;--j)
    {
        if(!isP(la[j][u],v))
            u = la[j][u];
    }
    if(!isP(u,v))
        u = la[0][u];
    return u;
}
int dist(int u,int v)
{
    return dep[u] + dep[v] - 2 * dep[lca(u,v)];
}
void add(int u)
{
    auto it = vert.insert({tin[u],u});
    if(vert.size() == 1)
    {
        return ;
    }
    auto prev = it;
    if(it == vert.begin())
        prev = --vert.end();
    else
        prev--;
    auto nxt = ++it;
    if(nxt == vert.end())
        nxt = vert.begin();
    int v1 = (*prev).second;
    int v2 = (*nxt).second;
    //cout << u << ' ' << v1 << ' ' << v2 << endl;
    ans -= dist(v1,v2);
    ans += dist(v1,u);
    ans += dist(v2,u);
  //  cout << ans << endl;
}
void del(int u)
{
    auto it = vert.find({tin[u],u});
    assert(it != vert.end());
    if(vert.size() == 1)
    {
        vert.erase(it);
        return ;
    }
    auto prev = it;
    if(it == vert.begin())
        prev = --vert.end();
    else
        prev--;
    auto nxt = it;
    nxt++;
    if(nxt == vert.end())
        nxt = vert.begin();
    int v1 = (*prev).second;
    int v2 = (*nxt).second;
    ans += dist(v1,v2);
    ans -= dist(v1,u);
    ans -= dist(v2,u);
    vert.erase(it);
}
struct que
{
    que(int _l,int _r,int _i){l = _l;r = _r;i = _i;};
    que(){};
    int l,r,i;
    bool operator < (const que & oth) {return (l/sqr != oth.l/sqr ? l < oth.l : r < oth.r);};
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m,q;
    cin >> n >> m >> q;
    for(int i = 0;i < n-1;++i)
    {
        int u,v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(0,0,0);
    for(int j = 0;j < m;++j)
    {
        cin >> lv[j];
        lv[j]--;
    }
    vector<que> queries;
    for(int j = 0;j < q;++j)
    {
        int l,r;
        cin >> l >> r;
        l--;
        r--;
        queries.push_back(que(l,r,j));
    }
    sort(queries.begin(),queries.end());
    int res[q];
    for(int j = 0;j < q;++j)
    {
        int l = queries[j].l,r = queries[j].r;
       // cout << l << ' ' << r << endl;
        while(L > l)
            add(lv[--L]);
        while(R < r)
            add(lv[++R]);
        //cout << "!" << endl;
        while(L < l)
            del(lv[L++]);
        while(R > r)
            del(lv[R--]);
        //cout << "?" << endl;
        //cout << ans << endl;
        res[queries[j].i] = ans/2+1;
    }
    for(int j = 0;j < q;++j)
        cout << res[j] << "\n";
}

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