Submission #468539

#	Time	Username	Problem	Language	Result	Execution time	Memory
468539		Killer2501	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1178 ms	102312 KiB

treearray

#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define task "tests"
#define pll pair<ll, ll>
#define pi pair<ll, pll>
#define fi first
#define se second

using namespace std;
const ll mod = 1e9+7;
const ll N = 2e5+5;
const int base = 313;
ll n, m, t, k, T, ans, q, tong, c[N], a[N], b[N], h[N], P[N][20];
vector<ll> adj[N], kq;
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n & 1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}
set<ll> p1[N], p2[N];
void dfs(ll u, ll p)
{
    for(int i = 1; i < 20; i ++)P[u][i] = P[P[u][i-1]][i-1];
    for(ll v : adj[u])
    {
        if(v == p)continue;
        h[v] = h[u] + 1;
        P[v][0] = u;
        dfs(v, u);
    }
}
ll lca(ll u, ll v)
{
    if(h[u] < h[v])swap(u, v);
    ll log = log2(h[u])+1;
    for(int i = log; i >= 0; i --)if(h[u] >= h[v] + (1<<i))u = P[u][i];
    if(u == v)return u;
    for(int i = log; i >= 0; i --)
    {
        if(P[u][i] && P[u][i] != P[v][i])
        {
            u = P[u][i];
            v = P[v][i];
        }
    }
    return P[u][0];
}
void sol()
{
    cin >> n >> m >> q;
    for(int i = 1; i < n; i ++)
    {
        ll x, y;
        cin >> x >> y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    dfs(1, 0);
    for(int i = 1; i <= m; i ++)
    {
        cin >> a[i];
        p1[a[i]].insert(i);
    }
    for(int i = 1; i < m; i ++)
    {
        b[i] = lca(a[i], a[i+1]);
        p2[b[i]].insert(i);
    }
    for(int i = 1; i <= n; i ++)
    {
        p1[i].insert(mod);
        p2[i].insert(mod);
    }
    while(q -- > 0)
    {
        ll l, r;
        cin >> t >> l >> r;
        if(t == 1)
        {
            p1[a[l]].erase(l);
            if(l < m)p2[b[l]].erase(l);
            if(l > 1)p2[b[l-1]].erase(l-1);
            a[l] = r;
            p1[r].insert(l);
            if(l < m)
            {
                b[l] = lca(a[l], a[l+1]);
                p2[b[l]].insert(l);
            }
            if(l > 1)
            {
                b[l-1] = lca(a[l-1], a[l]);
                p2[b[l-1]].insert(l-1);
            }
        }
        else
        {
            cin >> k;
            auto it = p1[k].lower_bound(l);
            if((*it) <= r)cout << (*it) <<" "<<(*it) << '\n';
            else
            {
                it = p2[k].lower_bound(l);
                if((*it)+1 <= r)cout << (*it) <<" "<<(*it)+1<<'\n';
                else cout << -1 <<" "<<-1 << '\n';
            }
        }
    }
}
int main()
{
    if(fopen(task".in", "r"))
    {
       freopen(task".in", "r", stdin);
       freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:120:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |        freopen(task".in", "r", stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:121:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |        freopen(task".out", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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