oj.uz

Submission #923090

# Submission time Handle Problem Language Result Execution time Memory
923090 2024-02-06T14:52:06 Z denniskim Tourism (JOI23_tourism) C++17
0 / 100
 362 ms 96592 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[1000010];
gujo qry[1000010];
ll a[1000010];
ll IN[1000010], OUT[1000010], cc;
ll spa[1000010][21], dep[1000010], siz[1000010];
ll tp[1000010];
set<pll> st[1000010];
ll maxx[1000010];
ll ans[1000010];

struct fenwicktree
{
	ll bit[100010];
	
	void update(ll w, ll v)
	{
		for(ll i = w ; i <= cc + 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];
	//cout << "map update : " << num sp << X sp << Y sp << Z en;
	
	///cout << "map now\n";
	
	//for(auto &i : st[num])
	//	cout << i.fi sp << i.se en;
	
	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;
		}
	}
	
	//cout << "vv\n";
	
	//for(auto &i : vv)
	//	cout << i.fi.fi sp << i.se en;
	
	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)
{
	//cout << "start : " << X sp << Y sp << Z en;
	while(tp[X] != tp[Y])
	{
		if(dep[tp[X]] < dep[tp[Y]])
			swap(X, Y);
		//cout << "update : " << tp[X] sp << X en;
		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);
	//cout << "update : " << tp2 sp << X en;
	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], cc + 1});
		BIT.update(cc + 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 30 ms 70744 KB Output is correct
2 Correct 31 ms 70744 KB Output is correct
3 Correct 30 ms 70748 KB Output is correct
4 Incorrect 34 ms 70996 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 70744 KB Output is correct
2 Correct 31 ms 70744 KB Output is correct
3 Correct 30 ms 70748 KB Output is correct
4 Incorrect 34 ms 70996 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 70744 KB Output is correct
2 Correct 30 ms 71004 KB Output is correct
3 Correct 32 ms 71080 KB Output is correct
4 Incorrect 154 ms 96592 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 70748 KB Output is correct
2 Incorrect 186 ms 90448 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 70748 KB Output is correct
2 Correct 30 ms 70916 KB Output is correct
3 Correct 31 ms 71016 KB Output is correct
4 Incorrect 362 ms 96376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 70744 KB Output is correct
2 Correct 31 ms 70744 KB Output is correct
3 Correct 30 ms 70748 KB Output is correct
4 Incorrect 34 ms 70996 KB Output isn't correct
5 Halted 0 ms 0 KB -