제출 #311585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
311585		arwaeystoamneg	Regions (IOI09_regions)	C++17	90 / 100	8087 ms	84312 KiB

regions

/*
ID: awesome35
LANG: C++14
TASK: vans
*/
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
//#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pq priority_queue
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353
const ld pi = 3.1415926535;

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void build_primes(vi& primes, int size)
{
	vi visited;
	visited.rsz(size, 0);
	FOR(i, 2, size)
	{
		if (visited[i] == 0)
		{
			primes.pb(i);
			int a = i;
			while (a < size)
			{
				visited[a] = 1;
				a += i;
			}
		}
	}
}
vector<vector<ll>> matrix_mult(vector<vector<ll>>& a, vector<vector<ll>>& b)
{
	int n = a.size();
	vector<vector<ll>> answer;
	answer.resize(n);
	for (int i = 0; i < n; i++) answer[i].resize(n, 0);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++) // calculate answer[i][j]
		{
			for (int k = 0; k < n; k++)
				answer[i][j] = (answer[i][j] + a[i][k] * b[k][j]) % inf;
		}
	}
	return answer;
}
int modInverse(int a, int m)
{
	int m0 = m;
	int y = 0, x = 1;
	if (m == 1)
		return 0;
	while (a > 1)
	{
		// q is quotient 
		int q = a / m;
		int t = m;
		// m is remainder now, process same as 
		// Euclid's algo 
		m = a % m, a = t;
		t = y;
		// Update y and x 
		y = x - q * y;
		x = t;
	}
	// Make x positive 
	if (x < 0)
		x += m0;

	return x;
}
ll power(ll x, ll y)
{
	ll k = 1LL << 60;
	ll z = 1;
	while (k != 0)
	{
		z *= z;
		z %= inf;
		if (y >= k)
		{
			z *= x;
			z %= inf;
			y -= k;
		}
		k >>= 1;
	}
	return z;
}
struct point
{
	ld x, y;
	bool operator<(const point& rhs)const
	{
		if (x == rhs.x)return y < rhs.y;
		return x < rhs.x;
	}
};
struct pt
{
	ll x, y;
	bool operator<(const point& rhs)const
	{
		if (x == rhs.x)return y < rhs.y;
		return x < rhs.x;
	}
};
// remember that you need to take abs
long double area(point x, point y, point z)
{
	return (x.y * y.x + y.y * z.x + z.y * x.x - x.x * y.y - y.x * z.y - z.x * x.y) / 2.0;
}
bool clockwise(point x, point y, point z)
{
	return area(x, y, z) > 0;
}
// remember that you need to take abs
long double area(pt x, pt y, pt z)
{
	return (x.y * y.x + y.y * z.x + z.y * x.x - x.x * y.y - y.x * z.y - z.x * x.y) / 2.0;
}
bool clockwise(pt x, pt y, pt z)
{
	return area(x, y, z) > 0;
}
ll gcd(ll a, ll b)
{
	if (a > b)swap(a, b);
	if (a == 0)return b;
	return gcd(a, b % a);
}
int popcount(ll a)
{
	int count = 0;
	while (a)
	{
		count += (a & 1);
		a >>= 1;
	}
	return count;
}
ll choose(ll n, ll r)
{
	ll p = 1, k = 1;
	if (n - r < r)
		r = n - r;
	if (r != 0) {
		while (r) {
			p *= n;
			k *= r;
			long long m = gcd(p, k);
			p /= m;
			k /= m;
			n--;
			r--;
		}
	}
	else
		p = 1;
	return p;
}
vll prefix_hash(string& a, vll& powers)
{
	int n = sz(a);
	vll prefix(n + 1);
	F0R(i, n)prefix[i + 1] = (prefix[i] + powers[i] * (a[i] - 'a' + 1)) % inf;
	return prefix;
}
struct custom_hash {
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
	//the return type was size_t. But isnt that problematic?
	uint64_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};
struct custom_hash_fast {
	//the return type was size_t. But isnt that problematic?
	uint64_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		x ^= FIXED_RANDOM;
		return x ^ (x >> 16);
	}
};
struct node
{
	int tin, tout, index;
	bool operator<(const node& x)const
	{
		return tin < x.tin;
	}
};
class segment_tree
{
	struct item
	{
		vi tout;
	};
	item single(node i)
	{
		return { {i.tout} };
	}
	item merge(item& x, item& y)
	{
		item ans;
		int i = 0, j = 0;
		while (i < sz(x.tout) || j < sz(y.tout))
		{
			if (j == sz(y.tout))
			{
				ans.tout.pb(x.tout[i]);
				i++;
			}
			else if (i == sz(x.tout))
			{
				ans.tout.pb(y.tout[j]);
				j++;
			}
			else
			{
				if (x.tout[i] < y.tout[j])
				{
					ans.tout.pb(x.tout[i]);
					i++;
				}
				else
				{
					ans.tout.pb(y.tout[j]);
					j++;
				}
			}
		}
		return ans;
	}
	vector<item> tree;
	vector<item>A;
	int height;
	item neutral = { {} };
public:void build(vector<node>& B)
{
	int	n = B.size();
	height = log2(n) + 1;
	A.rsz(n);
	tree.rsz((1 << height + 1) - 1);
	F0R(i, n)A[i] = single(B[i]);
	A.rsz(1 << height, neutral);
	build(A, 0, 0, (1 << height) - 1);
}
	   void build(vector<item>& A, int v, int tl, int tr)
	   {
		   if (tl == tr)
			   tree[v] = A[tl];
		   else
		   {
			   int mid = (tl + tr) / 2;
			   build(A, 2 * v + 1, tl, mid);
			   build(A, 2 * v + 2, mid + 1, tr);
			   tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
		   }
	   }
	   ll calc(vi& a, int tout)
	   {
		   return upper_bound(all(a), tout) - a.begin();
	   }
	   ll calc1(vi& a, int tout)
	   {
		   return sz(a) - (upper_bound(all(a), tout) - a.begin());
	   }
public:ll query(int l, int r, int tout)
{
//	item ans = query(0, 0, (1 << height) - 1, l, r);
	//return upper_bound(all(ans.tout), tout) - ans.tout.begin();
	return query(0, 0, (1 << height) - 1, l, r, tout);
}
public:ll query1(int l, int r, int tout)
{
	 return query1(0, 0, (1 << height) - 1, l, r, tout);
}
	   ll query(int v, int tl, int tr, int l, int r, int tout)
	   {
		   if (r<tl || l>tr)return 0;
		   if (l <= tl && r >= tr)
		   {
			   return calc(tree[v].tout, tout);
		   }
		   int mid = (tl + tr) / 2;
		   return query(2 * v + 1, tl, mid, l, r, tout) + query(2 * v + 2, mid + 1, tr, l, r, tout);
	   }
	   ll query1(int v, int tl, int tr, int l, int r, int tout)
	   {
		   if (r<tl || l>tr)return 0;
		   if (l <= tl && r >= tr)
		   {
			   return calc1(tree[v].tout, tout);
		   }
		   int mid = (tl + tr) / 2;
		   return query1(2 * v + 1, tl, mid, l, r, tout) + query1(2 * v + 2, mid + 1, tr, l, r, tout);
	   }
};
//end of preprogrammed methods
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	//freopen((s + ".in").c_str(), "r", stdin);
	//freopen((s + ".out").c_str(), "w", stdout);
}
int n, k, q;
vector<vi>adj;
vi types, tin, tout, sizes, order, indexs;
int timenow;
void dfs(int i, int p)
{
	order.pb(i);
	sizes[i] = 1;
	tin[i] = timenow++;
	trav(x, adj[i])
	{
		if (x != p)
		{
			dfs(x, i);
			sizes[i] += sizes[x];
		}
	}
	tout[i] = timenow++;
}
vector<vector<node>> val;
vector<segment_tree>sum;
vector<unordered_map<int, ll>>ans;
ll solve(int a, int b)
{
	if (sz(val[a]) < sz(val[b]))
	{
		ll total = 0;
		trav(x, val[a])
		{
			int index = upper_bound(all(val[b]), x) - val[b].begin();
			total += sum[b].query(index, sz(val[b]) - 1, x.tout);
		}
		ans[a].insert({ b,total });
		return total;
	}
	else
	{
		ll total = 0;
		trav(x, val[b])
		{
			int index = upper_bound(all(val[a]), x) - val[a].begin() - 1;
			if (index != -1)
			{
				total += sum[a].query1(0, index, x.tout);
			}
		}
		ans[a].insert({ b,total });
		return total;
	}
}
int main()
{
	setIO("snowcow");
	cin >> n >> k >> q;
	adj.rsz(n);
	types.rsz(n);
	cin >> types[0];
	types[0]--;
	F0R(i, n - 1)
	{
		int a, b;
		cin >> a >> b;
		types[i + 1] = b - 1;
		adj[--a].pb(i + 1);
		adj[i + 1].pb(a);
	}
	tin.rsz(n);
	tout.rsz(n);
	sizes.rsz(n);
	dfs(0, -1);
	indexs.rsz(n);
	F0R(i, n)indexs[order[i]] = i;
	val.rsz(k);
	F0R(i, n)val[types[i]].pb({ tin[i],tout[i],i });
	F0R(i, k)sort(all(val[i]));
	sum.rsz(k);
	F0R(i, k)
	{
		sum[i].build(val[i]);
	}
	ans.rsz(k);
	F0R(i, q)
	{
		int a, b;
		cin >> a >> b;
		a--; b--;
		if (ans[a].count(b))
			cout << ans[a][b] << endl;
		else
			cout << solve(a, b) << endl;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

regions.cpp: In member function 'void segment_tree::build(std::vector<node>&)':
regions.cpp:285:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  285 |  tree.rsz((1 << height + 1) - 1);
      |                 ~~~~~~~^~~

• Subtask 1: 15 / 15
• Subtask 2: 75 / 85