oj.uz

Submission #934789

# Submission time Handle Problem Language Result Execution time Memory
934789 2024-02-28T02:34:03 Z Joshua_Andersson Inside information (BOI21_servers) C++14
50 / 100
 1187 ms 129556 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)
		{
			if (pathgood(u, i, inf))
			{
				enableat[getmax(u, i)+1].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:315:7: warning: unused variable 's' [-Wunused-variable]
  315 |   int s = u;
      |       ^
servers.cpp: In function 'int main()':
servers.cpp:358:8: warning: variable 'prev' set but not used [-Wunused-but-set-variable]
  358 |    int prev = u;
      |        ^~~~
servers.cpp:312:7: warning: variable 'enable' set but not used [-Wunused-but-set-variable]
  312 |  auto enable = [&](int ind)
      |       ^~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 17668 KB Output is correct
2 Correct 47 ms 21512 KB Output is correct
3 Correct 43 ms 21804 KB Output is correct
4 Correct 59 ms 21760 KB Output is correct
5 Correct 71 ms 22136 KB Output is correct
6 Correct 41 ms 21664 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 17668 KB Output is correct
2 Correct 47 ms 21512 KB Output is correct
3 Correct 43 ms 21804 KB Output is correct
4 Correct 59 ms 21760 KB Output is correct
5 Correct 71 ms 22136 KB Output is correct
6 Correct 41 ms 21664 KB Output is correct
7 Incorrect 34 ms 17660 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 17532 KB Output is correct
2 Correct 252 ms 105176 KB Output is correct
3 Correct 250 ms 105196 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 17532 KB Output is correct
2 Correct 252 ms 105176 KB Output is correct
3 Correct 250 ms 105196 KB Output is correct
4 Incorrect 31 ms 17668 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 17700 KB Output is correct
2 Correct 693 ms 121144 KB Output is correct
3 Correct 654 ms 121364 KB Output is correct
4 Correct 681 ms 129468 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 17700 KB Output is correct
2 Correct 693 ms 121144 KB Output is correct
3 Correct 654 ms 121364 KB Output is correct
4 Correct 681 ms 129468 KB Output is correct
5 Incorrect 31 ms 17676 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 17668 KB Output is correct
2 Correct 376 ms 109456 KB Output is correct
3 Correct 413 ms 103484 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 17668 KB Output is correct
2 Correct 376 ms 109456 KB Output is correct
3 Correct 413 ms 103484 KB Output is correct
4 Incorrect 34 ms 17804 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 17672 KB Output is correct
2 Correct 646 ms 121196 KB Output is correct
3 Correct 646 ms 121064 KB Output is correct
4 Correct 667 ms 129556 KB Output is correct
5 Correct 34 ms 17660 KB Output is correct
6 Correct 372 ms 109036 KB Output is correct
7 Correct 409 ms 103528 KB Output is correct
8 Correct 583 ms 104692 KB Output is correct
9 Correct 611 ms 104948 KB Output is correct
10 Correct 1106 ms 113364 KB Output is correct
11 Correct 1187 ms 112388 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 17672 KB Output is correct
2 Correct 646 ms 121196 KB Output is correct
3 Correct 646 ms 121064 KB Output is correct
4 Correct 667 ms 129556 KB Output is correct
5 Correct 34 ms 17660 KB Output is correct
6 Correct 372 ms 109036 KB Output is correct
7 Correct 409 ms 103528 KB Output is correct
8 Correct 583 ms 104692 KB Output is correct
9 Correct 611 ms 104948 KB Output is correct
10 Correct 1106 ms 113364 KB Output is correct
11 Correct 1187 ms 112388 KB Output is correct
12 Incorrect 30 ms 17676 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 17672 KB Output is correct
2 Correct 47 ms 21524 KB Output is correct
3 Correct 45 ms 21772 KB Output is correct
4 Correct 58 ms 21716 KB Output is correct
5 Correct 70 ms 22324 KB Output is correct
6 Correct 42 ms 21764 KB Output is correct
7 Correct 36 ms 17528 KB Output is correct
8 Correct 287 ms 105116 KB Output is correct
9 Correct 236 ms 105116 KB Output is correct
10 Correct 28 ms 17660 KB Output is correct
11 Correct 643 ms 121292 KB Output is correct
12 Correct 680 ms 121092 KB Output is correct
13 Correct 659 ms 129420 KB Output is correct
14 Correct 32 ms 17628 KB Output is correct
15 Correct 361 ms 109200 KB Output is correct
16 Correct 432 ms 103740 KB Output is correct
17 Correct 575 ms 105156 KB Output is correct
18 Correct 604 ms 104704 KB Output is correct
19 Correct 1141 ms 113328 KB Output is correct
20 Correct 1155 ms 112248 KB Output is correct
21 Correct 277 ms 105080 KB Output is correct
22 Correct 265 ms 105364 KB Output is correct
23 Correct 352 ms 106356 KB Output is correct
24 Correct 330 ms 106320 KB Output is correct
25 Correct 723 ms 109172 KB Output is correct
26 Correct 435 ms 103396 KB Output is correct
27 Correct 424 ms 103512 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 17672 KB Output is correct
2 Correct 47 ms 21524 KB Output is correct
3 Correct 45 ms 21772 KB Output is correct
4 Correct 58 ms 21716 KB Output is correct
5 Correct 70 ms 22324 KB Output is correct
6 Correct 42 ms 21764 KB Output is correct
7 Correct 36 ms 17528 KB Output is correct
8 Correct 287 ms 105116 KB Output is correct
9 Correct 236 ms 105116 KB Output is correct
10 Correct 28 ms 17660 KB Output is correct
11 Correct 643 ms 121292 KB Output is correct
12 Correct 680 ms 121092 KB Output is correct
13 Correct 659 ms 129420 KB Output is correct
14 Correct 32 ms 17628 KB Output is correct
15 Correct 361 ms 109200 KB Output is correct
16 Correct 432 ms 103740 KB Output is correct
17 Correct 575 ms 105156 KB Output is correct
18 Correct 604 ms 104704 KB Output is correct
19 Correct 1141 ms 113328 KB Output is correct
20 Correct 1155 ms 112248 KB Output is correct
21 Correct 277 ms 105080 KB Output is correct
22 Correct 265 ms 105364 KB Output is correct
23 Correct 352 ms 106356 KB Output is correct
24 Correct 330 ms 106320 KB Output is correct
25 Correct 723 ms 109172 KB Output is correct
26 Correct 435 ms 103396 KB Output is correct
27 Correct 424 ms 103512 KB Output is correct
28 Incorrect 34 ms 17676 KB Extra information in the output file
29 Halted 0 ms 0 KB -