Submission #1087353

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087353		coldbr3w	Tourism (JOI23_tourism)	C++17	28 / 100	5096 ms	32340 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 3e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 350;
ll n,m,q,timer=0;
vector<ll>adj[N];
ll up[N][20], d[N], tin[N], a[N];
void pre_dfs(ll u, ll par){
	tin[u] = ++timer;
	for(auto v : adj[u]){
		if(v == par) continue;
		up[v][0] = u;
        for(int i = 1; i <= 19;i++) up[v][i] = up[up[v][i-1]][i-1];
        d[v] = d[u] + 1;
		pre_dfs(v, u);
	}
}
ll lca(ll u, ll v){
    if(d[u] != d[v]){
        if(d[u] < d[v]) swap(u, v);
        ll k = d[u] - d[v];
        for(int i = 19; i >= 0;i--) if(k & (1 << i)) u = up[u][i];
    }
    if(u == v) return u;
    for(int i = 19; i >= 0;i--) if(up[u][i] != up[v][i]) u = up[u][i], v = up[v][i];
    return up[u][0];
}
ll dist(ll u, ll v){return d[u] + d[v] - 2 * d[lca(u, v)];}
void to_thic_cau(){
	cin >> n >> m >> q;
	for(int i = 1; i <= n - 1;i++){
		ll u,v; cin >> u >> v;
		adj[u].pb(v); adj[v].pb(u);
	}
	pre_dfs(1, 0);
	for(int i = 1; i <= m;i++) cin >> a[i];
	while(q--){
		ll l,r; cin >> l >> r;
		vector<ll>v;
		for(int i = l; i <= r;i++) v.pb(a[i]);
		sort(all(v), [&](const ll &a, const ll&b){
			return tin[a] < tin[b];
		});
		ll res = 0;
		for(int i = 1; i < v.size();i++) res += dist(v[i], v[i-1]);
		res += dist(v[0], v.back());
		res /= 2;
		cout << res + 1 << '\n';
	}
}
 
signed main()   
{ 
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

Compilation message (stderr)

tourism.cpp: In function 'void to_thic_cau()':
tourism.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int i = 1; i < v.size();i++) res += dist(v[i], v[i-1]);
      |                  ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 7
• Subtask 4: 18 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41