Submission #257452

#	Time	Username	Problem	Language	Result	Execution time	Memory
257452		karma	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1301 ms	83320 KiB

treearray

#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair
//#define int         int64_t

using namespace std;

const int N = int(2e5) + 7;
const int logN = 18;
typedef pair<int, int> pii;

int n, m, q, a[N];
int p[N][logN + 1], d[N];
vector<int> adj[N];

void dfs(int u) {
    for(int i = 1; i <= logN; ++i) p[u][i] = p[p[u][i - 1]][i - 1];
    for(int v: adj[u]) {
        if(v == p[u][0]) continue;
        p[v][0] = u;
        d[v] = d[u] + 1;
        dfs(v);
    }
}

int lca(int u, int v) {
    if(d[u] < d[v]) swap(u, v);
    for(int i = logN; i >= 0; --i)
        if(d[u] - (1 << i) >= d[v]) u = p[u][i];
    if(u == v) return u;
    for(int i = logN; i >= 0; --i)
        if(p[u][i] != p[v][i])
            u = p[u][i], v = p[v][i];
    return p[u][0];
}

set<int> s[2][N];

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n >> m >> q;
    for(int u, v, i = 1; i < n; ++i) {
        cin >> u >> v;
        adj[u].pb(v), adj[v].pb(u);
    }
    dfs(1);
    for(int i = 1; i <= m; ++i) {
        cin >> a[i];
        s[0][a[i]].insert(i);
        if(i > 1) s[1][lca(a[i], a[i - 1])].insert(i - 1);
    }
    int cmd, l, r, u;
    while(q --) {
        cin >> cmd;
        if(cmd == 1) {
            cin >> l >> u;
            s[0][a[l]].erase(l);
            if(l < m) s[1][lca(a[l], a[l + 1])].erase(l);
            if(l > 1) s[1][lca(a[l], a[l - 1])].erase(l - 1);
            a[l] = u;
            s[0][a[l]].insert(l);
            if(l < m) s[1][lca(a[l], a[l + 1])].insert(l);
            if(l > 1) s[1][lca(a[l], a[l - 1])].insert(l - 1);
        } else {
            cin >> l >> r >> u;
            auto it0 = s[0][u].lower_bound(l);
            if(it0 != s[0][u].end() && *it0 <= r) {
                cout << *it0 << ' ' << *it0 << '\n';
                continue;
            }
            auto it1 = s[1][u].lower_bound(l);
            if(it1 != s[1][u].end() && *it1 + 1 <= r) {
                cout << *it1 << ' '  << *it1 + 1 << '\n';
                continue;
            }
            cout << "-1 -1\n";
        }
    }
}

Compilation message (stderr)

treearray.cpp: In function 'int32_t main()':
treearray.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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