제출 #579992

#제출 시각아이디문제언어결과실행 시간메모리
579992loggerrBirthday gift (IZhO18_treearray)C++14
56 / 100
4093 ms69504 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...