Submission #1180662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180662		nguyenkhangninh99	Evacuation plan (IZhO18_plan)	C++20	0 / 100	615 ms	589824 KiB

plan

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int maxn = 1e6 + 5;

set <pair<int, int>> ans[maxn];
vector<int> g[maxn];

int h[maxn], up[maxn][21];
 
void dfs(int u){
    for(int v: g[u]){
		
		if(v == up[u][0]) continue;
		
		h[v] = h[u] + 1;
			
		//goi up[i][j] la dinh cha thu 2 mu j cua dinh i 
		up[v][0] = u; 
		for(int j = 1; j <= 20; j++){
			up[v][j]  = up[up[v][j - 1]][j - 1];
		} 
		
		dfs(v);
	}
}
 
int lca(int u, int v){
	if(h[u] != h[v]){
		if(h[u] < h[v]) swap(u, v);
		
		int k = h[u] - h[v];
		
		for(int j = 0; (1 << j) <= k; j++){
			if((k >> j) & 1){
				u = up[u][j];
			}
		}
	}
	
	if(u == v)  return u;
	
	int k = __lg(h[u]);
	
	for(int j = k; j >= 0; j--) {
		if(up[u][j] != up[v][j]){
			u = up[u][j];
			v = up[v][j];
		}
	}
	
	return up[u][0];
}

void solve(){
    int n, m, q; cin >> n >> m >> q;

    for(int i = 1; i <= n - 1; i++){
        int u , v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1);

    vector<int> a(m + 1);

    for(int i = 1; i <= m; i++){
        cin >> a[i];
        ans[a[i]].insert({i, i});

        if(i > 1) ans[lca(a[i] , a[i-1])].insert({i - 1, i});
    }

    while(q--){
        int type; cin >> type;

        if(type == 1){
            int pos, v; cin >> pos >> v;

            ans[a[pos]].erase({pos, pos});
            ans[v].insert({pos, pos});

            if(pos > 1){
                ans[lca(a[pos - 1] , a[pos])].erase({pos - 1, pos});
                ans[lca(a[pos - 1] , v)].insert({pos - 1, pos});
            }
            if(pos < m){
                ans[lca(a[pos], a[pos + 1])].erase({pos, pos + 1});
                ans[lca(v, a[pos + 1])].insert({pos, pos + 1});
            }
            a[pos] = v;
        }
        else{
            int l, r, v; cin >> l >> r >> v;

            auto it = ans[v].lower_bound({l, l});

            if(it != ans[v].end() && (*it).second <= r) cout << (*it).first << " " << (*it).second << "\n";
            else cout << -1 << " " << -1 << "\n";
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);

    solve();
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46