oj.uz

답안 #934142

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
934142 2024-02-26T21:36:12 Z Joshua_Andersson Inside information (BOI21_servers) C++14
15 / 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;
		int v = -1;
		while (!isancestor(u, b))
		{
			good &= upv[u] <= t;
			good &= upv[u] > v;
			v = upv[u];
			u = up[0][u];
		}

		return good&&(v<prev);
	};

	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
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 11264 KB Output is correct
2 Correct 38 ms 13064 KB Output is correct
3 Correct 32 ms 13136 KB Output is correct
4 Correct 386 ms 13368 KB Output is correct
5 Correct 321 ms 13428 KB Output is correct
6 Correct 31 ms 13064 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 11264 KB Output is correct
2 Correct 38 ms 13064 KB Output is correct
3 Correct 32 ms 13136 KB Output is correct
4 Correct 386 ms 13368 KB Output is correct
5 Correct 321 ms 13428 KB Output is correct
6 Correct 31 ms 13064 KB Output is correct
7 Incorrect 28 ms 12104 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 11272 KB Output is correct
2 Correct 64 ms 21896 KB Output is correct
3 Correct 67 ms 21924 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 11272 KB Output is correct
2 Correct 64 ms 21896 KB Output is correct
3 Correct 67 ms 21924 KB Output is correct
4 Incorrect 25 ms 11260 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 11184 KB Output is correct
2 Correct 108 ms 31876 KB Output is correct
3 Correct 100 ms 32004 KB Output is correct
4 Execution timed out 3577 ms 31224 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 11184 KB Output is correct
2 Correct 108 ms 31876 KB Output is correct
3 Correct 100 ms 32004 KB Output is correct
4 Execution timed out 3577 ms 31224 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 11264 KB Output is correct
2 Correct 76 ms 26056 KB Output is correct
3 Correct 107 ms 26200 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 11264 KB Output is correct
2 Correct 76 ms 26056 KB Output is correct
3 Correct 107 ms 26200 KB Output is correct
4 Incorrect 28 ms 12232 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 11296 KB Output is correct
2 Correct 96 ms 31880 KB Output is correct
3 Correct 103 ms 32000 KB Output is correct
4 Execution timed out 3555 ms 31460 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 11296 KB Output is correct
2 Correct 96 ms 31880 KB Output is correct
3 Correct 103 ms 32000 KB Output is correct
4 Execution timed out 3555 ms 31460 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 11260 KB Output is correct
2 Correct 38 ms 13064 KB Output is correct
3 Correct 31 ms 13068 KB Output is correct
4 Correct 390 ms 13176 KB Output is correct
5 Correct 321 ms 13552 KB Output is correct
6 Correct 32 ms 13076 KB Output is correct
7 Correct 25 ms 12028 KB Output is correct
8 Correct 65 ms 24696 KB Output is correct
9 Correct 65 ms 24688 KB Output is correct
10 Correct 30 ms 12228 KB Output is correct
11 Correct 126 ms 35328 KB Output is correct
12 Correct 96 ms 35332 KB Output is correct
13 Execution timed out 3503 ms 34684 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 11260 KB Output is correct
2 Correct 38 ms 13064 KB Output is correct
3 Correct 31 ms 13068 KB Output is correct
4 Correct 390 ms 13176 KB Output is correct
5 Correct 321 ms 13552 KB Output is correct
6 Correct 32 ms 13076 KB Output is correct
7 Correct 25 ms 12028 KB Output is correct
8 Correct 65 ms 24696 KB Output is correct
9 Correct 65 ms 24688 KB Output is correct
10 Correct 30 ms 12228 KB Output is correct
11 Correct 126 ms 35328 KB Output is correct
12 Correct 96 ms 35332 KB Output is correct
13 Execution timed out 3503 ms 34684 KB Time limit exceeded
14 Halted 0 ms 0 KB -