Submission #685129

#TimeUsernameProblemLanguageResultExecution timeMemory
685129Nuraly_SerikbayBirthday gift (IZhO18_treearray)C++14
56 / 100
206 ms952 KiB
/* Speech to the young */ //#include <bits/stdc++.h> #include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <string> #include <bitset> #include <cstdio> #include <limits> #include <vector> #include <climits> #include <cstring> #include <cstdlib> #include <fstream> #include <numeric> #include <sstream> #include <cassert> #include <iomanip> #include <iostream> #include <algorithm> #include <stdio.h> #include <fstream> #include <unordered_map> /* #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse,-fgcse-lm") #pragma GCC optimize("-ftree-pre,-ftree-vrp") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("Ofast,no-stack-protector") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") #pragma GCC optimize("unroll-loops") */ using namespace std; #define mp make_pair #define pb push_back #define all(x) x.begin(),x.end() #define F first #define S second #define YOSIK() ios_base::sync_with_stdio(0),cin.tie(0) #define int long long #define cube (x) ((x) * (x) * (x)) int gcd (int a, int b) {if (b == 0){return a;}else {return gcd (b, a % b);}} void pre(int a) { cout<<fixed<<setprecision(a); } int bitcount (int x) {return __builtin_popcount (x);} const int N = 2e6 + 10; const int INF = 1e18 + 1; const int MOD = 1e9 + 7; const int P = 31; const double eps = 1e-19; long double pi = 3.1415926535897323; int n, m, q, depth[2005], up[2005][20], a[2005]; vector <int> g[2005]; void dfs (int v, int p) { up[v][0] = p; for (int i = 1; i <= 15; ++ i) up[v][i] = up[up[v][i - 1]][i - 1]; for (auto to: g[v]) { if (to != p) { depth[to] = depth[v] + 1; dfs (to, v); } } return; } int lca (int a, int b) { if (depth[a] < depth[b]) swap (a, b); int k = depth[a] - depth[b]; for (int i = 15; i >= 0; -- i) if (((k >> i) & 1)) a = up[a][i]; if (a == b) return a; for (int i = 15; i >= 0; -- i) { if (up[a][i] != up[b][i]) { a = up[a][i], b = up[b][i]; } } return up[a][0]; } void Solution () { cin >> n >> m >> q; int x, y; for (int i = 1; i < n; ++ i) { cin >> x >> y; g[x].pb (y), g[y].pb (x); } dfs (1, 0); for (int i = 1; i <= m; ++ i) cin >> a[i]; while (q --) { int tp, l, r, v, pos; cin >> tp; if (tp == 1) { cin >> pos >> v; a[pos] = v; } else { cin >> l >> r >> v; pair <int, int> ans; int x = 0, bg = 0; for (int i = l; i <= r; ++ i) { if (lca (v, a[i]) == v) { if (!x) { x = a[i]; bg = i; } else x = lca (x, a[i]); if (x == v) { ans = {bg, i}; break; } } else x = 0; } if (ans.F == 0 && ans.S == 0) { cout << "-1 -1\n"; } else cout << ans.F << ' ' << ans.S << '\n'; } } } signed main () { YOSIK(); // precalc(); int T = 1; // cin >> T; while (T --) Solution (); exit (0); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...