oj.uz

Submission #934140

# Submission time Handle Problem Language Result Execution time Memory
934140 2024-02-26T21:29:55 Z Joshua_Andersson Inside information (BOI21_servers) C++14
0 / 100
 3500 ms 35332 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
const int inf = int(1e18);

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[18][maxn];
int upv[maxn];

void dfs(int u, int p, int p1, int _p2, vector<vector<p2>>& edges)
{
	tin[u] = timer++;
	up[0][u] = p;
	

	repe(e, edges[u]) if (e.first != p) dfs(e.first, u, p1, _p2, edges), upv[e.first]=e.second;

	tout[u] = timer++;
}

bool isancestor(int a, int b)
{
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

signed main()
{
	fast();

	int n, q;
	cin >> n >> q;

	vvi queries;
	int t = 0;
	vector<vector<p2>> edges(n);
	rep(i, n + q - 1)
	{
		char c;
		cin >> c;
		if (c=='S')
		{
			int a, b;
			cin >> a >> b;
			a--; b--;
			edges[a].emplace_back(b, t);
			edges[b].emplace_back(a, t);
			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 });
		}
	}
	dfs(0, 0, -1, -1, edges);


	auto pathgood = [&](int a, int b, int t)
	{
		// all edges <= t
		// from b->lca increasing
		// from a->lca decreasing
		bool good = 1;
		int u = b;
		int prev = inf;
		while (!isancestor(u, a))
		{
			good &= upv[u] <= t;
			good &= upv[u] < prev;
			prev = upv[u];
			u = up[0][u];
		}
		
		u = a;
		prev = -1;
		while (!isancestor(u, b))
		{
			good &= upv[u] <= t;
			good &= upv[u] > prev;
			prev = upv[u];
			u = up[0][u];
		}

		return good;
	};

	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";
		}
		
	}

	return 0;
}

Subtask #1
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 12040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 12040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 12296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 12296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12300 KB Output is correct
2 Correct 122 ms 35216 KB Output is correct
3 Correct 97 ms 35332 KB Output is correct
4 Execution timed out 3562 ms 34656 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12300 KB Output is correct
2 Correct 122 ms 35216 KB Output is correct
3 Correct 97 ms 35332 KB Output is correct
4 Execution timed out 3562 ms 34656 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 12040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 12040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12044 KB Output is correct
2 Correct 110 ms 35224 KB Output is correct
3 Correct 102 ms 35248 KB Output is correct
4 Execution timed out 3552 ms 34788 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12044 KB Output is correct
2 Correct 110 ms 35224 KB Output is correct
3 Correct 102 ms 35248 KB Output is correct
4 Execution timed out 3552 ms 34788 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 12044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 12044 KB Output isn't correct
2 Halted 0 ms 0 KB -