제출 #850711

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
850711		danikoynov	Tourism (JOI23_tourism)	C++14	100 / 100	410 ms	49744 KiB

tourism

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e5 + 10;

struct query
{
    int l, r, idx;
} task[maxn];

int n, m, c[maxn], q;
vector < int > adj[maxn];

void input()
{
    cin >> n >> m >> q;
    for (int i = 1; i < n; i ++)
    {
        int v, u;
        cin >> v >> u;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }

    for (int i = 1; i <= m; i ++)
    {
        cin >> c[i];
    }

    for (int i = 1; i <= q; i ++)
    {
        cin >> task[i].l >> task[i].r;
        task[i].idx = i;
    }
}


int depth[maxn], tin[maxn], tout[maxn];
int occ[2 * maxn], rev[2 * maxn], timer;
int sub[maxn], heavy[maxn];

void euler(int v = 1, int p = - 1)
{
    occ[++ timer] = v;
    tin[v] = timer;
    rev[timer] = v;
    sub[v] = 1;
    heavy[v] = -1;
    for (int u : adj[v])
    {
        if (u == p)
            continue;
        depth[u] = depth[v] + 1;
        euler(u, v);
        if (heavy[v] == -1 || sub[u] > sub[heavy[v]])
            heavy[v] = u;
        sub[v] += sub[u];
        occ[++ timer] = v;
    }
    tout[v] = timer;
}

const int maxlog = 20;

int lg[2 * maxn], dp[maxlog][2 * maxn];

void sparse_table()
{
    for (int i = 1; i <= timer; i ++)
    {
        lg[i] = lg[i / 2] + 1;
        dp[0][i] = occ[i];
    }

    for (int j = 1; j < lg[timer]; j ++)
        for (int i = 1; i <= timer - (1 << j); i ++)
        {
            dp[j][i] = dp[j - 1][i + (1 << (j - 1))];
            if (depth[dp[j - 1][i]] < depth[dp[j][i]])
                dp[j][i] = dp[j - 1][i];
        }
}

int get_lca(int v, int u)
{
    int l = tin[v], r = tin[u];
    if (l > r)
        swap(l, r);
    int len = lg[r - l + 1] - 1;
    int lca = dp[len][r - (1 << len) + 1];
    if (depth[dp[len][l]] < depth[lca])
        lca = dp[len][l];
    return lca;
}

int get_distance(int v, int u)
{
    return depth[v] + depth[u] - 2 * depth[get_lca(v, u)];
}

struct interval
{
    int left, right, value;

    interval(int _left = 0, int _right = 0, int _value = 0)
    {
        left = _left;
        right = _right;
        value = _value;
    }
    bool operator < (const interval seg) const
    {
        if (left == seg.left)
        {
            if (value == seg.value)
                assert(right == seg.right);
            /// values cannot be the same
            return value > seg.value;

        }
        else
            return left < seg.left;
    }
};
struct chain
{
    int top, left, right;


    set < interval > act;
} st[maxn];

int ch_idx[maxn], ch_cnt, ord[maxn], last, ch_pos[maxn];

void hld(int v = 1, int p = -1)
{
    ///cout << v << " : " << p << endl;
    ch_idx[v] = ch_cnt;
    ord[++ last] = v;
    ch_pos[v] = last;
    st[ch_idx[v]].right = last;
    if (heavy[v] != -1)
        hld(heavy[v], v);
    for (int u : adj[v])
    {
        if (u == p || u == heavy[v])
            continue;
        ch_cnt ++;
        st[ch_cnt].top = v;
        st[ch_cnt].left = last + 1;
        st[ch_cnt].right = last + 1;
        hld(u, v);
    }
}

void decompose()
{
    ch_idx[1] = 1;
    ch_cnt = 1;
    ch_pos[1] = 1;
    st[ch_cnt].left = st[ch_cnt].right = 1;
    st[ch_cnt].top = 0;
    hld();

    /**cout << ch_cnt << endl;
    for (int i = 1; i <= ch_cnt; i ++)
        cout << st[i].left << " " << st[i].right << endl;
    for (int i = 1; i <= n; i ++)
    cout << ord[i] << " ";
    cout << endl;*/
}

int fen[maxn];

void update(int v, int val)
{
    for (int i = v; i <= m; i += (i & -i))
        fen[i] += val;
}

int query_sum(int v)
{
    int s = 0;
    for (int i = v; i > 0; i -= (i & -i))
        s += fen[i];
    return s;
}

int col[maxn];
void write_on_chain(int idx, int left, int right, int val)
{
    /**for (int i = left; i <= right; i ++)
    {
        if (col[i] != 0)
            update(col[i], - 1);
        col[i] = val;
    }*/
    ///update(val, right - left + 1);
    ///return;
    interval seg(left, right, val);


    st[idx].act.insert(seg);
    set < interval > :: iterator it, bef, aft;
    it = st[idx].act.find(seg);
    update(val, right - left + 1);
    ///cout << "write on chain " << val << " " << left << " " << right << endl;
    if (it != st[idx].act.begin())
    {
        bef = prev(it);

        if (bef -> right >= right)
        {
            update(bef -> value, - (right - left + 1));
            interval lf_split(bef -> left, left - 1, bef -> value);
            interval rf_split(right + 1, bef -> right, bef -> value);
            st[idx].act.erase(bef);
            if (lf_split.left <= lf_split.right)
                st[idx].act.insert(lf_split);
            if (rf_split.left <= rf_split.right)
                st[idx].act.insert(rf_split);
        }
        else if (bef -> right >= left)
        {

            update(bef -> value, - (bef -> right - left + 1));

            interval new_bef(bef -> left, left - 1, bef -> value);
            st[idx].act.erase(bef);
            if (new_bef.left <= new_bef.right)
                st[idx].act.insert(new_bef);
        }
    }

    while(true)
    {

        it = st[idx].act.find(seg);
        if (next(it) != st[idx].act.end())
        {
            aft = next(it);
            if (aft -> right <= right)
            {
                update(aft -> value, - (aft -> right - aft -> left + 1));
                st[idx].act.erase(aft);
                continue;
            }
            if (aft -> left <= right)
            {
                update(aft -> value, - (right - aft -> left + 1));
                interval new_aft(right + 1, aft -> right, aft -> value);
                st[idx].act.erase(aft);
                if (new_aft.left <= new_aft.right)
                    st[idx].act.insert(new_aft);
            }
            break;
        }
        else
            break;


    }

    /**if (idx != 25)
        return;
    cout << "writing " << idx << endl;
    cout << "add " << left << " " << right << endl;
        for (interval cur : st[idx].act)
    {

        cout << cur.left << " " << cur.right << " " << cur.value << endl;
    }
    for (interval cur : st[idx].act)
    {
        for (int j  = cur.left; j <= cur.right; j ++)
        {
            if (col[j] != cur.value)
            {
                cout <<" wtf " << endl;
                //exit(0);
            }
        }

    }*/
}

void write_on_path(int v, int p, int val)
{
    ///cout << "write on path " << v << " " << p << endl;
    while(ch_idx[v] != ch_idx[p])
    {
        write_on_chain(ch_idx[v], st[ch_idx[v]].left, ch_pos[v], val);
        v = st[ch_idx[v]].top;
    }


    if (ch_pos[p] < ch_pos[v])
        write_on_chain(ch_idx[v], ch_pos[p] + 1, ch_pos[v], val);

}


vector < query > ask[maxn];
int res[maxn];
void queries()
{

    ///q = 1;
    for (int i = 1; i <= q; i ++)
        ask[task[i].l].push_back(task[i]);

    for (int i = m; i > 0; i --)
    {
        if (i != m)
        {
            int v = c[i], u = c[i + 1];
            int lca = get_lca(v, u);
            write_on_path(v, lca, i);
            write_on_path(u, lca, i);
        }
        /**cout << "step " << i << endl;
        for (int j = 1; j <= m; j ++)
            cout << query_sum(j) - query_sum(j - 1) << " ";
        cout << endl;*/
        for (query cur : ask[i])
        {
            res[cur.idx] = query_sum(cur.r - 1) + 1;
        }
    }


    for (int i = 1; i <= q; i ++)
        cout << res[i] << endl;
}

void solve()
{
    input();
    euler();
    sparse_table();
    decompose();
    queries();

}

int main()
{
    ///freopen("test.txt", "r", stdin);
    speed();
    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