답안 #934166

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
934166 2024-02-26T22:47:41 Z Joshua_Andersson Inside information (BOI21_servers) C++14
20 / 100
3500 ms 118684 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 upincreasing[18][maxn];
int updecreasing[18][maxn];
int upmax[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;
	upmax[0][u] = upv[u];
	upincreasing[0][u] = upmax[0][u] < upmax[0][p] || p==0;
	updecreasing[0][u] = upmax[0][u] > upmax[0][p] || p==0 || u==0;
	repp(d,1,18)
	{
		int mid = up[d - 1][u];
		up[d][u] = up[d - 1][mid];
		upmax[d][u] = max(upmax[d - 1][u], upmax[d - 1][mid]);
		upincreasing[d][u] = upincreasing[d - 1][u] && upincreasing[d-1][mid] && (upmax[0][mid] < upmax[0][up[0][mid]]);
		updecreasing[d][u] = updecreasing[d - 1][u] && updecreasing[d-1][mid] && (upmax[0][mid] > upmax[0][up[0][mid]] || up[0][mid]==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[d][a], b))
		{
			ret = max(ret, upmax[d][a]);
			a = up[d][a];
		}
	}
	return max(ret, upmax[0][a]);
}

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);
	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 getmax = [&](int a, int b)
	{
		return max(pathmax(a, b), pathmax(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[d][u],a))
			{
				good &= updecreasing[d][u];
				u = up[d][u];
			}
		}
		
		if (!isancestor(u,a))
		{
			prev = upmax[0][u];
		}
		/*bool g = 1;
		int p = inf;
		while (!isancestor(u, a))
		{
			g &= upv[u] < p;
			p = upv[u];
			u = up[0][u];
		}*/
		//assert(prev == p);
		//assert(g == good);

		u = a;
		int v = -1;
		while (!isancestor(u, b))
		{
			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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 87080 KB Output is correct
2 Correct 50 ms 85800 KB Output is correct
3 Correct 47 ms 89852 KB Output is correct
4 Correct 60 ms 89932 KB Output is correct
5 Correct 209 ms 92152 KB Output is correct
6 Correct 46 ms 91660 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 87080 KB Output is correct
2 Correct 50 ms 85800 KB Output is correct
3 Correct 47 ms 89852 KB Output is correct
4 Correct 60 ms 89932 KB Output is correct
5 Correct 209 ms 92152 KB Output is correct
6 Correct 46 ms 91660 KB Output is correct
7 Incorrect 39 ms 93196 KB Extra information in the output file
8 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 91168 KB Output is correct
2 Correct 205 ms 104016 KB Output is correct
3 Correct 186 ms 104844 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 91168 KB Output is correct
2 Correct 205 ms 104016 KB Output is correct
3 Correct 186 ms 104844 KB Output is correct
4 Incorrect 37 ms 93304 KB Extra information in the output file
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 91140 KB Output is correct
2 Correct 164 ms 117668 KB Output is correct
3 Correct 191 ms 118472 KB Output is correct
4 Correct 2337 ms 117260 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 91140 KB Output is correct
2 Correct 164 ms 117668 KB Output is correct
3 Correct 191 ms 118472 KB Output is correct
4 Correct 2337 ms 117260 KB Output is correct
5 Incorrect 41 ms 90108 KB Extra information in the output file
6 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 91140 KB Output is correct
2 Correct 142 ms 104828 KB Output is correct
3 Correct 162 ms 104960 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 91140 KB Output is correct
2 Correct 142 ms 104828 KB Output is correct
3 Correct 162 ms 104960 KB Output is correct
4 Incorrect 37 ms 89240 KB Extra information in the output file
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 91144 KB Output is correct
2 Correct 210 ms 117780 KB Output is correct
3 Correct 166 ms 118296 KB Output is correct
4 Correct 2315 ms 117628 KB Output is correct
5 Correct 38 ms 92180 KB Output is correct
6 Correct 151 ms 108304 KB Output is correct
7 Correct 187 ms 108464 KB Output is correct
8 Correct 385 ms 109700 KB Output is correct
9 Correct 232 ms 109312 KB Output is correct
10 Correct 1702 ms 115352 KB Output is correct
11 Execution timed out 3562 ms 115020 KB Time limit exceeded
12 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 91144 KB Output is correct
2 Correct 210 ms 117780 KB Output is correct
3 Correct 166 ms 118296 KB Output is correct
4 Correct 2315 ms 117628 KB Output is correct
5 Correct 38 ms 92180 KB Output is correct
6 Correct 151 ms 108304 KB Output is correct
7 Correct 187 ms 108464 KB Output is correct
8 Correct 385 ms 109700 KB Output is correct
9 Correct 232 ms 109312 KB Output is correct
10 Correct 1702 ms 115352 KB Output is correct
11 Execution timed out 3562 ms 115020 KB Time limit exceeded
12 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 91156 KB Output is correct
2 Correct 49 ms 89760 KB Output is correct
3 Correct 46 ms 89860 KB Output is correct
4 Correct 60 ms 91900 KB Output is correct
5 Correct 205 ms 92156 KB Output is correct
6 Correct 48 ms 91720 KB Output is correct
7 Correct 37 ms 91392 KB Output is correct
8 Correct 197 ms 104232 KB Output is correct
9 Correct 195 ms 104052 KB Output is correct
10 Correct 36 ms 89536 KB Output is correct
11 Correct 173 ms 118684 KB Output is correct
12 Correct 168 ms 117760 KB Output is correct
13 Correct 2371 ms 117772 KB Output is correct
14 Correct 38 ms 92164 KB Output is correct
15 Correct 138 ms 108796 KB Output is correct
16 Correct 162 ms 108772 KB Output is correct
17 Correct 396 ms 109984 KB Output is correct
18 Correct 277 ms 108748 KB Output is correct
19 Correct 1699 ms 115648 KB Output is correct
20 Execution timed out 3521 ms 114516 KB Time limit exceeded
21 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 91156 KB Output is correct
2 Correct 49 ms 89760 KB Output is correct
3 Correct 46 ms 89860 KB Output is correct
4 Correct 60 ms 91900 KB Output is correct
5 Correct 205 ms 92156 KB Output is correct
6 Correct 48 ms 91720 KB Output is correct
7 Correct 37 ms 91392 KB Output is correct
8 Correct 197 ms 104232 KB Output is correct
9 Correct 195 ms 104052 KB Output is correct
10 Correct 36 ms 89536 KB Output is correct
11 Correct 173 ms 118684 KB Output is correct
12 Correct 168 ms 117760 KB Output is correct
13 Correct 2371 ms 117772 KB Output is correct
14 Correct 38 ms 92164 KB Output is correct
15 Correct 138 ms 108796 KB Output is correct
16 Correct 162 ms 108772 KB Output is correct
17 Correct 396 ms 109984 KB Output is correct
18 Correct 277 ms 108748 KB Output is correct
19 Correct 1699 ms 115648 KB Output is correct
20 Execution timed out 3521 ms 114516 KB Time limit exceeded
21 Halted 0 ms 0 KB -