Submission #502047

#	Time	Username	Problem	Language	Result	Execution time	Memory
502047		ismoilov	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1087 ms	87096 KiB

treearray

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
#define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
#define fm(a,i,c) for(int (a) = (i); (a) > (c); (a)--)
#define fmm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
const int maxx = 2e5+5;
vector <int> g[maxx];
int a[maxx], d[maxx], lc[maxx][20];
set <int> A[maxx], B[maxx];
int n, m, q;

void dfs(int v, int p = 0){
	lc[v][0] = p;
	fpp(i,1,18)
		lc[v][i] = lc[lc[v][i-1]][i-1];
	for(auto it : g[v]){
		if(it != p){
			d[it] = d[v]+1;
			dfs(it, v);
		}
	}
}

int lca(int u, int v){
	if(d[u] < d[v])
		swap(u, v);
	int k = d[u] - d[v];
	fmm(i,18,0){
		if(k>>i & 1)
			u = lc[u][i];
	}
	if(u == v)
		return u;
	fmm(i,18,0){
		if(lc[u][i] != lc[v][i])
			u = lc[u][i], v = lc[v][i];
	}
	return lc[u][0];
}

void upd(int id, int v){
	if(id > 1){
		int y = lca(a[id], a[id-1]);
		A[y].erase(id-1);
		A[lca(v, a[id-1])].insert(id-1);
	}
	if(id < m){
		int y = lca(a[id], a[id+1]);
		A[y].erase(id);
		A[lca(v, a[id+1])].insert(id);
	}
	B[a[id]].erase(id);
	B[v].insert(id);
	a[id] = v;
}

void get(int l, int r, int v){
	auto it = B[v].lower_bound(l);
	if(it != B[v].end() && *it <= r){
		cout << *it << " " << *it << "\n";
		return;
	}
	it = A[v].lower_bound(l);
	if(it != A[v].end() && *it+1 <= r){
		cout << *it << " " << *it+1 << "\n";
		return;
	}
	cout << "-1 -1\n";
}

void S()
{
//	int n, m, q;
	cin >> n >> m >> q;
	fp(i,1,n){
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1);
	fpp(i,1,m)
		cin >> a[i];
	fpp(i,1,m){
		int x = lca(a[i], a[i+1]);
	//	cout << i << " " << x << "\n";
		if(i < m)
			A[x].insert(i);
		B[a[i]].insert(i);
	}
/*	fpp(i,1,n){
		cout << i << " ";
		for(auto it : A[i])
			cout << it << " ";
		cout << "\n";
	}*/
	while(q --){
		int t;
		cin >> t;
		if(t == 1){
			int id, v;
			cin >> id >> v;
			upd(id, v);
		}
		else{
			int l, r, v;
			cin >> l >> r >> v;
			get(l, r, v);
		}
	}
}
int main()
{
	IOS;
	S();
}

Compilation message (stderr)

treearray.cpp: In function 'void dfs(int, int)':
treearray.cpp:7:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
      |                            ^
treearray.cpp:18:2: note: in expansion of macro 'fpp'
   18 |  fpp(i,1,18)
      |  ^~~
treearray.cpp: In function 'int lca(int, int)':
treearray.cpp:9:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define fmm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
      |                            ^
treearray.cpp:32:2: note: in expansion of macro 'fmm'
   32 |  fmm(i,18,0){
      |  ^~~
treearray.cpp:9:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define fmm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
      |                            ^
treearray.cpp:38:2: note: in expansion of macro 'fmm'
   38 |  fmm(i,18,0){
      |  ^~~
treearray.cpp: In function 'void S()':
treearray.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
      |                           ^
treearray.cpp:79:2: note: in expansion of macro 'fp'
   79 |  fp(i,1,n){
      |  ^~
treearray.cpp:7:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
      |                            ^
treearray.cpp:86:2: note: in expansion of macro 'fpp'
   86 |  fpp(i,1,m)
      |  ^~~
treearray.cpp:7:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
      |                            ^
treearray.cpp:88:2: note: in expansion of macro 'fpp'
   88 |  fpp(i,1,m){
      |  ^~~

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44