oj.uz

Submission #934788

# Submission time Handle Problem Language Result Execution time Memory
934788 2024-02-28T02:33:24 Z Joshua_Andersson Inside information (BOI21_servers) C++14
50 / 100
 3500 ms 131236 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)].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 17504 KB Output is correct
2 Correct 47 ms 22532 KB Output is correct
3 Correct 44 ms 22792 KB Output is correct
4 Correct 60 ms 22788 KB Output is correct
5 Correct 67 ms 23292 KB Output is correct
6 Correct 43 ms 22788 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 17504 KB Output is correct
2 Correct 47 ms 22532 KB Output is correct
3 Correct 44 ms 22792 KB Output is correct
4 Correct 60 ms 22788 KB Output is correct
5 Correct 67 ms 23292 KB Output is correct
6 Correct 43 ms 22788 KB Output is correct
7 Correct 34 ms 18228 KB Output is correct
8 Incorrect 65 ms 22432 KB Extra information in the output file
9 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 17700 KB Output is correct
2 Correct 293 ms 105244 KB Output is correct
3 Correct 260 ms 105092 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 17700 KB Output is correct
2 Correct 293 ms 105244 KB Output is correct
3 Correct 260 ms 105092 KB Output is correct
4 Correct 38 ms 17676 KB Output is correct
5 Execution timed out 3547 ms 110120 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17716 KB Output is correct
2 Correct 637 ms 123068 KB Output is correct
3 Correct 635 ms 123128 KB Output is correct
4 Correct 664 ms 131212 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17716 KB Output is correct
2 Correct 637 ms 123068 KB Output is correct
3 Correct 635 ms 123128 KB Output is correct
4 Correct 664 ms 131212 KB Output is correct
5 Incorrect 30 ms 18368 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 31 ms 17664 KB Output is correct
2 Correct 372 ms 110968 KB Output is correct
3 Correct 411 ms 105276 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 17664 KB Output is correct
2 Correct 372 ms 110968 KB Output is correct
3 Correct 411 ms 105276 KB Output is correct
4 Correct 34 ms 18432 KB Output is correct
5 Incorrect 476 ms 116588 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 17664 KB Output is correct
2 Correct 659 ms 123104 KB Output is correct
3 Correct 642 ms 123080 KB Output is correct
4 Correct 669 ms 131236 KB Output is correct
5 Correct 33 ms 18436 KB Output is correct
6 Correct 358 ms 110964 KB Output is correct
7 Correct 461 ms 105420 KB Output is correct
8 Correct 630 ms 106672 KB Output is correct
9 Correct 582 ms 106696 KB Output is correct
10 Correct 1181 ms 115524 KB Output is correct
11 Correct 1244 ms 115672 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 17664 KB Output is correct
2 Correct 659 ms 123104 KB Output is correct
3 Correct 642 ms 123080 KB Output is correct
4 Correct 669 ms 131236 KB Output is correct
5 Correct 33 ms 18436 KB Output is correct
6 Correct 358 ms 110964 KB Output is correct
7 Correct 461 ms 105420 KB Output is correct
8 Correct 630 ms 106672 KB Output is correct
9 Correct 582 ms 106696 KB Output is correct
10 Correct 1181 ms 115524 KB Output is correct
11 Correct 1244 ms 115672 KB Output is correct
12 Incorrect 32 ms 18440 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 34 ms 17692 KB Output is correct
2 Correct 46 ms 22524 KB Output is correct
3 Correct 46 ms 22796 KB Output is correct
4 Correct 67 ms 22904 KB Output is correct
5 Correct 67 ms 23292 KB Output is correct
6 Correct 45 ms 22784 KB Output is correct
7 Correct 31 ms 18444 KB Output is correct
8 Correct 251 ms 106896 KB Output is correct
9 Correct 236 ms 106788 KB Output is correct
10 Correct 29 ms 18432 KB Output is correct
11 Correct 645 ms 123120 KB Output is correct
12 Correct 624 ms 122876 KB Output is correct
13 Correct 668 ms 131224 KB Output is correct
14 Correct 32 ms 18324 KB Output is correct
15 Correct 360 ms 111092 KB Output is correct
16 Correct 409 ms 105600 KB Output is correct
17 Correct 602 ms 106432 KB Output is correct
18 Correct 574 ms 106964 KB Output is correct
19 Correct 1118 ms 115728 KB Output is correct
20 Correct 1207 ms 115452 KB Output is correct
21 Correct 313 ms 108572 KB Output is correct
22 Correct 276 ms 108700 KB Output is correct
23 Correct 367 ms 109956 KB Output is correct
24 Correct 333 ms 109940 KB Output is correct
25 Correct 732 ms 112592 KB Output is correct
26 Correct 448 ms 106848 KB Output is correct
27 Correct 447 ms 106912 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 17692 KB Output is correct
2 Correct 46 ms 22524 KB Output is correct
3 Correct 46 ms 22796 KB Output is correct
4 Correct 67 ms 22904 KB Output is correct
5 Correct 67 ms 23292 KB Output is correct
6 Correct 45 ms 22784 KB Output is correct
7 Correct 31 ms 18444 KB Output is correct
8 Correct 251 ms 106896 KB Output is correct
9 Correct 236 ms 106788 KB Output is correct
10 Correct 29 ms 18432 KB Output is correct
11 Correct 645 ms 123120 KB Output is correct
12 Correct 624 ms 122876 KB Output is correct
13 Correct 668 ms 131224 KB Output is correct
14 Correct 32 ms 18324 KB Output is correct
15 Correct 360 ms 111092 KB Output is correct
16 Correct 409 ms 105600 KB Output is correct
17 Correct 602 ms 106432 KB Output is correct
18 Correct 574 ms 106964 KB Output is correct
19 Correct 1118 ms 115728 KB Output is correct
20 Correct 1207 ms 115452 KB Output is correct
21 Correct 313 ms 108572 KB Output is correct
22 Correct 276 ms 108700 KB Output is correct
23 Correct 367 ms 109956 KB Output is correct
24 Correct 333 ms 109940 KB Output is correct
25 Correct 732 ms 112592 KB Output is correct
26 Correct 448 ms 106848 KB Output is correct
27 Correct 447 ms 106912 KB Output is correct
28 Correct 35 ms 18436 KB Output is correct
29 Incorrect 67 ms 22880 KB Extra information in the output file
30 Halted 0 ms 0 KB -