Submission #889697

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
889697	2023-12-20T05:36:11 Z	vjudge1	Tourism (JOI23_tourism)	C++17	7 / 100	134 ms	23388 KB

tourism

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define int long long
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<type1, null_type, less_equal<type1>, rb_tree_tag, tree_order_statistics_node_update>;

using namespace std;
using namespace __gnu_pbds;

const int mod = 1e9+7;
const double PI = acos(-1.0);
const double epsilon = 1e-6;
const int N = 1e5+5;
vector<int> g[N];
int c[N],t2[N*4],t[N*4],dis[N],up[20][N],tin[N],tout[N];
int timer;

void dfs(int v, int pr,int d) {
	dis[v] = d;
    tin[v] = ++timer;
    up[0][v] = pr;
    for (int i = 1; i <= 17; i++) {
        up[i][v] = up[i - 1][ up[i - 1][v] ]; // parent of the parent
    }
    for (int to : g[v]) {
        if (to != pr) dfs(to, v, d + 1);
    }
    tout[v] = timer;
}
 
bool upper(int a, int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}
 
int lca(int a, int b) {
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;
    for (int i = 17; i >= 0; i--) {
        if (!upper(up[i][a], b)) {
            a = up[i][a];
        }
    }
    return up[0][a];
}

void build(int v, int l, int r){
	if(l == r){
		t[v] = c[l];
		t2[v] = c[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(v * 2, l, mid);
	build(v * 2 + 1, mid + 1, r);
	t[v] = min(t[v * 2], t[v * 2 + 1]);
	t2[v] = max(t2[v * 2], t2[v * 2 + 1]);
}
 
int getmn(int v, int tl, int tr, int l, int r) {
    if (l > tr || tl > r) return 1e18;
    if (l <= tl && tr <= r)return t[v];
    int tm = (tl + tr) / 2;
    return min(getmn(v * 2, tl, tm, l, r),getmn(v * 2 + 1, tm + 1, tr, l, r));
}

int getmx(int v, int tl, int tr, int l, int r) {
    if (l > tr || tl > r) return 0;
    if (l <= tl && tr <= r)return t2[v];
    int tm = (tl + tr) / 2;
    return max(getmx(v * 2, tl, tm, l, r),getmx(v * 2 + 1, tm + 1, tr, l, r));
}

void solve(){
	int n,m,q;
	cin >> n >> m >> q;
	bool ok = 1;
	for(int i = 1; i < n; i++){
		int u,v; cin >> u >> v;
		g[u].pb(v); g[v].pb(u);
		if(!(u == i && v == i+1)) ok = 0;
	}
	for(int i = 1; i <= m; i++){
		cin >> c[i];
	}
	if(ok){
		build(1,1,m);
		while(q--){
			int l,r; cin >> l >> r;
			cout << getmx(1,1,m,l,r) - getmn(1,1,m,l,r) + 1 << '\n';
		}
		return;
	}
	dfs(1,0,0);
	
	vector<int> lc(m);
	for(int i = 0; i < m-1; i++){
		lc[i] = lca(c[i],c[i+1]);
	}
	while(q--){
		int l,r; cin >> l >> r;
		l--;r--;
		int ans = 1;
		for(int i = l; i < r; i++){
			if(i == l){
				ans += dis[c[i]] + dis[c[i+1]] - dis[lc[i]] * 2;
			}else{
				
				ans += dis[c[i]] + dis[c[i+1]] - dis[lc[i]] * 2 - (dis[c[i]] - dis[lc[i-1]] + 1);
			}
			cout << ans << ' ';
		}
		cout << ans << '\n';
	}
}

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
}

Compilation message

tourism.cpp:123:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  123 | main(){
      | ^~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	23388 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	23388 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	9052 KB	Output is correct
2	Correct	2 ms	9052 KB	Output is correct
3	Correct	3 ms	9052 KB	Output is correct
4	Correct	78 ms	14332 KB	Output is correct
5	Correct	70 ms	15056 KB	Output is correct
6	Correct	71 ms	15440 KB	Output is correct
7	Correct	134 ms	16212 KB	Output is correct
8	Correct	121 ms	16028 KB	Output is correct
9	Correct	122 ms	16484 KB	Output is correct
10	Correct	109 ms	16192 KB	Output is correct
11	Correct	112 ms	16056 KB	Output is correct
12	Correct	91 ms	16140 KB	Output is correct
13	Correct	98 ms	16028 KB	Output is correct
14	Correct	94 ms	16164 KB	Output is correct
15	Correct	34 ms	13432 KB	Output is correct
16	Correct	91 ms	15712 KB	Output is correct
17	Correct	94 ms	12112 KB	Output is correct