Submission #999360

#	Time	Username	Problem	Language	Result	Execution time	Memory
999360		TAhmed33	Inside information (BOI21_servers)	C++98	50 / 100	173 ms	113232 KiB

servers

    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 3e5 + 25;
    const int B = 18;
    int n, q;
    array <int, 4> queries[MAXN];
    vector <pair <int, int>> adj[MAXN];
    int p[MAXN], dp[B][MAXN], dep[MAXN], top[B][MAXN], inc[B][MAXN], decr[B][MAXN];
    void dfs (int pos, int par) {
    	p[pos] = par;
    	for (auto [j, k] : adj[pos]) {
    		if (j == par) continue;
    		dep[j] = 1 + dep[pos];
    		dp[0][j] = pos;
    		top[0][j] = k;
    		inc[0][j] = 1;
    		decr[0][j] = 1;
    		for (int i = 1; i < B; i++) {
    			dp[i][j] = dp[i - 1][dp[i - 1][j]];
    			top[i][j] = top[i - 1][dp[i - 1][j]];
    			inc[i][j] = inc[i - 1][j] && inc[i - 1][dp[i - 1][j]] && (top[i - 1][j] < top[0][dp[i - 1][j]]);
    			decr[i][j] = decr[i - 1][j] && decr[i - 1][dp[i - 1][j]] && (top[i - 1][j] > top[0][dp[i - 1][j]]);
    		} 
    		dfs(j, pos);
    	}
    }
    int jump (int a, int b) {
    	for (int i = B - 1; i >= 0; i--) {
    		if (b & (1 << i)) {
    			a = dp[i][a];
    		}
    	}
    	return a;
    }
    int lca (int a, int b) {
    	if (dep[a] > dep[b]) swap(a, b);
    	b = jump(b, dep[b] - dep[a]);
    	if (a == b) return a;
    	for (int i = B - 1; i >= 0; i--) {
    		int x = dp[i][a], y = dp[i][b];
    		if (x && y && x != y) {
    			a = x, b = y;
    		}
    	}
    	return dp[0][a];
    }
    pair <bool, int> check_inc (int a, int b, int x) {
    	bool f = 1; int last = 0;
    	for (int i = B - 1; i >= 0; i--) {
    		int z = dp[i][a];
    		if (!z || dep[z] <= dep[b]) continue;
    		f &= inc[i][a]; f &= top[0][a] > last;
    		last = top[i][a]; a = z;
    	}
    	f &= top[0][a] <= x;
    	f &= top[0][a] > last;
    	return {f, top[0][a]};
    } 
    pair <bool, int> check_decr (int a, int b, int x) {
    	bool f = top[0][a] <= x; int last = 1e9;
    	for (int i = B - 1; i >= 0; i--) {
    		int z = dp[i][a];
    		if (!z || dep[z] <= dep[b]) continue;
    		f &= decr[i][a]; f &= top[0][a] < last;
    		last = top[i][a]; a = z;
    	}
    	f &= top[0][a] < last;
    	return {f, top[0][a]};
    }
    bool check (int a, int b, int x) {
    	if (a == b) return 1;
    	int z = lca(a, b);
    	if (z == a) return check_decr(b, z, x).first;
    	if (z == b) return check_inc(a, z, x).first;
    	auto g = check_inc(a, z, x), h = check_decr(b, z, x);
    	return g.first && h.first && g.second < h.second;
    }
    void solve () {
    	cin >> n >> q;
    	int ee = 0;
    	for (int i = 1; i <= n - 1 + q; i++) {
    		char c; cin >> c;
    		if (c == 'S') {	
    			int x, y; cin >> x >> y;
    			adj[x].push_back({y, i});
    			adj[y].push_back({x, i});
    		} else if (c == 'Q') {
    			int x, y; cin >> x >> y;
    			queries[++ee] = {1, y, x, i};
    		} else {
    			int x; cin >> x;
    			queries[++ee] = {2, x, 0, i};
    		}
    	}
    	dfs(1, 0);
    	for (int i = 1; i <= q; i++) {
    		auto g = check(queries[i][1], queries[i][2], queries[i][3]);
    		cout << (g ? "yes\n" : "no\n");
    	}
    }		
    signed main () {
    	ios::sync_with_stdio(0); cin.tie(0);
    	int tc = 1; //cin >> tc;
    	while (tc--) solve();
    }

Compilation message (stderr)

servers.cpp: In function 'void dfs(int, int)':
servers.cpp:11:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   11 |      for (auto [j, k] : adj[pos]) {
      |                ^

• Subtask 1: 2.5 / 2.5
• Subtask 2: 0 / 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: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5