Submission #1307110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307110		the_commando_x	Birthday gift (IZhO18_treearray)	C++17	100 / 100	594 ms	84452 KiB

treearray

// #pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;

using pii = pair<int, int>;
using vii = vector<pii>;
using vvii = vector<vii>;

using l = long long;
using vl = vector<l>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;

using pll = pair<l, l>;
using vll = vector<pll>;
using vvll = vector<vll>;

using d = double;
using vd = vector<d>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;

using ld = long double;
using vld = vector<ld>;
using vvld = vector<vld>;
using vvvld = vector<vvld>;

using vb = vector<bool>;
using vvb = vector<vb>;
using pbb = pair<bool, bool>;
using vbb = vector<pbb>;

#define ff first
#define ss second

#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

void setIO(string name = "")
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (!name.empty())
    {
        (void)freopen((name + ".in").c_str(), "r", stdin);
        (void)freopen((name + ".out").c_str(), "w", stdout);
    }
}

const ld pi = 3.14159265358979323846;

const l LINF = 1e18;
const l INF = 1e9;

const l MOD = 1e9 + 7;
// const l MOD = 998244353;

const l MAXN = 2e5 + 5;
const l LOG = 20;

int n, m, q;

vvi adj(MAXN);

vi a(MAXN);

vvi up(MAXN, vi(LOG));
vi depth(MAXN);

vector<set<int>> LCA(MAXN), POS(MAXN);

int timer = 0;

void dfs(int u = 1, int p = 0)
{
    up[u][0] = p;
    for (auto v : adj[u])
    {
        if (v == p)
            continue;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}

int lift(int u, int k)
{
    for (int i = 0; i < LOG; ++i)
        if (k & (1 << i))
            u = up[u][i];

    return u;
}

int lca(int a, int b)
{
    if (depth[a] < depth[b])
        swap(a, b);

    a = lift(a, depth[a] - depth[b]);

    if (a == b)
        return a;

    for (int i = LOG - 1; i >= 0; --i)
        if (up[a][i] != up[b][i])
            a = up[a][i], b = up[b][i];

    return up[a][0];
}

void solve()
{
    cin >> n >> m >> q;

    for (int i = 1; i <= n - 1; ++i)
    {
        int a, b;
        cin >> a >> b;

        adj[a].pb(b);
        adj[b].pb(a);
    }

    for (int i = 1; i <= m; ++i)
        cin >> a[i];

    dfs(1, 0);

    for (int k = 1; k < LOG; ++k)
        for (int i = 1; i <= n; ++i)
            up[i][k] = up[up[i][k - 1]][k - 1];

    for (int i = 1; i <= m; ++i)
        POS[a[i]].insert(i);

    for (int i = 1; i < m; ++i)
        LCA[lca(a[i], a[i + 1])].insert(i);

    auto query1 = [&](int i, int x)
    {
        POS[a[i]].erase(i);
        POS[x].insert(i);

        if (i > 1)
            LCA[lca(a[i - 1], a[i])].erase(i - 1), LCA[lca(a[i - 1], x)].insert(i - 1);
        if (i < m)
            LCA[lca(a[i], a[i + 1])].erase(i), LCA[lca(x, a[i + 1])].insert(i);

        a[i] = x;
    };

    auto query2 = [&](int left, int right, int x)
    {
        // segment size == 1
        auto pit = POS[x].lower_bound(left);
        if (pit != POS[x].end() && *pit <= right)
            return (void)(cout << *pit << " " << *pit << "\n");

        // segment size == 2
        auto it = LCA[x].lower_bound(left);

        if (it == LCA[x].end() || *it >= right)
            return (void)(cout << "-1 -1\n");

        int i = *it;

        return (void)(cout << i << " " << i + 1 << "\n");
    };

    while (q--)
    {
        int type;
        cin >> type;

        if (type == 1)
        {
            int pos, val;
            cin >> pos >> val;

            query1(pos, val);
        }
        else if (type == 2)
        {
            int left, right, val;
            cin >> left >> right >> val;

            query2(left, right, val);
        }
    }
}

int main()
{
    setIO("");

#ifndef ONLINE_JUDGE
    // setIO("filename");
#endif

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

/*
https://oj.uz/problem/view/IZhO18_treearray
IZHO 2018 F. Birthday gift
*/

Compilation message (stderr)

treearray.cpp: In function 'void setIO(std::string)':
treearray.cpp:53:22: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         (void)freopen((name + ".in").c_str(), "r", stdin);
      |               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:54:22: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         (void)freopen((name + ".out").c_str(), "w", stdout);
      |               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44