Submission #934782

#	Time	Username	Problem	Language	Result	Execution time	Memory
934782		Joshua_Andersson	Inside information (BOI21_servers)	C++14	37.50 / 100	3572 ms	144320 KiB

servers

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
//#define int ll
const int inf = int(1e9);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)
#define ceildiv(x,y) ((x + y - 1) / (y))

inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

#define _LOCAL _DEBUG
#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif

const int maxn = int(1.5e5);
int tin[maxn];
int tout[maxn];
int timer = 0;
int up[maxn][18];
bool upincreasing[maxn][18];
bool updecreasing[maxn][18];
int upmax[maxn][18];
int upmin[maxn][18];
int upv[maxn];
int depth[maxn];

void dfs(int u, int p, int p1, int _p2, vector<vector<p2>>& edges)
{
	depth[u] = depth[p] + 1;
	tin[u] = timer++;
	up[u][0] = p;
	upmax[u][0] = upv[u];
	upmin[u][0] = upv[u];
	upincreasing[u][0] = upmax[u][0] < upmax[p][0] || p==0 || u==0;
	updecreasing[u][0] = upmax[u][0] > upmax[p][0] || p==0 || u==0;
	repp(d,1,18)
	{
		int mid = up[u][d - 1];
		up[u][d] = up[mid][d - 1];
		upmax[u][d] = max(upmax[u][d - 1], upmax[mid][d - 1]);
		upmin[u][d] = min(upmin[u][d - 1], upmin[mid][d - 1]);
		upincreasing[u][d] = upincreasing[u][d - 1] && upincreasing[mid][d - 1] && (upmax[mid][0] < upmax[up[mid][0]][0] || up[mid][0] ==0||mid==0);
		updecreasing[u][d] = updecreasing[u][d - 1] && updecreasing[mid][d - 1] && (upmax[mid][0] > upmax[up[mid][0]][0] || up[mid][0] ==0||mid==0);
	}
	

	repe(e, edges[u]) if (e.first != p)
	{
		upv[e.first] = e.second;
		dfs(e.first, u, p1, _p2, edges);
	}

	tout[u] = timer++;
}

bool isancestor(int a, int b)
{
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int pathmax(int a, int b)
{
	if (isancestor(a, b)) return -1;
	int ret = -1;
	for (int d = 17; d >= 0; d--)
	{
		if (!isancestor(up[a][d], b))
		{
			ret = max(ret, upmax[a][d]);
			a = up[a][d];
		}
	}
	return max(ret, upmax[a][0]);
}

int pathmin(int a, int b)
{
	if (isancestor(a, b)) return inf;
	int ret = inf;
	for (int d = 17; d >= 0; d--)
	{
		if (!isancestor(up[a][d], b))
		{
			ret = min(ret, upmin[a][d]);
			a = up[a][d];
		}
	}
	return min(ret, upmin[a][0]);
}

int lca(int a, int b)
{
	if (isancestor(a, b)) return a;
	if (isancestor(b, a)) return b;
	for (int d = 17; d >= 0; d--)
	{
		if (!isancestor(up[a][d],b))
		{
			a = up[a][d];
		}
	}
	return up[a][0];
}

struct Centroid
{
	int n;
	vvi edges;
	vi vis;
	vi par;
	vi size;

	Centroid() {}
	Centroid(vvi& edges) : edges(edges), n(edges.size()), vis(n), par(n), size(n)
	{
		init_centroid(0, -1);
	}

	int find_centroid(int u, int p, int n)
	{
		repe(e, edges[u])
		{
			if (e == p) continue;
			if (!vis[e] && size[e] > n / 2) return find_centroid(e, u, n);
		}
		return u;
	}

	int find_size(int u, int p)
	{
		if (vis[u]) return 0;
		size[u] = 1;

		repe(e, edges[u])
		{
			if (e == p) continue;
			size[u] += find_size(e, u);
		}
		return size[u];
	}

	void init_centroid(int u, int p)
	{
		find_size(u, u);

		int c = find_centroid(u, u, size[u]);
		vis[c] = 1;
		par[c] = p;

		repe(e, edges[c])
		{
			if (!vis[e]) init_centroid(e, c);
		}
	}
};

int cdepth[maxn];
void d(int u, int p, vvi& adj)
{
	cdepth[u] = cdepth[p] + 1;
	repe(e, adj[u]) if (e != p) d(e, u, adj);
}

signed main()
{
	fast();

	//ifstream in("C:\\Users\\Matis\\desktop\\comp_prog\\x64\\debug\\in.txt");
	//cin.rdbuf(in.rdbuf());

	int n, q;
	cin >> n >> q;

	vvi queries;
	int t = 0;
	vector<vector<p2>> edges(n);
	vector<p2> edgelist;
	vvi e(n);
	rep(i, n + q - 1)
	{
		char c;
		cin >> c;
		if (c=='S')
		{
			int a, b;
			cin >> a >> b;
			a--; b--;
			edgelist.push_back(p2(a, b));
			edges[a].push_back(p2(b, t));
			edges[b].push_back(p2(a, t));
			e[a].push_back(b);
			e[b].push_back(a);
			t++;
		}
		else if (c=='Q')
		{
			int a, b;
			cin >> a >> b;
			a--; b--;
			queries.push_back({ 0, b, a, t-1 });
		}
		else
		{
			int c;
			cin >> c;
			c--;
			queries.push_back({ 1, c, -1, t-1 });
		}
	}
	depth[0] = 0;
	dfs(0, 0, -1, -1, edges);
	Centroid cent(e);

	auto getmax = [&](int a, int b)
	{
		return max(pathmax(a, b), pathmax(b, a));
	};
	
	auto getmin = [&](int a, int b)
	{
		return min(pathmin(a, b), pathmin(b, a));
	};

	auto pathgood = [&](int a, int b, int t)
	{
		if (getmax(a, b) > t) return false;
		// all edges <= t
		// from b->lca increasing
		// from a->lca decreasing
		bool good = 1;
		int u = b;
		int prev = inf;
		for (int d = 17; d >= 0; d--)
		{
			if (!isancestor(up[u][d],a))
			{
				good &= updecreasing[u][d];
				u = up[u][d];
			}
		}
		if (!isancestor(u,a))
		{
			prev = upmax[u][0];
		}
		

		u = a;
		int v = -1;
		for (int d = 17; d >= 0; d--)
		{
			if (!isancestor(up[u][d], b))
			{
				good &= upincreasing[u][d];
				u = up[u][d];
			}
		}
		if (!isancestor(u, b))
		{
			v = upmax[u][0];
		}

		return good && (v < prev);
	};

	vector<map<int,int>> children(n);
	vi sum(n);
	vvi blocked(n);
	rep(i, n)blocked[i].push_back(inf);
	vi parenton(n);
	vi centroidpar = cent.par;
	vvi centroidadj(n);
	rep(i, n)
	{
		if (centroidpar[i] == -1) continue;
		centroidadj[i].push_back(centroidpar[i]);
		centroidadj[centroidpar[i]].push_back(i);
	}
	Centroid c2(e);
	c2.vis = vi(n); c2.par = vi(n); c2.size = vi(n);
	c2.find_size(0, 0);
	int center = c2.find_centroid(0, 0, c2.size[0]);
	d(center, center, centroidadj);

	vector<vector<p2>> enableat(n + 2);
	rep(i, n)
	{
		int u = centroidpar[i];
		int prev = i;
		while (u!=-1)
		{
			int lo = -1;
			int hi = n + 1;
			while (lo+1<hi)
			{
				int mid = (lo + hi) / 2;
				if (pathgood(u, i, mid)) hi = mid;
				else lo = mid;
			}
			enableat[hi].emplace_back(prev, getmin(i, u));
			prev = u;
			u = centroidpar[u];
		}
	}

	auto enable = [&](int ind)
	{
		int u = cdepth[edgelist[ind].first] > cdepth[edgelist[ind].second] ? edgelist[ind].first : edgelist[ind].second;
		int s = u;
		while (true)
		{
			if (centroidpar[u] == -1) break;
			//if (!pathgood(centroidpar[u],s,ind)) break;
			int pe = getmin(u, centroidpar[u]);
			repe(c, blocked[u])
			{
				if (c>pe)
				{
					children[centroidpar[u]][pe]++;
					blocked[centroidpar[u]].push_back(pe);
				}
			}
			blocked[u] = vi();
			u = centroidpar[u];
		}
	};

	int timer = 0;
	repe(q, queries)
	{
		int type=q[0], a=q[1], b=q[2], t=q[3];
		
		if (type==0)
		{
			cout << (pathgood(a, b, t) ? "yes" : "no") << "\n";
		}
		else
		{
			
			while (timer<=t)
			{
				repe(e, enableat[timer])
				{
					children[centroidpar[e.first]][e.second]++;
				}
				timer++;
			}
			
			int ans = 0;
			repe(c, children[a]) ans += c.second;
			int u=a;
			int prev = u;
			while (u!=center)
			{
				prev = u;
				u = centroidpar[u];
				if (pathgood(a, u, t))
				{
					ans++;// = depth[u] + depth[prev] - 2 * depth[lca(u, prev)];
					int v = getmax(a, u);
					repe(c, children[u]) if (c.first > v) ans += c.second;
				}
				
			}

			cout << ans+1 << "\n";
		}
	}

	return 0;
}

Compilation message (stderr)

servers.cpp: In constructor 'Centroid::Centroid(vvi&)':
servers.cpp:119:6: warning: 'Centroid::edges' will be initialized after [-Wreorder]
  119 |  vvi edges;
      |      ^~~~~
servers.cpp:118:6: warning:   'int Centroid::n' [-Wreorder]
  118 |  int n;
      |      ^
servers.cpp:125:2: warning:   when initialized here [-Wreorder]
  125 |  Centroid(vvi& edges) : edges(edges), n(edges.size()), vis(n), par(n), size(n)
      |  ^~~~~~~~
servers.cpp: In lambda function:
servers.cpp:319:7: warning: unused variable 's' [-Wunused-variable]
  319 |   int s = u;
      |       ^
servers.cpp: In function 'int main()':
servers.cpp:362:8: warning: variable 'prev' set but not used [-Wunused-but-set-variable]
  362 |    int prev = u;
      |        ^~~~
servers.cpp:316:7: warning: variable 'enable' set but not used [-Wunused-but-set-variable]
  316 |  auto enable = [&](int ind)
      |       ^~~~~~

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5