oj.uz

답안 #558332

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
558332 2022-05-07T06:15:15 Z cheissmart Inside information (BOI21_servers) C++14
50 / 100
 461 ms 175036 KB 
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 120005;

V<pi> G[N];

namespace he {

struct Data {
	bool ok;
	int l, r;
	int mx;
	Data(int _mx = -1) {
		ok = true;
		l = r = mx = _mx;
	}
	friend Data operator + (const Data lhs, const Data rhs) {
		if(lhs.mx == -1) return rhs;
		if(rhs.mx == -1) return lhs;
		Data res;
		res.ok = lhs.ok & rhs.ok & (lhs.r < rhs.l);
		res.l = lhs.l, res.r = rhs.r;
		res.mx = max(lhs.mx, rhs.mx);
		return res;
	}
} up[N][20], down[N][20];

int p[N][20], d[N];

void dfs(int u, int pa = 0) {
	p[u][0] = pa;
	for(int i = 1; i < 20; i++) {
		p[u][i] = p[p[u][i - 1]][i - 1];
		up[u][i] = up[u][i - 1] + up[p[u][i - 1]][i - 1];
		down[u][i] = down[p[u][i - 1]][i - 1] + down[u][i - 1];
	}
	for(auto[v, i]:G[u]) if(v != pa) {
		d[v] = d[u] + 1;
		up[v][0] = down[v][0] = Data(i);
		dfs(v, u);
	}
}

int lca(int u, int v) {
	if(d[u] > d[v]) swap(u, v);
	for(int i = 0; i < 20; i++)
		if((d[v] - d[u]) >> i & 1)
			v = p[v][i];
	if(u == v) return u;
	for(int i = 19; i >= 0; i--)
		if(p[u][i] != p[v][i])
			u = p[u][i], v = p[v][i];
	assert(u != v && p[u][0] == p[v][0]);
	return p[u][0];
}

Data go_up(int u, int step) {
	Data res;
	for(int i = 0; i < 20; i++) if(step >> i & 1)
		res = res + up[u][i], u = p[u][i];
	return res;
}
Data go_down(int u, int step) {
	Data res;
	for(int i = 0; i < 20; i++) if(step >> i & 1)
		res = down[u][i] + res, u = p[u][i];
	return res;
}

}

namespace be {

vi aux[N];
int ans[N], sz[N];
bool vis[N];

void dfs_sz(int u, int p = 0) {
	sz[u] = 1;
	for(auto[v, i] : G[u]) if(v != p && !vis[v]) {
		dfs_sz(v, u);
		sz[u] += sz[v];
	}
}

void dfs_c(int u, int& c, int tot, int p = 0) {
	int mx = tot - sz[u];
	for(auto[v, i] : G[u]) if(v != p && !vis[v]) {
		dfs_c(v, c, tot, u);
		mx = max(mx, sz[v]);
	}
	if(mx * 2 <= tot) c = u;
}

void dfs_down(int u, V<pi>&down, int l, int r, int p) {
	down.EB(l, r);
	for(auto[v, i] : G[u]) if(v != p && !vis[v])
		if(i > r)
			dfs_down(v, down, l, i, u);
}

void dfs_up(int u, V<pi>&up, int l, int r, int p) {
	for(int i:aux[u]) if(i >= r) {
		up.EB(r, i);
		ans[i]++; // to c
	}
	for(auto[v, i] : G[u]) if(v != p && !vis[v])
		if(i < l)
			dfs_up(v, up, i, r, u);
}

void go(V<pi> up, V<pi> down, int op) {
	for(pi p:up) {
		for(pi pp:down) {
			if(p.F <= pp.F && pp.S <= p.S)
				ans[p.S] += op;
		}
	}
}

void CD(int u) {
	dfs_sz(u);
	int c = -1; dfs_c(u, c, sz[u]);
	V<pi> down_all, up_all;

	for(auto[v, i]:G[c]) if(!vis[v]) {
		V<pi> down;
		dfs_down(v, down, i, i, c);
		V<pi> up;
		dfs_up(v, up, i, i, c);
		go(up, down, -1);

		for(pi p:up) up_all.PB(p);
		for(pi p:down) down_all.PB(p);
	}
	go(up_all, down_all, 1);

	V<pi> upc;
	for(int i:aux[c])
		upc.EB(0, i);

	go(upc, down_all, 1);

	vis[c] = 1;
	for(auto[v, i]:G[c]) if(!vis[v])
		CD(v);

}

}
	
signed main()
{
	IO_OP;

	int n, k;
	cin >> n >> k;
	V<array<int, 3>> qq;
	for(int i = 1; i <= n + k - 1; i++) {
		char op; cin >> op;
		if(op == 'S') {
			int u, v; cin >> u >> v;
			G[u].EB(v, i);
			G[v].EB(u, i);
		} else if(op == 'Q') {
			int u, v; cin >> u >> v;
			qq.PB({u, v, i});
		} else {
			int u; cin >> u;
			qq.PB({u, -1, i});
			be::aux[u].PB(i);
		}
	}
	he::dfs(1);

	be::CD(1);

	for(auto[u, v, i] : qq) {
		if(v != -1) {
			// is the path v -> u increasing?
			if(u == v) {
				cout << "yes\n";
				continue;
			}
			int l = he::lca(u, v);
			auto tt = he::go_up(v, he::d[v] - he::d[l]) + he::go_down(u, he::d[u] - he::d[l]);
			if(tt.mx < i && tt.ok)
				cout << "yes\n";
			else
				cout << "no\n";
		} else {
			cout << be::ans[i] + 1 << '\n';
		}
	}

}

Compilation message

servers.cpp: In function 'void he::dfs(int, int)':
servers.cpp:52:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |  for(auto[v, i]:G[u]) if(v != pa) {
      |          ^
servers.cpp: In function 'void be::dfs_sz(int, int)':
servers.cpp:95:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |  for(auto[v, i] : G[u]) if(v != p && !vis[v]) {
      |          ^
servers.cpp: In function 'void be::dfs_c(int, int&, int, int)':
servers.cpp:103:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |  for(auto[v, i] : G[u]) if(v != p && !vis[v]) {
      |          ^
servers.cpp: In function 'void be::dfs_down(int, std::vector<std::pair<int, int> >&, int, int, int)':
servers.cpp:112:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  112 |  for(auto[v, i] : G[u]) if(v != p && !vis[v])
      |          ^
servers.cpp: In function 'void be::dfs_up(int, std::vector<std::pair<int, int> >&, int, int, int)':
servers.cpp:122:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  122 |  for(auto[v, i] : G[u]) if(v != p && !vis[v])
      |          ^
servers.cpp: In function 'void be::CD(int)':
servers.cpp:141:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  141 |  for(auto[v, i]:G[c]) if(!vis[v]) {
      |          ^
servers.cpp:160:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  160 |  for(auto[v, i]:G[c]) if(!vis[v])
      |          ^
servers.cpp: In function 'int main()':
servers.cpp:193:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  193 |  for(auto[u, v, i] : qq) {
      |          ^

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 83464 KB Output is correct
2 Correct 95 ms 83660 KB Output is correct
3 Correct 87 ms 83872 KB Output is correct
4 Correct 102 ms 83908 KB Output is correct
5 Correct 90 ms 84236 KB Output is correct
6 Correct 83 ms 83936 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 83464 KB Output is correct
2 Correct 95 ms 83660 KB Output is correct
3 Correct 87 ms 83872 KB Output is correct
4 Correct 102 ms 83908 KB Output is correct
5 Correct 90 ms 84236 KB Output is correct
6 Correct 83 ms 83936 KB Output is correct
7 Runtime error 130 ms 168204 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 83560 KB Output is correct
2 Correct 227 ms 100080 KB Output is correct
3 Correct 238 ms 100100 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 83560 KB Output is correct
2 Correct 227 ms 100080 KB Output is correct
3 Correct 238 ms 100100 KB Output is correct
4 Runtime error 140 ms 168112 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 83456 KB Output is correct
2 Correct 355 ms 108752 KB Output is correct
3 Correct 323 ms 108780 KB Output is correct
4 Correct 330 ms 110216 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 83456 KB Output is correct
2 Correct 355 ms 108752 KB Output is correct
3 Correct 323 ms 108780 KB Output is correct
4 Correct 330 ms 110216 KB Output is correct
5 Runtime error 140 ms 168256 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 83544 KB Output is correct
2 Correct 270 ms 99976 KB Output is correct
3 Correct 268 ms 98964 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 83544 KB Output is correct
2 Correct 270 ms 99976 KB Output is correct
3 Correct 268 ms 98964 KB Output is correct
4 Runtime error 136 ms 175036 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 83480 KB Output is correct
2 Correct 329 ms 108792 KB Output is correct
3 Correct 319 ms 108752 KB Output is correct
4 Correct 308 ms 110240 KB Output is correct
5 Correct 77 ms 83388 KB Output is correct
6 Correct 275 ms 99880 KB Output is correct
7 Correct 272 ms 98896 KB Output is correct
8 Correct 380 ms 99272 KB Output is correct
9 Correct 322 ms 99368 KB Output is correct
10 Correct 371 ms 104880 KB Output is correct
11 Correct 461 ms 104248 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 83480 KB Output is correct
2 Correct 329 ms 108792 KB Output is correct
3 Correct 319 ms 108752 KB Output is correct
4 Correct 308 ms 110240 KB Output is correct
5 Correct 77 ms 83388 KB Output is correct
6 Correct 275 ms 99880 KB Output is correct
7 Correct 272 ms 98896 KB Output is correct
8 Correct 380 ms 99272 KB Output is correct
9 Correct 322 ms 99368 KB Output is correct
10 Correct 371 ms 104880 KB Output is correct
11 Correct 461 ms 104248 KB Output is correct
12 Runtime error 132 ms 168204 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 83468 KB Output is correct
2 Correct 96 ms 83672 KB Output is correct
3 Correct 84 ms 83928 KB Output is correct
4 Correct 107 ms 83864 KB Output is correct
5 Correct 123 ms 84276 KB Output is correct
6 Correct 98 ms 84016 KB Output is correct
7 Correct 76 ms 83380 KB Output is correct
8 Correct 211 ms 99992 KB Output is correct
9 Correct 215 ms 100048 KB Output is correct
10 Correct 75 ms 83356 KB Output is correct
11 Correct 321 ms 108956 KB Output is correct
12 Correct 322 ms 108784 KB Output is correct
13 Correct 306 ms 110188 KB Output is correct
14 Correct 74 ms 83424 KB Output is correct
15 Correct 299 ms 99860 KB Output is correct
16 Correct 265 ms 98956 KB Output is correct
17 Correct 362 ms 99220 KB Output is correct
18 Correct 312 ms 99320 KB Output is correct
19 Correct 374 ms 104880 KB Output is correct
20 Correct 448 ms 104068 KB Output is correct
21 Correct 241 ms 100032 KB Output is correct
22 Correct 225 ms 99624 KB Output is correct
23 Correct 266 ms 99028 KB Output is correct
24 Correct 277 ms 99060 KB Output is correct
25 Correct 365 ms 103668 KB Output is correct
26 Correct 323 ms 98364 KB Output is correct
27 Correct 312 ms 98368 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 83468 KB Output is correct
2 Correct 96 ms 83672 KB Output is correct
3 Correct 84 ms 83928 KB Output is correct
4 Correct 107 ms 83864 KB Output is correct
5 Correct 123 ms 84276 KB Output is correct
6 Correct 98 ms 84016 KB Output is correct
7 Correct 76 ms 83380 KB Output is correct
8 Correct 211 ms 99992 KB Output is correct
9 Correct 215 ms 100048 KB Output is correct
10 Correct 75 ms 83356 KB Output is correct
11 Correct 321 ms 108956 KB Output is correct
12 Correct 322 ms 108784 KB Output is correct
13 Correct 306 ms 110188 KB Output is correct
14 Correct 74 ms 83424 KB Output is correct
15 Correct 299 ms 99860 KB Output is correct
16 Correct 265 ms 98956 KB Output is correct
17 Correct 362 ms 99220 KB Output is correct
18 Correct 312 ms 99320 KB Output is correct
19 Correct 374 ms 104880 KB Output is correct
20 Correct 448 ms 104068 KB Output is correct
21 Correct 241 ms 100032 KB Output is correct
22 Correct 225 ms 99624 KB Output is correct
23 Correct 266 ms 99028 KB Output is correct
24 Correct 277 ms 99060 KB Output is correct
25 Correct 365 ms 103668 KB Output is correct
26 Correct 323 ms 98364 KB Output is correct
27 Correct 312 ms 98368 KB Output is correct
28 Runtime error 128 ms 168180 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -