oj.uz

Submission #934243

# Submission time Handle Problem Language Result Execution time Memory
934243 2024-02-27T03:29:58 Z Joshua_Andersson Inside information (BOI21_servers) C++14
50 / 100
 3500 ms 120072 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];
int cnt[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);

	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(u,centroidpar[u],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)
			{
				enable(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)) break;
				ans+=depth[u]+depth[prev]-2*depth[lca(u,prev)];
				int v = getmin(a, u);
				repe(c, children[u]) if (c.first > v) ans += c.second;
				if (u == 0)
				{
					break;
				}
			}

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

	return 0;
}

Compilation message

servers.cpp: In constructor 'Centroid::Centroid(vvi&)':
servers.cpp:120:6: warning: 'Centroid::edges' will be initialized after [-Wreorder]
  120 |  vvi edges;
      |      ^~~~~
servers.cpp:119:6: warning:   'int Centroid::n' [-Wreorder]
  119 |  int n;
      |      ^
servers.cpp:126:2: warning:   when initialized here [-Wreorder]
  126 |  Centroid(vvi& edges) : edges(edges), n(edges.size()), vis(n), par(n), size(n)
      |  ^~~~~~~~
servers.cpp: In lambda function:
servers.cpp:299:7: warning: unused variable 's' [-Wunused-variable]
  299 |   int s = u;
      |       ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 20476 KB Output is correct
2 Correct 45 ms 25084 KB Output is correct
3 Correct 51 ms 24920 KB Output is correct
4 Correct 52 ms 25088 KB Output is correct
5 Correct 63 ms 25336 KB Output is correct
6 Correct 42 ms 24844 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 20476 KB Output is correct
2 Correct 45 ms 25084 KB Output is correct
3 Correct 51 ms 24920 KB Output is correct
4 Correct 52 ms 25088 KB Output is correct
5 Correct 63 ms 25336 KB Output is correct
6 Correct 42 ms 24844 KB Output is correct
7 Incorrect 33 ms 20732 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 32 ms 20480 KB Output is correct
2 Correct 231 ms 103660 KB Output is correct
3 Correct 219 ms 103660 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 20480 KB Output is correct
2 Correct 231 ms 103660 KB Output is correct
3 Correct 219 ms 103660 KB Output is correct
4 Correct 33 ms 20620 KB Output is correct
5 Execution timed out 3544 ms 105696 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 20484 KB Output is correct
2 Correct 309 ms 119964 KB Output is correct
3 Correct 331 ms 119872 KB Output is correct
4 Correct 277 ms 119900 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 20484 KB Output is correct
2 Correct 309 ms 119964 KB Output is correct
3 Correct 331 ms 119872 KB Output is correct
4 Correct 277 ms 119900 KB Output is correct
5 Incorrect 29 ms 20484 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 20488 KB Output is correct
2 Correct 235 ms 102004 KB Output is correct
3 Correct 315 ms 102076 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 20488 KB Output is correct
2 Correct 235 ms 102004 KB Output is correct
3 Correct 315 ms 102076 KB Output is correct
4 Incorrect 33 ms 20492 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 31 ms 20480 KB Output is correct
2 Correct 329 ms 119972 KB Output is correct
3 Correct 303 ms 119928 KB Output is correct
4 Correct 261 ms 120008 KB Output is correct
5 Correct 32 ms 20480 KB Output is correct
6 Correct 205 ms 102008 KB Output is correct
7 Correct 303 ms 101948 KB Output is correct
8 Correct 332 ms 103180 KB Output is correct
9 Correct 323 ms 103348 KB Output is correct
10 Correct 361 ms 109160 KB Output is correct
11 Correct 431 ms 107728 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 20480 KB Output is correct
2 Correct 329 ms 119972 KB Output is correct
3 Correct 303 ms 119928 KB Output is correct
4 Correct 261 ms 120008 KB Output is correct
5 Correct 32 ms 20480 KB Output is correct
6 Correct 205 ms 102008 KB Output is correct
7 Correct 303 ms 101948 KB Output is correct
8 Correct 332 ms 103180 KB Output is correct
9 Correct 323 ms 103348 KB Output is correct
10 Correct 361 ms 109160 KB Output is correct
11 Correct 431 ms 107728 KB Output is correct
12 Incorrect 30 ms 20484 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 20480 KB Output is correct
2 Correct 46 ms 24828 KB Output is correct
3 Correct 51 ms 25092 KB Output is correct
4 Correct 51 ms 24940 KB Output is correct
5 Correct 61 ms 25528 KB Output is correct
6 Correct 43 ms 24928 KB Output is correct
7 Correct 31 ms 20580 KB Output is correct
8 Correct 241 ms 103660 KB Output is correct
9 Correct 219 ms 103696 KB Output is correct
10 Correct 30 ms 20632 KB Output is correct
11 Correct 300 ms 120060 KB Output is correct
12 Correct 303 ms 119732 KB Output is correct
13 Correct 281 ms 120072 KB Output is correct
14 Correct 32 ms 20492 KB Output is correct
15 Correct 245 ms 102036 KB Output is correct
16 Correct 293 ms 101872 KB Output is correct
17 Correct 326 ms 103356 KB Output is correct
18 Correct 341 ms 103356 KB Output is correct
19 Correct 344 ms 109212 KB Output is correct
20 Correct 403 ms 107668 KB Output is correct
21 Correct 232 ms 104044 KB Output is correct
22 Correct 255 ms 104568 KB Output is correct
23 Correct 285 ms 105036 KB Output is correct
24 Correct 255 ms 104872 KB Output is correct
25 Correct 367 ms 107892 KB Output is correct
26 Correct 301 ms 102400 KB Output is correct
27 Correct 256 ms 102332 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 20480 KB Output is correct
2 Correct 46 ms 24828 KB Output is correct
3 Correct 51 ms 25092 KB Output is correct
4 Correct 51 ms 24940 KB Output is correct
5 Correct 61 ms 25528 KB Output is correct
6 Correct 43 ms 24928 KB Output is correct
7 Correct 31 ms 20580 KB Output is correct
8 Correct 241 ms 103660 KB Output is correct
9 Correct 219 ms 103696 KB Output is correct
10 Correct 30 ms 20632 KB Output is correct
11 Correct 300 ms 120060 KB Output is correct
12 Correct 303 ms 119732 KB Output is correct
13 Correct 281 ms 120072 KB Output is correct
14 Correct 32 ms 20492 KB Output is correct
15 Correct 245 ms 102036 KB Output is correct
16 Correct 293 ms 101872 KB Output is correct
17 Correct 326 ms 103356 KB Output is correct
18 Correct 341 ms 103356 KB Output is correct
19 Correct 344 ms 109212 KB Output is correct
20 Correct 403 ms 107668 KB Output is correct
21 Correct 232 ms 104044 KB Output is correct
22 Correct 255 ms 104568 KB Output is correct
23 Correct 285 ms 105036 KB Output is correct
24 Correct 255 ms 104872 KB Output is correct
25 Correct 367 ms 107892 KB Output is correct
26 Correct 301 ms 102400 KB Output is correct
27 Correct 256 ms 102332 KB Output is correct
28 Incorrect 33 ms 20484 KB Extra information in the output file
29 Halted 0 ms 0 KB -