Submission #570368

#	Time	Username	Problem	Language	Result	Execution time	Memory
570368		Hanksburger	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1027 ms	84172 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
int par[200005][20], dep[200005], a[200005];
set<int> r[200005], s[200005];
vector<int> adj[200005];
int lca(int u, int v)
{
    if (dep[u]>dep[v])
        swap(u, v);
    int d=dep[v]-dep[u];
    for (int i=0; i<20; i++)
        if (d&(1<<i))
            v=par[v][i];
    if (u==v)
        return u;
    for (int i=19; i>=0; i--)
    {
        if (par[u][i]!=par[v][i])
        {
            u=par[u][i];
            v=par[v][i];
        }
    }
    return par[u][0];
}
void dfs(int u, int p)
{
    dep[u]=dep[p]+1;
    par[u][0]=p;
    for (int i=1; i<20; i++)
        par[u][i]=par[par[u][i-1]][i-1];
    for (int i=0; i<adj[u].size(); i++)
    {
        int v=adj[u][i];
        if (v!=p)
            dfs(v, u);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i=1; i<n; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 1);
    for (int i=1; i<=m; i++)
    {
        cin >> a[i];
        r[a[i]].insert(i);
        if (i>=2)
        {
            s[lca(a[i-1], a[i])].insert(i-1);
//            cout << "s " << lca(a[i-1], a[i]) << " insert " << i-1 << '\n';
        }
    }
    for (int i=0; i<q; i++)
    {
        int t;
        cin >> t;
        if (t==1)
        {
            int pos, u;
            cin >> pos >> u;
            r[a[pos]].erase(pos);
            s[lca(a[pos-1], a[pos])].erase(pos-1);
            s[lca(a[pos], a[pos+1])].erase(pos);
//            cout << "s " << lca(a[pos-1], a[pos]) << " erase " << pos-1 << '\n';
//            cout << "s " << lca(a[pos], a[pos+1]) << " erase " << pos << '\n';
            a[pos]=u;
            r[a[pos]].insert(pos);
            s[lca(a[pos-1], a[pos])].insert(pos-1);
            s[lca(a[pos], a[pos+1])].insert(pos);
//            cout << "s " << lca(a[pos-1], a[pos]) << " insert " << pos-1 << '\n';
//            cout << "s " << lca(a[pos], a[pos+1]) << " insert " << pos << '\n';
        }
        else
        {
            int x, y, u;
            cin >> x >> y >> u;
            auto itr1=r[u].lower_bound(x), itr2=s[u].lower_bound(x);
            if (itr1!=r[u].end() && (*itr1)<=y)
                cout << (*itr1) << ' ' << (*itr1) << '\n';
            else if (itr2!=s[u].end() && (*itr2)<y)
                cout << (*itr2) << ' ' << (*itr2)+1 << '\n';
            else
                cout << -1 << ' ' << -1 << '\n';
        }
    }
    return 0;
}

Compilation message (stderr)

treearray.cpp: In function 'void dfs(int, int)':
treearray.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i=0; i<adj[u].size(); i++)
      |                   ~^~~~~~~~~~~~~~

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