oj.uz

Submission #923094

# Submission time Handle Problem Language Result Execution time Memory
923094 2024-02-06T14:57:00 Z denniskim Tourism (JOI23_tourism) C++17
31 / 100
 458 ms 52104 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

struct gujo
{
	ll L, R, num;
	
	bool operator < (const gujo &xx) const
	{
		return L > xx.L;
	}
};

ll n, m, q;
ll all, bll;
vector<ll> vec[100010];
gujo qry[100010];
ll a[100010];
ll IN[100010], OUT[100010], cc;
ll spa[100010][21], dep[100010], siz[100010];
ll tp[100010];
set<pll> st[100010];
ll maxx[100010];
ll ans[100010];

struct fenwicktree
{
	ll bit[100010];
	
	void update(ll w, ll v)
	{
		for(ll i = w ; i <= m + 1 ; i += (i & (-i)))
			bit[i] += v;
	}
	
	ll query(ll w)
	{
		ll ret = 0;
		
		for(ll i = w ; i > 0 ; i -= (i & (-i)))
			ret += bit[i];
		
		return ret;
	}
}BIT;

void dfs0(ll here, ll pa)
{
	IN[here] = ++cc;
	siz[here] = 1;
	
	for(auto &i : vec[here])
	{
		if(i == pa)
			continue;
		
		dep[i] = dep[here] + 1;
		spa[i][0] = here;
		dfs0(i, here);
		siz[here] += siz[i];
	}
	
	OUT[here] = cc;
}

void dfs(ll here)
{
	for(auto &i : vec[here])
	{
		if(i == vec[here][0])
			tp[i] = tp[here];
		else
			tp[i] = i;
		
		dfs(i);
	}
}

ll lift(ll X, ll Y)
{
	for(ll i = 20 ; i >= 0 ; i--)
	{
		if((1LL << i) <= Y)
		{
			Y -= (1LL << i);
			X = spa[X][i];
		}
	}
	
	return X;
}

ll LCA(ll X, ll Y)
{
	if(dep[X] < dep[Y])
		swap(X, Y);
	
	ll cha = dep[X] - dep[Y];
	
	X = lift(X, cha);
	
	if(X == Y)
		return X;
	
	for(ll i = 20 ; i >= 0 ; i--)
	{
		if(spa[X][i] != spa[Y][i])
		{
			X = spa[X][i];
			Y = spa[Y][i];
		}
	}
	
	return spa[X][0];
}

void map_update(ll num, ll X, ll Y, ll Z)
{
	auto p = st[num].upper_bound({X, INF});
	auto p2 = p;
	vector< pair<pll, ll> > vv;
	ll END = maxx[num];
	
	p2--;
	
	while(1)
	{
		vv.push_back({{(*p2).fi, INF}, (*p2).se});
		p2++;
		
		if(p2 == st[num].end())
			break;
		
		if((*p2).fi > Y)
		{
			END = (*p2).fi - 1;
			break;
		}
	}
	
	for(ll i = 0 ; i < (ll)vv.size() ; i++)
	{
		if(i < (ll)vv.size() - 1)
			vv[i].fi.se = vv[i + 1].fi.fi - 1;
		else
			vv[i].fi.se = END;
	}
	
	vector< pair<pll, ll> > vv2;
	
	for(auto &i : vv)
	{
		if(X <= i.fi.fi && i.fi.se <= Y)
			continue;
		
		if(i.fi.fi < X)
		{
			if(X <= i.fi.se)
			{
				vv2.push_back({{i.fi.fi, X - 1}, i.se});
				
				if(Y < i.fi.se)
					vv2.push_back({{Y + 1, i.fi.se}, i.se});
			}
			
			else
				vv2.push_back(i);
		}
		
		else if(Y < i.fi.se)
		{
			if(i.fi.fi <= Y)
				vv2.push_back({{Y + 1, i.fi.se}, i.se});
			else
				vv2.push_back(i);
		}
	}
	
	vv2.push_back({{X, Y}, Z});
	
	for(auto &i : vv)
	{
		BIT.update(i.se, -i.fi.se + i.fi.fi - 1);
		st[num].erase({i.fi.fi, i.se});
	}
	
	for(auto &i : vv2)
	{
		BIT.update(i.se, i.fi.se - i.fi.fi + 1);
		st[num].insert({i.fi.fi, i.se});
	}
}

void update(ll X, ll Y, ll Z)
{
	while(tp[X] != tp[Y])
	{
		if(dep[tp[X]] < dep[tp[Y]])
			swap(X, Y);
		
		map_update(tp[X], IN[tp[X]], IN[X], Z);
		X = spa[tp[X]][0];
	}
	
	if(dep[X] < dep[Y])
		swap(X, Y);
	
	if(X == Y)
		return;
	
	ll tp2 = lift(X, dep[X] - dep[Y] - 1);
	
	map_update(tp[X], IN[tp2], IN[X], Z);
}

int main(void)
{
	fastio
	
	cin >> n >> m >> q;
	
	for(ll i = 1 ; i < n ; i++)
	{
		cin >> all >> bll;
		
		vec[all].push_back(bll);
		vec[bll].push_back(all);
	}
	
	for(ll i = 1 ; i <= m ; i++)
		cin >> a[i];
	
	for(ll i = 1 ; i <= q ; i++)
	{
		cin >> qry[i].L >> qry[i].R;
		qry[i].num = i;
	}
	
	sort(qry + 1, qry + 1 + q);
	
	dfs0(1, 0);
	
	for(ll i = 1 ; i <= 20 ; i++)
	{
		for(ll j = 1 ; j <= n ; j++)
			spa[j][i] = spa[spa[j][i - 1]][i - 1];
	}
	
	for(ll i = 2 ; i <= n ; i++)
	{
		for(ll j = 0 ; j < (ll)vec[i].size() - 1 ; j++)
		{
			if(vec[i][j] == spa[i][0])
				swap(vec[i][j], vec[i][j + 1]);
		}
		
		vec[i].pop_back();
		
		for(ll j = 0 ; j < (ll)vec[i].size() ; j++)
		{
			if(siz[vec[i][j]] > siz[vec[i][0]])
				swap(vec[i][j], vec[i][0]);
		}
	}
	
	tp[1] = 1;
	dfs(1);
	
	for(ll i = 1 ; i <= n ; i++)
	{
		maxx[tp[i]] = max(maxx[tp[i]], IN[i]);
		st[i].insert({IN[i], m + 1});
		BIT.update(m + 1, 1);
	}
	
	ll p = m;
	
	for(ll i = 1 ; i <= q ; i++)
	{
		while(p > qry[i].L)
		{
			update(a[p - 1], a[p], p);
			p--;
		}
		
		ans[qry[i].num] = BIT.query(qry[i].R);
	}
	
	for(ll i = 1 ; i <= q ; i++)
		cout << ans[i] + 1 en;
	
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 4 ms 12636 KB Output is correct
3 Correct 4 ms 12656 KB Output is correct
4 Correct 124 ms 35000 KB Output is correct
5 Correct 114 ms 43344 KB Output is correct
6 Correct 136 ms 47656 KB Output is correct
7 Correct 183 ms 51796 KB Output is correct
8 Correct 203 ms 51904 KB Output is correct
9 Correct 187 ms 51644 KB Output is correct
10 Correct 177 ms 51792 KB Output is correct
11 Correct 193 ms 51744 KB Output is correct
12 Correct 135 ms 52052 KB Output is correct
13 Correct 133 ms 52104 KB Output is correct
14 Correct 145 ms 52016 KB Output is correct
15 Correct 65 ms 49044 KB Output is correct
16 Correct 203 ms 51300 KB Output is correct
17 Correct 31 ms 14752 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Incorrect 145 ms 30984 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 4 ms 12636 KB Output is correct
4 Correct 386 ms 34080 KB Output is correct
5 Correct 361 ms 36616 KB Output is correct
6 Correct 422 ms 45284 KB Output is correct
7 Correct 458 ms 48668 KB Output is correct
8 Correct 427 ms 48620 KB Output is correct
9 Correct 434 ms 48720 KB Output is correct
10 Correct 436 ms 48980 KB Output is correct
11 Correct 441 ms 48692 KB Output is correct
12 Correct 455 ms 48632 KB Output is correct
13 Correct 428 ms 48780 KB Output is correct
14 Correct 31 ms 14764 KB Output is correct

Subtask #6
0 / 41.0

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