Submission #93219

#	Time	Username	Problem	Language	Result	Execution time	Memory
93219		SamAnd	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1399 ms	86040 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;

int n, m, q;
vector<int> a[N];
int b[N];

int k = 20;
int p[N][22];
int tim;
int tin[N], tout[N];
void dfs(int x, int cp)
{
    tin[x] = tim++;
    p[x][0] = cp;
    for (int i = 1; i <= k; ++i)
    {
        p[x][i] = p[p[x][i - 1]][i - 1];
    }
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (h == cp)
            continue;
        dfs(h, x);
    }
    tout[x] = tim++;
}

bool par(int x, int y)
{
    return (tin[x] <= tin[y] && tout[x] >= tout[y]);
}

int lca(int x, int y)
{
    if (par(x, y))
        return x;
    if (par(y, x))
        return y;
    for (int i = k; i >= 0; --i)
    {
        if (!par(p[x][i], y))
            x = p[x][i];
    }
    return p[x][0];
}

set<int> s[N], t[N];
void solv()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; ++i)
    {
        a[i].clear();
        s[i].clear();
        t[i].clear();
    }
    for (int i = 0; i < n - 1; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    for (int i = 1; i <= m; ++i)
        scanf("%d", &b[i]);
    dfs(1, 1);
    for (int i = 1; i < m; ++i)
    {
        s[lca(b[i], b[i + 1])].insert(i);
    }
    for (int i = 1; i <= m; ++i)
    {
        t[b[i]].insert(i);
    }
    while (q--)
    {
        int ty;
        scanf("%d", &ty);
        if (ty == 1)
        {
            int i, x;
            scanf("%d%d", &i, &x);
            if (m == 1)
            {
                b[i] = x;
                continue;
            }
            if (i == 1)
            {
                s[lca(b[i], b[i + 1])].erase(i);
                t[b[i]].erase(i);
            }
            else if (i == m)
            {
                s[lca(b[i - 1], b[i])].erase(i - 1);
                t[b[i]].erase(i);
            }
            else
            {
                s[lca(b[i], b[i + 1])].erase(i);
                s[lca(b[i - 1], b[i])].erase(i - 1);
                t[b[i]].erase(i);
            }
            b[i] = x;
            if (i == 1)
            {
                s[lca(b[i], b[i + 1])].insert(i);
                t[b[i]].insert(i);
            }
            else if (i == m)
            {
                s[lca(b[i - 1], b[i])].insert(i - 1);
                t[b[i]].insert(i);
            }
            else
            {
                s[lca(b[i], b[i + 1])].insert(i);
                s[lca(b[i - 1], b[i])].insert(i - 1);
                t[b[i]].insert(i);
            }
        }
        else
        {
            int l, r, x;
            scanf("%d%d%d", &l, &r, &x);
            if (m == 1)
            {
                if (x == b[m])
                    printf("1 1\n");
                else
                    printf("-1 -1\n");
                continue;
            }
            set<int>::iterator it1 = t[x].lower_bound(l);
            set<int>::iterator it = s[x].lower_bound(l);
            if (it1 != t[x].end() && *it1 <= r)
                printf("%d %d\n", *it1, *it1);
            else if (it != s[x].end() && *it + 1 <= r)
                printf("%d %d\n", *it, *it + 1);
            else
                printf("-1 -1\n");
        }
    }
}

int main()
{
    //freopen("input2.txt", "r", stdin);
    int tt = 1;
    while (tt--)
    {
        solv();
    }
    return 0;
}

Compilation message (stderr)

treearray.cpp: In function 'void dfs(int, int)':
treearray.cpp:21:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
treearray.cpp: In function 'void solv()':
treearray.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
treearray.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b[i]);
         ~~~~~^~~~~~~~~~~~~
treearray.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ty);
         ~~~~~^~~~~~~~~~~
treearray.cpp:85:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &i, &x);
             ~~~~~^~~~~~~~~~~~~~~~
treearray.cpp:128:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d%d", &l, &r, &x);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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