Submission #558336

#	Time	Username	Problem	Language	Result	Execution time	Memory
558336		cheissmart	Inside information (BOI21_servers)	C++14	62.50 / 100	3580 ms	112704 KiB

servers

#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 * 2], 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 (stderr)

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:142:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  142 |  for(auto[v, i]:G[c]) if(!vis[v]) {
      |          ^
servers.cpp:161:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  161 |  for(auto[v, i]:G[c]) if(!vis[v])
      |          ^
servers.cpp: In function 'int main()':
servers.cpp:194:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  194 |  for(auto[u, v, i] : qq) {
      |          ^

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5