Submission #383667

#	Time	Username	Problem	Language	Result	Execution time	Memory
383667		BartolM	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1468 ms	82640 KiB

treearray

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=2e5+5;
const int LOG=18;

int n, m, q;
int p[N];
vector <int> ls[N];
int dep[N], par[LOG][N];
set <int> S[N], gdje[N];

void build() {
    for (int i=1; i<LOG; ++i) {
        for (int j=1; j<=n; ++j) {
            par[i][j]=par[i-1][par[i-1][j]];
        }
    }
}

int lca(int x, int y) {
    if (dep[x]<dep[y]) swap(x, y);
    for (int i=LOG-1; i>=0; --i) {
        if (dep[x]-(1<<i)>=dep[y]) x=par[i][x];
    }
    if (x==y) return x;
    for (int i=LOG-1; i>=0; --i) {
        if (par[i][x]!=par[i][y]) x=par[i][x], y=par[i][y];
    }
    return par[0][x];
}

void dfs(int node, int rod) {
    par[0][node]=rod;
    dep[node]=dep[rod]+1;
    for (int sus:ls[node]) if (sus!=rod) dfs(sus, node);
}

void solve() {
    dfs(1, 0);
    build();
    for (int i=0; i<m-1; ++i) S[lca(p[i], p[i+1])].insert(i);
    for (int i=0; i<m; ++i) gdje[p[i]].insert(i);

    for (int i=0; i<q; ++i) {
        int br, l, r, x;
        scanf("%d", &br);
        if (br==1) {
            scanf("%d %d", &l, &x); l--;
            if (l) {
                S[lca(p[l], p[l-1])].erase(l-1);
                S[lca(p[l-1], x)].insert(l-1);
            }
            if (l<m-1) {
                S[lca(p[l], p[l+1])].erase(l);
                S[lca(x, p[l+1])].insert(l);
            }
            gdje[p[l]].erase(l);
            gdje[x].insert(l);
            p[l]=x;
        }
        else {
            scanf("%d %d %d", &l, &r, &x); l--; r--;
            auto it=gdje[x].lower_bound(l);
            if (it!=gdje[x].end() && (*it)<=r) {
                printf("%d %d\n", (*it)+1, (*it)+1);
                continue;
            }

            it=S[x].lower_bound(l);
            if (it==S[x].end() || (*it)>=r) printf("-1 -1\n");
            else printf("%d %d\n", (*it)+1, (*it)+2);
        }
    }
}

void load() {
    scanf("%d %d %d", &n, &m, &q);
    for (int i=0; i<n-1; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        ls[a].pb(b); ls[b].pb(a);
    }
    for (int i=0; i<m; ++i) scanf("%d", &p[i]);
}

int main() {
    load();
    solve();
	return 0;
}

Compilation message (stderr)

treearray.cpp: In function 'void solve()':
treearray.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |         scanf("%d", &br);
      |         ~~~~~^~~~~~~~~~~
treearray.cpp:61:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |             scanf("%d %d", &l, &x); l--;
      |             ~~~~~^~~~~~~~~~~~~~~~~
treearray.cpp:75:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |             scanf("%d %d %d", &l, &r, &x); l--; r--;
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp: In function 'void load()':
treearray.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~
treearray.cpp:96:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |     for (int i=0; i<m; ++i) scanf("%d", &p[i]);
      |                             ~~~~~^~~~~~~~~~~~~

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