oj.uz

Submission #819276

# Submission time Handle Problem Language Result Execution time Memory
819276 2023-08-10T08:47:34 Z sentheta Tourism (JOI23_tourism) C++17
10 / 100
 5000 ms 27828 KB 
// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
	#define DBG 1
#else
	#include"bits/stdc++.h"
	#define DBG 0
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)

#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}

// #define int long long
// const Int MOD = 1e9+7;
const Int MOD = 998244353;
Int bpow(Int a,Int b){
	Int ret = 1;
	for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
	return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}

void solve(); int TC, ALLTC;
signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(7);
	// cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0;
	solve();
}














const int N = 1e5+69;
const int LN = 18;
const int SN = 600;
int hilbert(int x, int y){
	int d = 0;
	for(int s=1LL<<(LN-1); s; s>>=1){
		bool rx=x&s, ry=y&s;
		d = d<<2 | rx*3^ry;
		if(!ry){ if(rx){
			x = (1<<LN)-x; y = (1<<LN)-y;
		} swap(x,y); }
	} return d;
}

int n, m, q;
int a[N];


// tree utilities
V<int> adj[N];
int d[N], p[N];
int getMinDepth(int x,int y){
	return d[x]<d[y] ? x : y;
}
int getMaxDepth(int x,int y){
	return d[x]>d[y] ? x : y;
}
struct Stable{
	int v[2*N][LN];
	void build(){
		rep(lg,1,LN) for(int i=0; i+(1<<lg)-1<2*N; i++)
			v[i][lg] = getMinDepth(v[i][lg-1], v[i+(1<<(lg-1))][lg-1]);
	}
	int qry(int l,int r){
		int lg = __lg(r-l+1);
		return getMinDepth(v[l][lg], v[r-(1<<lg)+1][lg]);
	}
} stable;
int t[N], tim;
int getLca(int x,int y){
	if(!(t[x]<t[y])) swap(x,y);
	return stable.qry(t[x],t[y]);
}
void dfs_init(int x=1){
	t[x] = tim;
	stable.v[tim++][0] = x;

	for(int y : adj[x]) if(y!=p[x]){
		d[y] = d[x]+1;
		p[y] = x;
		dfs_init(y);
		
		stable.v[tim++][0] = x;
	}
}


// s = {t[nodes]}
multiset<int> s;
int pathlen = 0;
int getSemipath(int i,int j){
	// return d[stable.v[j][0]] - d[stable.qry(i,j)];
	assert(i <= j);
	int u = stable.v[i][0];
	int v = stable.v[j][0];
	return d[v] - d[getLca(u,v)];
}
void insert(int i){
	auto it = s.insert(i);
	
	// remove prv-nxt
	if(it!=s.begin() && it!=prev(s.end())){
		int prvi = *prev(it), nxti = *next(it);
		pathlen -= getSemipath(prvi, nxti);
	}
	// connect prv-i
	if(it!=s.begin()){
		int prvi = *prev(it);
		pathlen += getSemipath(prvi, i);
	}
	// connect i-nxt
	if(it!=prev(s.end())){
		int nxti = *next(it);
		pathlen += getSemipath(i, nxti);
	}
}
void erase(int i){
	auto it = s.find(i);
	
	// remove prv-i
	if(it!=s.begin()){
		int prvi = *prev(it);
		pathlen -= getSemipath(prvi, i);
	}
	// remove i-nxt
	if(it!=prev(s.end())){
		int nxti = *next(it);
		pathlen -= getSemipath(i, nxti);
	}	
	// connect prv-nxt
	if(it!=s.begin() && it!=prev(s.end())){
		int prvi = *prev(it), nxti = *next(it);
		pathlen += getSemipath(prvi, nxti);
	}
	
	s.erase(it);
}



int ql[N], qr[N], qans[N];
int qhsh[N];



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

	rep(i,0,n-1){
		int u, v;
		cin >> u >> v;
		
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs_init();
	stable.build();
	
	// rep(i,1,n+1) cerr << t[i] << " ";
	// cerr << nl;

	rep(i,1,m+1){
		cin >> a[i];
	}
	
	V<int> ord;
	rep(i,1,q+1){
		cin >> ql[i] >> qr[i];
		
		ord.push_back(i);
		qhsh[i] = hilbert(ql[i], qr[i]);
	}
	sort(all(ord),[&](int i,int j){
		return qhsh[i] < qhsh[j];
		// if(ql[i]/SN==ql[j]/SN) return qr[i] < qr[j];
		// return ql[i]/SN < ql[j]/SN;
	});
	
	
	int l=1, r=1;
	insert(t[a[1]]);
	for(int i : ord){
		while(ql[i] < l) insert(t[a[--l]]);
		while(r < qr[i]) insert(t[a[++r]]);
		while(l < ql[i]) erase(t[a[l++]]);
		while(qr[i] < r) erase(t[a[r--]]);
		assert(l==ql[i] && r==qr[i]);

		// leftmost and rightmost node
		int li = *s.begin();
		int ri = *prev(s.end());
		int u = stable.v[li][0];
		int v = stable.v[ri][0];
		int lca = getLca(u,v);
		
		dbg(pathlen);
		int ans = pathlen + d[u]-d[lca];
		// int ans = pathlen + d[stable.v[li][0]]-d[stable.qry(li,ri)];
		qans[i] = ans;
	}
	
	rep(i,1,q+1){
		cout << qans[i]+1 << nl;
	}



}

Compilation message

tourism.cpp: In function 'int hilbert(int, int)':
tourism.cpp:68:18: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   68 |   d = d<<2 | rx*3^ry;
      |              ~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16784 KB Output is correct
2 Correct 31 ms 16792 KB Output is correct
3 Correct 30 ms 16796 KB Output is correct
4 Correct 37 ms 16792 KB Output is correct
5 Correct 19 ms 16764 KB Output is correct
6 Correct 27 ms 16800 KB Output is correct
7 Correct 46 ms 16804 KB Output is correct
8 Correct 40 ms 16792 KB Output is correct
9 Correct 26 ms 16808 KB Output is correct
10 Correct 23 ms 16724 KB Output is correct
11 Correct 20 ms 16820 KB Output is correct
12 Correct 20 ms 16800 KB Output is correct
13 Correct 30 ms 16816 KB Output is correct
14 Correct 22 ms 16804 KB Output is correct
15 Correct 19 ms 16828 KB Output is correct
16 Correct 26 ms 16844 KB Output is correct
17 Correct 21 ms 16772 KB Output is correct
18 Correct 24 ms 16780 KB Output is correct
19 Correct 35 ms 16844 KB Output is correct
20 Correct 18 ms 16844 KB Output is correct
21 Correct 16 ms 16776 KB Output is correct
22 Correct 23 ms 16816 KB Output is correct
23 Correct 22 ms 16824 KB Output is correct
24 Correct 27 ms 16896 KB Output is correct
25 Correct 21 ms 16824 KB Output is correct
26 Correct 20 ms 16800 KB Output is correct
27 Correct 24 ms 16776 KB Output is correct
28 Correct 29 ms 16796 KB Output is correct
29 Correct 21 ms 16808 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16784 KB Output is correct
2 Correct 31 ms 16792 KB Output is correct
3 Correct 30 ms 16796 KB Output is correct
4 Correct 37 ms 16792 KB Output is correct
5 Correct 19 ms 16764 KB Output is correct
6 Correct 27 ms 16800 KB Output is correct
7 Correct 46 ms 16804 KB Output is correct
8 Correct 40 ms 16792 KB Output is correct
9 Correct 26 ms 16808 KB Output is correct
10 Correct 23 ms 16724 KB Output is correct
11 Correct 20 ms 16820 KB Output is correct
12 Correct 20 ms 16800 KB Output is correct
13 Correct 30 ms 16816 KB Output is correct
14 Correct 22 ms 16804 KB Output is correct
15 Correct 19 ms 16828 KB Output is correct
16 Correct 26 ms 16844 KB Output is correct
17 Correct 21 ms 16772 KB Output is correct
18 Correct 24 ms 16780 KB Output is correct
19 Correct 35 ms 16844 KB Output is correct
20 Correct 18 ms 16844 KB Output is correct
21 Correct 16 ms 16776 KB Output is correct
22 Correct 23 ms 16816 KB Output is correct
23 Correct 22 ms 16824 KB Output is correct
24 Correct 27 ms 16896 KB Output is correct
25 Correct 21 ms 16824 KB Output is correct
26 Correct 20 ms 16800 KB Output is correct
27 Correct 24 ms 16776 KB Output is correct
28 Correct 29 ms 16796 KB Output is correct
29 Correct 21 ms 16808 KB Output is correct
30 Correct 27 ms 16972 KB Output is correct
31 Correct 35 ms 16984 KB Output is correct
32 Correct 39 ms 16968 KB Output is correct
33 Correct 32 ms 17052 KB Output is correct
34 Correct 37 ms 17052 KB Output is correct
35 Correct 25 ms 17080 KB Output is correct
36 Correct 28 ms 17048 KB Output is correct
37 Correct 32 ms 17040 KB Output is correct
38 Correct 33 ms 17120 KB Output is correct
39 Correct 37 ms 17132 KB Output is correct
40 Correct 28 ms 17152 KB Output is correct
41 Correct 37 ms 17156 KB Output is correct
42 Correct 23 ms 17144 KB Output is correct
43 Correct 26 ms 17108 KB Output is correct
44 Correct 46 ms 17100 KB Output is correct
45 Correct 42 ms 17076 KB Output is correct
46 Correct 32 ms 17064 KB Output is correct
47 Correct 26 ms 17084 KB Output is correct
48 Correct 28 ms 17080 KB Output is correct
49 Correct 22 ms 17084 KB Output is correct
50 Correct 48 ms 17032 KB Output is correct
51 Correct 39 ms 17056 KB Output is correct
52 Correct 41 ms 17064 KB Output is correct
53 Correct 41 ms 17060 KB Output is correct
54 Correct 42 ms 16988 KB Output is correct
55 Correct 48 ms 17056 KB Output is correct
56 Correct 29 ms 16940 KB Output is correct
57 Correct 29 ms 16916 KB Output is correct
58 Correct 25 ms 16932 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16792 KB Output is correct
2 Correct 19 ms 16800 KB Output is correct
3 Correct 28 ms 16920 KB Output is correct
4 Execution timed out 5065 ms 27828 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 16788 KB Output is correct
2 Correct 140 ms 21960 KB Output is correct
3 Execution timed out 5059 ms 22872 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16796 KB Output is correct
2 Correct 24 ms 16704 KB Output is correct
3 Correct 44 ms 16904 KB Output is correct
4 Execution timed out 5087 ms 24836 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16784 KB Output is correct
2 Correct 31 ms 16792 KB Output is correct
3 Correct 30 ms 16796 KB Output is correct
4 Correct 37 ms 16792 KB Output is correct
5 Correct 19 ms 16764 KB Output is correct
6 Correct 27 ms 16800 KB Output is correct
7 Correct 46 ms 16804 KB Output is correct
8 Correct 40 ms 16792 KB Output is correct
9 Correct 26 ms 16808 KB Output is correct
10 Correct 23 ms 16724 KB Output is correct
11 Correct 20 ms 16820 KB Output is correct
12 Correct 20 ms 16800 KB Output is correct
13 Correct 30 ms 16816 KB Output is correct
14 Correct 22 ms 16804 KB Output is correct
15 Correct 19 ms 16828 KB Output is correct
16 Correct 26 ms 16844 KB Output is correct
17 Correct 21 ms 16772 KB Output is correct
18 Correct 24 ms 16780 KB Output is correct
19 Correct 35 ms 16844 KB Output is correct
20 Correct 18 ms 16844 KB Output is correct
21 Correct 16 ms 16776 KB Output is correct
22 Correct 23 ms 16816 KB Output is correct
23 Correct 22 ms 16824 KB Output is correct
24 Correct 27 ms 16896 KB Output is correct
25 Correct 21 ms 16824 KB Output is correct
26 Correct 20 ms 16800 KB Output is correct
27 Correct 24 ms 16776 KB Output is correct
28 Correct 29 ms 16796 KB Output is correct
29 Correct 21 ms 16808 KB Output is correct
30 Correct 27 ms 16972 KB Output is correct
31 Correct 35 ms 16984 KB Output is correct
32 Correct 39 ms 16968 KB Output is correct
33 Correct 32 ms 17052 KB Output is correct
34 Correct 37 ms 17052 KB Output is correct
35 Correct 25 ms 17080 KB Output is correct
36 Correct 28 ms 17048 KB Output is correct
37 Correct 32 ms 17040 KB Output is correct
38 Correct 33 ms 17120 KB Output is correct
39 Correct 37 ms 17132 KB Output is correct
40 Correct 28 ms 17152 KB Output is correct
41 Correct 37 ms 17156 KB Output is correct
42 Correct 23 ms 17144 KB Output is correct
43 Correct 26 ms 17108 KB Output is correct
44 Correct 46 ms 17100 KB Output is correct
45 Correct 42 ms 17076 KB Output is correct
46 Correct 32 ms 17064 KB Output is correct
47 Correct 26 ms 17084 KB Output is correct
48 Correct 28 ms 17080 KB Output is correct
49 Correct 22 ms 17084 KB Output is correct
50 Correct 48 ms 17032 KB Output is correct
51 Correct 39 ms 17056 KB Output is correct
52 Correct 41 ms 17064 KB Output is correct
53 Correct 41 ms 17060 KB Output is correct
54 Correct 42 ms 16988 KB Output is correct
55 Correct 48 ms 17056 KB Output is correct
56 Correct 29 ms 16940 KB Output is correct
57 Correct 29 ms 16916 KB Output is correct
58 Correct 25 ms 16932 KB Output is correct
59 Correct 16 ms 16792 KB Output is correct
60 Correct 19 ms 16800 KB Output is correct
61 Correct 28 ms 16920 KB Output is correct
62 Execution timed out 5065 ms 27828 KB Time limit exceeded
63 Halted 0 ms 0 KB -