oj.uz

Submission #934782

# Submission time Handle Problem Language Result Execution time Memory
934782 2024-02-28T02:27:23 Z Joshua_Andersson Inside information (BOI21_servers) C++14
37.5 / 100
 3500 ms 144320 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 41 ms 18340 KB Output is correct
2 Correct 65 ms 23288 KB Output is correct
3 Correct 51 ms 23036 KB Output is correct
4 Correct 112 ms 23516 KB Output is correct
5 Correct 99 ms 24160 KB Output is correct
6 Correct 45 ms 23028 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 18340 KB Output is correct
2 Correct 65 ms 23288 KB Output is correct
3 Correct 51 ms 23036 KB Output is correct
4 Correct 112 ms 23516 KB Output is correct
5 Correct 99 ms 24160 KB Output is correct
6 Correct 45 ms 23028 KB Output is correct
7 Correct 35 ms 18576 KB Output is correct
8 Correct 87 ms 22888 KB Output is correct
9 Correct 199 ms 23092 KB Output is correct
10 Correct 144 ms 23284 KB Output is correct
11 Correct 184 ms 23764 KB Output is correct
12 Correct 786 ms 23152 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 18428 KB Output is correct
2 Correct 374 ms 108024 KB Output is correct
3 Correct 354 ms 108040 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 18428 KB Output is correct
2 Correct 374 ms 108024 KB Output is correct
3 Correct 354 ms 108040 KB Output is correct
4 Correct 43 ms 18688 KB Output is correct
5 Execution timed out 3572 ms 112992 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 18552 KB Output is correct
2 Correct 2729 ms 139124 KB Output is correct
3 Correct 2704 ms 139064 KB Output is correct
4 Correct 2950 ms 139340 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 18552 KB Output is correct
2 Correct 2729 ms 139124 KB Output is correct
3 Correct 2704 ms 139064 KB Output is correct
4 Correct 2950 ms 139340 KB Output is correct
5 Correct 43 ms 18444 KB Output is correct
6 Correct 3047 ms 142640 KB Output is correct
7 Correct 3249 ms 144320 KB Output is correct
8 Correct 3160 ms 142048 KB Output is correct
9 Correct 3202 ms 143624 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 18440 KB Output is correct
2 Correct 2101 ms 119448 KB Output is correct
3 Correct 2199 ms 122944 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 18440 KB Output is correct
2 Correct 2101 ms 119448 KB Output is correct
3 Correct 2199 ms 122944 KB Output is correct
4 Correct 43 ms 18632 KB Output is correct
5 Correct 2217 ms 124480 KB Output is correct
6 Correct 2311 ms 125716 KB Output is correct

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 18368 KB Output is correct
2 Correct 2724 ms 139120 KB Output is correct
3 Correct 2699 ms 140252 KB Output is correct
4 Correct 2977 ms 140916 KB Output is correct
5 Correct 33 ms 18496 KB Output is correct
6 Correct 2101 ms 119228 KB Output is correct
7 Correct 2243 ms 122548 KB Output is correct
8 Correct 2252 ms 124744 KB Output is correct
9 Correct 2179 ms 125552 KB Output is correct
10 Execution timed out 3543 ms 133200 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 18368 KB Output is correct
2 Correct 2724 ms 139120 KB Output is correct
3 Correct 2699 ms 140252 KB Output is correct
4 Correct 2977 ms 140916 KB Output is correct
5 Correct 33 ms 18496 KB Output is correct
6 Correct 2101 ms 119228 KB Output is correct
7 Correct 2243 ms 122548 KB Output is correct
8 Correct 2252 ms 124744 KB Output is correct
9 Correct 2179 ms 125552 KB Output is correct
10 Execution timed out 3543 ms 133200 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 18444 KB Output is correct
2 Correct 64 ms 23204 KB Output is correct
3 Correct 53 ms 23200 KB Output is correct
4 Correct 96 ms 23476 KB Output is correct
5 Correct 101 ms 24316 KB Output is correct
6 Correct 55 ms 23292 KB Output is correct
7 Correct 36 ms 18548 KB Output is correct
8 Correct 338 ms 107876 KB Output is correct
9 Correct 328 ms 107968 KB Output is correct
10 Correct 28 ms 18684 KB Output is correct
11 Correct 2730 ms 140732 KB Output is correct
12 Correct 2679 ms 139956 KB Output is correct
13 Correct 2938 ms 140984 KB Output is correct
14 Correct 35 ms 18436 KB Output is correct
15 Correct 2086 ms 120740 KB Output is correct
16 Correct 2159 ms 121932 KB Output is correct
17 Correct 2207 ms 125816 KB Output is correct
18 Correct 2205 ms 124964 KB Output is correct
19 Execution timed out 3537 ms 132540 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 18444 KB Output is correct
2 Correct 64 ms 23204 KB Output is correct
3 Correct 53 ms 23200 KB Output is correct
4 Correct 96 ms 23476 KB Output is correct
5 Correct 101 ms 24316 KB Output is correct
6 Correct 55 ms 23292 KB Output is correct
7 Correct 36 ms 18548 KB Output is correct
8 Correct 338 ms 107876 KB Output is correct
9 Correct 328 ms 107968 KB Output is correct
10 Correct 28 ms 18684 KB Output is correct
11 Correct 2730 ms 140732 KB Output is correct
12 Correct 2679 ms 139956 KB Output is correct
13 Correct 2938 ms 140984 KB Output is correct
14 Correct 35 ms 18436 KB Output is correct
15 Correct 2086 ms 120740 KB Output is correct
16 Correct 2159 ms 121932 KB Output is correct
17 Correct 2207 ms 125816 KB Output is correct
18 Correct 2205 ms 124964 KB Output is correct
19 Execution timed out 3537 ms 132540 KB Time limit exceeded
20 Halted 0 ms 0 KB -