이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
using ll = int;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vpl = vector<pll>;
using ld = long double;
using str = string;
using big_int = __int128_t;
const ld eps = 1e-7;
const ld PI = acos(-1);
#define all(c) (c).begin(), (c).end()
#define rall(c) ((c).rbegin()), ((c).rend())
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define fast ios_base::sync_with_stdio(0); cin.tie(0)
#define forn(i, n) for (ll i = 0; i < n; ++i)
#define sz(a) (ll)a.size()
#define endl '\n'
#define u_map unordered_map
#define mset multiset
//#define x first
//#define y second
#ifdef ONLINE_JUDGE
#define debug(x);
#else
#define debug(x) cerr << #x << ": " << x << endl;
#endif
str IO[2] = {"NO\n", "YES\n"};
str io[2] = {"no\n", "yes\n"};
str Io[2] = {"No\n", "Yes\n"};
//
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnd(1232423);
template<class T> bool inmin(T& x_, T y_) {return y_ < x_ ? (x_ = y_, true) : false;}
template<class T> bool inmax(T& x_, T y_) {return y_ > x_ ? (x_ = y_, true) : false;}
//const ll Mod = 1e9 + 7;
const ll Mod = 998244353;
//const ll Mod = 1e9 + 9;
//const ll Mod = 1234567891;
const ll INF = 1e18;
template<class T> void add(T& x_, T y_) { x_ = (x_ + y_) % Mod; };
template<class T> void sub(T& x_, T y_) { x_ = (x_ + Mod - y_) % Mod; };
template<class T> void mul(T& x_, T y_) { x_ = (x_ * y_) % Mod; };
const ll Maxn = 2e5 + 10;
const ll Lg = 22;
vll gr[Maxn];
ll up[Lg][Maxn];
ll d[Maxn];
void dfs(ll v, ll p) {
up[0][v] = p;
d[v] = d[p] + 1;
for (ll adj : gr[v]) {
if (adj == p) continue;
dfs(adj, v);
}
}
ll la(ll v, ll k) {
forn (i, Lg) {
if (k & (1 << i))
v = up[i][v];
}
return v;
}
ll lca(ll u, ll v) {
if (d[u] < d[v]) swap(u, v);
u = la(u, d[u] - d[v]);
if (u == v)
return u;
for (ll i = Lg - 1; i >= 0; --i) {
if (up[i][u] == up[i][v]) continue;
u = up[i][u], v = up[i][v];
}
return up[0][u];
}
set<ll> dcV[Maxn], dcL[Maxn];
inline void solve() {
ll n, m, q;
cin >> n >> m >> q;
forn (i, n - 1) {
ll u, v;
cin >> u >> v;
--u, --v;
gr[u].pb(v), gr[v].pb(u);
}
dfs(0, 0);
for (ll i = 1; i < Lg; ++i) {
forn (v, Maxn) {
up[i][v] = up[i - 1][up[i - 1][v]];
}
}
vll que(m);
forn (i, m) {
cin >> que[i];
--que[i];
dcV[que[i]].insert(i);
}
vll lcas(m - 1);
forn (i, m - 1) {
lcas[i] = lca(que[i], que[i + 1]);
dcL[lcas[i]].insert(i);
}
while (q--) {
ll tp;
cin >> tp;
if (tp == 1) {
ll pos, v;
cin >> pos >> v;
--pos, --v;
dcV[que[pos]].erase(pos);
//debug(1);
if (pos - 1 >= 0) {
dcL[lcas[pos - 1]].erase(pos - 1);
}
if (pos + 1 < m) {
dcL[lcas[pos]].erase(pos);
}
que[pos] = v;
dcV[que[pos]].insert(pos);
if (pos - 1 >= 0) {
lcas[pos - 1] = lca(que[pos - 1], que[pos]);
dcL[lcas[pos - 1]].insert(pos - 1);
}
if (pos + 1 < m) {
lcas[pos] = lca(que[pos], que[pos + 1]);
dcL[lcas[pos]].insert(pos);
}
continue;
}
ll l, r, v;
cin >> l >> r >> v;
--l, --r, --v;
auto id = lower_bound(all(dcV[v]), l);
if (id != dcV[v].end() && *id <= r) {
cout << *id + 1 << ' ' << *id + 1 << endl;
continue;
}
if (l == r) {
cout << -1 << ' ' << -1 << endl;
continue;
}
--r;
id = lower_bound(all(dcL[v]), l);
if (id != dcL[v].end() && *id <= r) {
cout << *id + 1 << ' ' << *id + 2 << endl;
continue;
}
cout << -1 << ' ' << -1 << endl;
}
return;
}
int main() {
fast;
//cout << fixed << satprecision(10);
ll test;
test = 1;
//cin >> test;
for (ll id = 0; id < test; ++id) solve();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
treearray.cpp:50:16: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
50 | const ll INF = 1e18;
| ^~~~
# | 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... |