# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
245650 | Mercenary | Birthday gift (IZhO18_treearray) | C++14 | 1450 ms | 82644 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#define pb push_back
#define mp make_pair
#define taskname "A"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
const int logn = log2(maxn) + 1;
int n , m , q;
vector<int> adj[maxn];
int a[maxn];
int P[maxn][logn] , dep[maxn];
void dfs(int u , int par){
for(auto c : adj[u]){
if(c == par)continue;
dep[c] = dep[u] + 1;
P[c][0] = u;
for(int i = 1 ; i < logn ; ++i)P[c][i] = P[P[c][i - 1]][i - 1];
dfs(c , u);
}
}
int lca(int u , int v){
if(dep[u] < dep[v])swap(u ,v);
for(int i = 0 ; i < logn ; ++i)if((dep[u] - dep[v]) & (1 << i))u = P[u][i];
if(u == v)return u;
for(int i = logn - 1 ; i >= 0 ; --i){
if(P[u][i] != P[v][i]){
u = P[u][i];
v = P[v][i];
}
}
return P[u][0];
}
set<int> s[maxn] , s1[maxn];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen(taskname".INP","r")){
freopen(taskname".INP", "r",stdin);
freopen(taskname".OUT", "w",stdout);
}
cin >> n >> m >> q;
for(int i = 1 ; i < n ; ++i){
int u , v;cin >> u >> v;
adj[u].pb(v);adj[v].pb(u);
}
for(int i = 1 ; i <= m ; ++i)cin >> a[i];
dfs(1 , 0);
for(int i = 1 ; i < m ; ++i){
s1[lca(a[i] , a[i + 1])].insert(i);
}
for(int i = 1 ; i <= m ; ++i){
s[a[i]].insert(i);
}
while(q--){
int type;cin >> type;
if(type == 1){
int i , v;cin >> i >> v;
if(a[i] == v)continue;
s[a[i]].erase(i);
if(i > 1)s1[lca(a[i],a[i - 1])].erase(i - 1);
if(i + 1 <= m)s1[lca(a[i] , a[i + 1])].erase(i);
a[i] = v;
s[a[i]].insert(i);
if(i > 1)s1[lca(a[i],a[i - 1])].insert(i - 1);
if(i + 1 <= m)s1[lca(a[i] , a[i + 1])].insert(i);
}else{
int l , r , v;cin >> l >> r >> v;
auto it = s[v].lower_bound(l);
if(it == s[v].end() || *it > r){
auto it1 = s1[v].lower_bound(l);
if(it1 == s1[v].end() || *it1 + 1 > r){
cout << -1 << " " << -1 << '\n';
}else{
cout << *it1 << " " << *it1 + 1 << '\n';
}
}else{
cout << *it << " " << *it << '\n';
}
}
}
}
Compilation message (stderr)
# | 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... |