oj.uz

Submission #1087393

# Submission time Handle Problem Language Result Execution time Memory
1087393 2024-09-12T15:27:11 Z coldbr3w Tourism (JOI23_tourism) C++17
0 / 100
 306 ms 47184 KB 
#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 tin[N], heavy[N], sz[N], p[N], head[N], res[N], a[N];
vector<pll>t[N];
set<array<ll,3>>s;
struct fenwick_tree{
	ll n;
	vector<ll>ft;
	void init(ll _n){
		n = _n;
		ft.resize(n + 10);
	}
	void update(ll idx, ll val){
		while(idx <= n) ft[idx] += val, idx += (idx & (-idx));
	}
	ll get(ll idx){
		ll res = 0;
		while(idx > 0) res += ft[idx], idx -= (idx & (-idx));
		return res;
	}
} ft;
void dfs(ll u, ll par){
    sz[u] = 1;
    for(auto v : adj[u]){
        if(v == par) continue;
        dfs(v, u);
        p[v] = u;
        sz[u] += sz[v];
        if(sz[v] > sz[heavy[u]]) heavy[u] = v;
    }
}
void HLD(ll u, ll h){
    head[u] = h; tin[u] = ++timer;
    if(heavy[u]) HLD(heavy[u], h);
    for(auto v : adj[u]){
        if(v != p[u] && v != heavy[u]) HLD(v, v);
    }
}
void change(ll l, ll r, ll val){
	auto it = s.lower_bound({l, l, 0});
	if(it != s.begin()) --it;
	vector<array<ll,3>>del, add;
	add.pb({l, r, val});
	while(it != s.end() && (*it)[0] <= r){
		ll l1 = (*it)[0], r1 = (*it)[1], v1 = (*it)[2];
		if(r1 < l){
			++it;
			continue;
		}
		del.pb(*it);
		if(l1 < l) add.pb({l1, l - 1, v1});
		if(r1 > r) add.pb({r + 1, r1, v1});
		++it;
	}
	for(auto x : del){
		ft.update(x[2], -(x[1] - x[0] + 1));
		s.erase(x);
	}
	for(auto x : add){
		ft.update(x[2], x[1] - x[0] + 1);
		s.insert(x);
	}
}
void upd(ll a, ll b, ll val){
    for(; head[a] != head[b]; b = p[head[b]]){
        if(tin[a] > tin[b]) swap(a, b);
        change(tin[head[b]], tin[b], val);
    }
    if(tin[a] > tin[b]) swap(a, b);
   	change(tin[a], tin[b], val);
}
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);
	}
	dfs(1, 0);	
	HLD(1, 1);
	for(int i = 1; i <= m;i++) cin >> a[i];
	for(int i = 1; i <= q;i++){
		ll l,r; cin >> l >> r;
		t[r].pb({l, i});
	}
	s.insert({1, n, 1});
	ft.init(n);
	ft.update(1, n);
	for(int i = 1; i <= m;i++){
		if(i > 1) upd(a[i-1], a[i], i);
		for(auto x : t[i]){
			ll l = x.F, idx = x.S;
			if(l == i){
				res[idx] = 1;
				continue;
			}
			res[idx] = ft.get(n) - ft.get(l);
		}
	}
	for(int i = 1; i <= q;i++) cout << res[i] << '\n';
}
 
signed main()   
{ 
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 8 ms 14428 KB Output is correct
3 Correct 7 ms 14564 KB Output is correct
4 Incorrect 7 ms 14428 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 8 ms 14428 KB Output is correct
3 Correct 7 ms 14564 KB Output is correct
4 Incorrect 7 ms 14428 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14552 KB Output is correct
2 Incorrect 7 ms 14428 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14556 KB Output is correct
2 Correct 303 ms 22832 KB Output is correct
3 Runtime error 306 ms 47184 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Incorrect 7 ms 14464 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14424 KB Output is correct
2 Correct 8 ms 14428 KB Output is correct
3 Correct 7 ms 14564 KB Output is correct
4 Incorrect 7 ms 14428 KB Output isn't correct
5 Halted 0 ms 0 KB -