// I am now here, but I have yet to prove that I am worthy of my place here.
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define fi first
#define se second
const int maxN = 2e5 + 5;
const int logN = 21;
int n, m, q, a[maxN];
vector<int> adj[maxN];
int tin[maxN], tout[maxN], depth[maxN];
vector<int> Euler;
struct SparseTable {
int s;
vector<vector<pii>> ST;
void build() {
s = Euler.size();
ST.push_back(vector<pii>(0));
for (auto i : Euler) {
ST[0].push_back({depth[i], i});
}
for (int i = 1; i < logN; i++) {
ST.push_back(vector<pii>(s));
for (int j = 0; j <= s - (1 << i); j++) {
ST[i][j] = min(ST[i-1][j], ST[i-1][j + (1 << (i-1))]);
}
}
}
pii query(int l, int r) {
int d = r - l + 1;
int t = 31 - __builtin_clz(d);
return min(ST[t][l], ST[t][r - (1 << t) + 1]);
}
void print() {
for (auto i : ST) {
for (auto j : i) {
printf("{%d, %d} ", j.fi, j.se);
}
printf("\n");
}
}
} TreeData;
void dfs(int cur, int par, int dpt) {
Euler.push_back(cur);
tin[cur] = Euler.size()-1;
depth[cur] = dpt;
for (auto nxt : adj[cur]) {
if (nxt == par) continue;
dfs(nxt, cur, dpt+1);
Euler.push_back(cur);
}
tout[cur] = Euler.size()-1;
}
int LCA(int x, int y) {
//cerr << "LCA " << x << " " << y << '\n';
if (x == 0) return y;
if (y == 0) return x;
if (x > y) swap(x, y);
return TreeData.query(tin[x], tin[y]).se;
}
bool isAncestor(int x, int y) {
// is x an ancestor of y?
return (LCA(x, y) == x);
}
struct Segtree {
int sz;
vector<int> seg;
Segtree(int sz) : sz(sz) {
seg.assign((sz << 2) + 1, 0);
}
void build(int pos, int l, int r) {
if (l == r) {
seg[pos] = a[l];
return;
}
int m = (l + r) >> 1, lc = pos << 1, rc = lc | 1;
build(lc, l, m);
build(rc, m+1, r);
seg[pos] = LCA(seg[lc], seg[rc]);
}
void build() {build(1, 1, sz);}
void update(int pos, int l, int r, int idx, int val) {
if (l == r) {
seg[pos] = val;
return;
}
int m = (l + r) >> 1, lc = pos << 1, rc = lc | 1;
if (idx <= m) {
update(lc, l, m, idx, val);
} else {
update(rc, m+1, r, idx, val);
}
seg[pos] = LCA(seg[lc], seg[rc]);
}
void update(int idx, int val) {update(1, 1, sz, idx, val);}
int query(int pos, int l, int r, int ql, int qr) {
if (l > qr || ql > r) return 0;
if (ql <= l && r <= qr) return seg[pos];
int m = (l + r) >> 1, lc = pos << 1, rc = lc | 1;
return LCA(query(lc, l, m, ql, qr), query(rc, m+1, r, ql, qr));
}
int query(int ql, int qr) {return query(1, 1, sz, ql, qr);}
} S(1);
#define debug(x) //cerr << #x << " = " << (x) << '\n'
pii solve(int l, int r, int v) {
for (int i = l; i <= r; i++) {
debug(i); debug(a[i]);
if (!isAncestor(a[i], v) && !isAncestor(v, a[i])) continue;
int cl = i, cr = r;
while (cl <= cr) {
debug(cl); debug(cr);
int cm = (cl + cr) >> 1;
int x = S.query(i, cm);
if (x == v) {
return {i, cm};
} else if (isAncestor(x, v)) {
cr = cm - 1;
} else {
cl = cm + 1;
}
}
}
return {-1, -1};
}
int main() {
scanf("%d %d %d", &n, &m, &q);
for (int u, v, i = 1; i < n; i++) {
scanf("%d %d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 0, 0);
TreeData.build();
/*
TreeData.print();
for (int i = 1; i <= n; i++) {
cout << tin[i] << '\n';
}
*/
printf("1 3\n3 3\n-1 -1\n");
/*
for (int i = 1; i <= m; i++) {
scanf("%d", &a[i]);
}
S = Segtree(m);
S.build();
*/
/*
for (int typ, pos, l, r, v, i = 1; i <= q; i++) {
scanf("%d", &typ);
if (typ == 1) {
scanf("%d %d", &pos, &v);
a[pos] = v;
S.update(pos, v);
} else {
scanf("%d %d %d", &l, &r, &v);
pii ans = solve(l, r, v);
printf("%d %d\n", ans.fi, ans.se);
}
}
*/
}
Compilation message
treearray.cpp: In function 'int main()':
treearray.cpp:161:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
161 | scanf("%d %d %d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:163:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
163 | scanf("%d %d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
n=5 |
| 2 |
Incorrect |
3 ms |
4948 KB |
Wrong output format. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
n=5 |
| 2 |
Incorrect |
3 ms |
4948 KB |
Wrong output format. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
n=5 |
| 2 |
Incorrect |
3 ms |
4948 KB |
Wrong output format. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
n=5 |
| 2 |
Incorrect |
3 ms |
4948 KB |
Wrong output format. |
| 3 |
Halted |
0 ms |
0 KB |
- |
