Submission #1212118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212118		jerzyk	Tourism (JOI23_tourism)	C++20	100 / 100	649 ms	30304 KiB

tourism

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1'000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1'000'000'007LL;
const int K = 17;
const int N = 1<<K;
int rev[N], pre[N], pos[N], wys[N], cnt = 0;
int jp[N][K + 1];
vector<int> ed[N];

int tab[N];

int v1[N], v2[N];
pair<int, int> que[N];
int answer[N];

int drz[2 * N];

void DFS(int v)
{
    ++cnt; pre[v] = cnt; pos[v] = cnt;
    rev[cnt] = v;
    for(int i = 1; i <= K; ++i)
        jp[v][i] = jp[jp[v][i - 1]][i - 1];
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(jp[ed[v][i]][0]) continue;
        jp[ed[v][i]][0] = v;
        wys[ed[v][i]] = wys[v] + 1;
        DFS(ed[v][i]);
        pos[v] = pos[ed[v][i]];
    }
}

int LCA(int a, int b)
{
    if(pre[a] > pre[b]) swap(a, b);
    for(int i = K; i >= 0; --i)
        if(pos[jp[a][i]] < pre[b])
            a = jp[a][i];
    if(pos[a] < pre[b])
        a = jp[a][0];
    return a;
}

void Add(int v, int x)
{
    v += N;
    while(v > 0)
    {
        drz[v] += x;
        v /= 2;
    }
}

int Query(int a, int b)
{
    a += N - 1; b += N + 1;
    int ans = 0;
    while(a / 2 != b / 2)
    {
        if(a % 2 == 0)
            ans += drz[a + 1];
        if(b % 2 == 1)
            ans += drz[b - 1];
        a /= 2; b /= 2;
    }
    return ans;
}

vector<int> td;
vector<int> tv; int p1 = 0;
vector<pair<pair<int, int>, int>> dod;

void DFSD(int v)
{
    while(p1 < (int)tv.size() - 1 && pre[tv[p1 + 1]] <= pos[v])
    {
        ++p1;
        int ne = tv[p1];
        ed[v].pb(ne); ed[ne].pb(v);
        DFSD(ne);
    }
}

void DFSA(int v, int o)
{
    //cout << "D: " << v << " " << o << " | " << v1[v] << " " << v2[v] << "\n";
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(ed[v][i] == o) continue;
        int ne = ed[v][i];
        DFSA(ed[v][i], v);
        v1[v] = max(v1[v], v1[ne]);
        v2[v] = min(v2[v], v2[ne]);
    }
    if(o == v) return;
    int d = wys[v] - wys[o];
    if(d < 0) d *= -1;
    dod.pb(pair{pair{v1[v], v2[v]}, d});
}

void DC(int p, int k)
{
    if((int)td.size() == 0) return;
    int s = (p + k) / 2;
    vector<int> q1, q2, cur;
    vector<pair<pair<int, int>, int>> akt;
    //cout << "\nDC: " << p << " " << k << "\n"; 
    for(int i = 0; i < (int)td.size(); ++i)
    {
        if(que[td[i]].nd < s)
            {q1.pb(td[i]); continue;}
        if(que[td[i]].st > s)
            {q2.pb(td[i]); continue;}
        //cout << "Q: " << " " << td[i] << "\n";
        akt.pb(pair{que[td[i]], td[i]});
    }

    td.clear(); tv.clear(); dod.clear();

    sort(akt.begin(), akt.end());
    for(int i = p; i <= k; ++i)
        cur.pb(pre[tab[i]]);
    sort(cur.begin(), cur.end());
    for(int i = 0; i < k - p; ++i)
        cur.pb(pre[LCA(rev[cur[i]], rev[cur[i + 1]])]);
    sort(cur.begin(), cur.end());
    for(int i = 0; i < (int)cur.size(); ++i)
    {
        v1[rev[cur[i]]] = p - 1; v2[rev[cur[i]]] = k + 1;
        if(i == 0 || cur[i] != cur[i - 1])
            tv.pb(rev[cur[i]]);
    }
    for(int i = p; i < s; ++i)
        v1[tab[i]] = i;
    for(int i = k; i > s; --i)
        v2[tab[i]] = i;
    p1 = 0;

    //cout << "\nDFS:\n";
    DFSD(tv[0]);
    DFSA(tab[s], tab[s]);
    for(int i = 0; i < (int)tv.size(); ++i)
        ed[tv[i]].clear();
    sort(dod.begin(), dod.end());
    int j = -1, sum = 1;
    for(int i = 0; i < (int)dod.size(); ++i) sum += dod[i].nd;
    for(int i = 0; i < (int)akt.size(); ++i)
    {
        while(j < (int)dod.size() - 1 && dod[j + 1].st.st < akt[i].st.st)
        {
            ++j;
            Add(dod[j].st.nd, dod[j].nd);
            sum -= dod[j].nd;
        }
        answer[akt[i].nd] = sum + Query(1, akt[i].st.nd);
    }
    while(j >= 0)
    {
        Add(dod[j].st.nd, -dod[j].nd);
        --j;
    }

    td = q1;
    if(s > p)
        DC(p, s - 1);
    td = q2;
    if(s < k)
        DC(s + 1, k);
}

void Solve()
{
    int n, m, a, b, q;
    cin >> n >> m >> q;
    for(int i = 1; i < n; ++i)
    {
        cin >> a >> b;
        ed[a].pb(b); ed[b].pb(a);
    }
    jp[1][0] = 1;
    DFS(1);
    for(int i = 1; i <= n; ++i) ed[i].clear();
    for(int i = 1; i <= m; ++i)
        cin >> tab[i];
    vector<pair<int, int>> v;
    for(int i = 1; i <= q; ++i)
    {
        cin >> que[i].st >> que[i].nd;
        v.pb(pair{que[i].st, i});
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < q; ++i)
        td.pb(v[i].nd);
    DC(1, m);
    for(int i = 1; i <= q; ++i)
        cout << answer[i] << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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