oj.uz

Submission #934240

# Submission time Handle Problem Language Result Execution time Memory
934240 2024-02-27T03:25:04 Z Joshua_Andersson Inside information (BOI21_servers) C++14
50 / 100
 3500 ms 120436 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(s,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)
      |  ^~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 20732 KB Output is correct
2 Correct 46 ms 24836 KB Output is correct
3 Correct 48 ms 24900 KB Output is correct
4 Correct 67 ms 25084 KB Output is correct
5 Correct 64 ms 25340 KB Output is correct
6 Correct 43 ms 24928 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 20732 KB Output is correct
2 Correct 46 ms 24836 KB Output is correct
3 Correct 48 ms 24900 KB Output is correct
4 Correct 67 ms 25084 KB Output is correct
5 Correct 64 ms 25340 KB Output is correct
6 Correct 43 ms 24928 KB Output is correct
7 Incorrect 34 ms 20496 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 243 ms 103912 KB Output is correct
3 Correct 230 ms 103912 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 243 ms 103912 KB Output is correct
3 Correct 230 ms 103912 KB Output is correct
4 Correct 37 ms 20732 KB Output is correct
5 Execution timed out 3533 ms 106100 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 20492 KB Output is correct
2 Correct 321 ms 120280 KB Output is correct
3 Correct 311 ms 120256 KB Output is correct
4 Correct 259 ms 120328 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 20492 KB Output is correct
2 Correct 321 ms 120280 KB Output is correct
3 Correct 311 ms 120256 KB Output is correct
4 Correct 259 ms 120328 KB Output is correct
5 Incorrect 32 ms 20480 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 33 ms 20484 KB Output is correct
2 Correct 250 ms 102316 KB Output is correct
3 Correct 280 ms 102460 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 20484 KB Output is correct
2 Correct 250 ms 102316 KB Output is correct
3 Correct 280 ms 102460 KB Output is correct
4 Incorrect 37 ms 20556 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 41 ms 20752 KB Output is correct
2 Correct 300 ms 120184 KB Output is correct
3 Correct 337 ms 120192 KB Output is correct
4 Correct 278 ms 120284 KB Output is correct
5 Correct 32 ms 20732 KB Output is correct
6 Correct 205 ms 102496 KB Output is correct
7 Correct 269 ms 102368 KB Output is correct
8 Correct 449 ms 103872 KB Output is correct
9 Correct 321 ms 103844 KB Output is correct
10 Correct 367 ms 109432 KB Output is correct
11 Correct 402 ms 108176 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 20752 KB Output is correct
2 Correct 300 ms 120184 KB Output is correct
3 Correct 337 ms 120192 KB Output is correct
4 Correct 278 ms 120284 KB Output is correct
5 Correct 32 ms 20732 KB Output is correct
6 Correct 205 ms 102496 KB Output is correct
7 Correct 269 ms 102368 KB Output is correct
8 Correct 449 ms 103872 KB Output is correct
9 Correct 321 ms 103844 KB Output is correct
10 Correct 367 ms 109432 KB Output is correct
11 Correct 402 ms 108176 KB Output is correct
12 Incorrect 30 ms 20488 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 37 ms 20800 KB Output is correct
2 Correct 45 ms 24836 KB Output is correct
3 Correct 59 ms 25088 KB Output is correct
4 Correct 60 ms 25084 KB Output is correct
5 Correct 65 ms 25344 KB Output is correct
6 Correct 42 ms 24836 KB Output is correct
7 Correct 32 ms 20488 KB Output is correct
8 Correct 222 ms 104156 KB Output is correct
9 Correct 228 ms 103912 KB Output is correct
10 Correct 30 ms 20480 KB Output is correct
11 Correct 326 ms 120436 KB Output is correct
12 Correct 328 ms 120304 KB Output is correct
13 Correct 329 ms 120180 KB Output is correct
14 Correct 32 ms 20556 KB Output is correct
15 Correct 215 ms 102260 KB Output is correct
16 Correct 310 ms 102860 KB Output is correct
17 Correct 357 ms 103984 KB Output is correct
18 Correct 387 ms 103732 KB Output is correct
19 Correct 391 ms 109564 KB Output is correct
20 Correct 408 ms 108160 KB Output is correct
21 Correct 251 ms 104564 KB Output is correct
22 Correct 259 ms 104568 KB Output is correct
23 Correct 315 ms 105060 KB Output is correct
24 Correct 253 ms 105236 KB Output is correct
25 Correct 381 ms 108440 KB Output is correct
26 Correct 333 ms 102812 KB Output is correct
27 Correct 275 ms 102736 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 20800 KB Output is correct
2 Correct 45 ms 24836 KB Output is correct
3 Correct 59 ms 25088 KB Output is correct
4 Correct 60 ms 25084 KB Output is correct
5 Correct 65 ms 25344 KB Output is correct
6 Correct 42 ms 24836 KB Output is correct
7 Correct 32 ms 20488 KB Output is correct
8 Correct 222 ms 104156 KB Output is correct
9 Correct 228 ms 103912 KB Output is correct
10 Correct 30 ms 20480 KB Output is correct
11 Correct 326 ms 120436 KB Output is correct
12 Correct 328 ms 120304 KB Output is correct
13 Correct 329 ms 120180 KB Output is correct
14 Correct 32 ms 20556 KB Output is correct
15 Correct 215 ms 102260 KB Output is correct
16 Correct 310 ms 102860 KB Output is correct
17 Correct 357 ms 103984 KB Output is correct
18 Correct 387 ms 103732 KB Output is correct
19 Correct 391 ms 109564 KB Output is correct
20 Correct 408 ms 108160 KB Output is correct
21 Correct 251 ms 104564 KB Output is correct
22 Correct 259 ms 104568 KB Output is correct
23 Correct 315 ms 105060 KB Output is correct
24 Correct 253 ms 105236 KB Output is correct
25 Correct 381 ms 108440 KB Output is correct
26 Correct 333 ms 102812 KB Output is correct
27 Correct 275 ms 102736 KB Output is correct
28 Incorrect 36 ms 20592 KB Extra information in the output file
29 Halted 0 ms 0 KB -