이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for (int i = x; i < y; i++)
const int mx = 2e5 + 5, ml = 18;
int n, m, q, up[mx][ml], dep[mx], A[mx], L[mx];
vector<int> adj[mx]; set<int> posA[mx], posL[mx];
void dfs(int cur){
FOR(i, 1, ml) up[cur][i] = up[up[cur][i - 1]][i - 1];
for (int to : adj[cur]) if (to != up[cur][0]){
up[to][0] = cur; dep[to] = dep[cur] + 1;
dfs(to);
}
}
int lca(int a, int b){
if (dep[a] < dep[b]) swap(a, b);
int dif = dep[a] - dep[b];
FOR(i, 0, 18) if ((dif >> i) % 2) a = up[a][i];
if (a == b) return a;
for (int i = 17; ~i; i--) if (up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];
return up[a][0];
}
void upd(int i, int v){
posA[A[i]].erase(i); A[i] = v; posA[A[i]].insert(i);
posL[L[i - 1]].erase(i - 1); posL[L[i]].erase(i);
L[i - 1] = lca(A[i - 1], A[i]); L[i] = lca(A[i], A[i + 1]);
posL[L[i - 1]].insert(i - 1); posL[L[i]].insert(i);
}
bool solve(int l, int r, int v){
auto itA = posA[v].lower_bound(l);
auto itL = posL[v].lower_bound(l);
if (itA != posA[v].end() and *itA <= r) cout<<*itA<<" "<<*itA<<"\n";
else if (itL != posL[v].end() and *itL < r) cout<<*itL<<" "<<*itL + 1<<"\n";
else cout<<"-1 -1"<<"\n";
}
int main(){
cin >> n >> m >> q;
FOR(i, 1, n){
int a, b; cin >> a >> b;
adj[a].push_back(b); adj[b].push_back(a);
}
dfs(1);
FOR(i, 1, m + 1){ int v; cin >> v; upd(i, v); }
while (q--){
int t; cin >> t;
if (t == 1){ int a, v; cin >> a >> v; upd(a, v); }
else{ int l, r, v; cin >> l >> r >> v; solve(l, r, v); }
}
}
컴파일 시 표준 에러 (stderr) 메시지
treearray.cpp: In function 'bool solve(int, int, int)':
treearray.cpp:40:1: warning: no return statement in function returning non-void [-Wreturn-type]
40 | }
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |