Submission #864118

#	Time	Username	Problem	Language	Result	Execution time	Memory
864118		TAhmed33	Inside information (BOI21_servers)	C++98	2.50 / 100	83 ms	56316 KiB

servers

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 120005;
const int MM = 17;
vector <pair <int, int>> adj[MAXN];
pair <int, int> queries[MAXN];
int t[MAXN];
int cnt = 0;
vector <int> pp[MAXN];
int dp[MM][MAXN];
int inc[MM][MAXN]; 
int decc[MM][MAXN];
int mx[MM][MAXN];
int top[MM][MAXN];
int u[MAXN];
int dep[MAXN];
void calc (int pos, int par) {
	for (auto j : adj[pos]) {
		if (j.first != par) {
			dep[j.first] = 1 + dep[pos];
			dp[0][j.first] = pos;
            inc[0][j.first] = 1;
            decc[0][j.first] = 1;
            mx[0][j.first] = top[0][j.first] = j.second;
			u[j.first] = j.second;
			calc(j.first, pos);
		}
	}
}
int jump (int a, int b) {
	for (int i = MM - 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 = MM - 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];
}
bool checkinc (int a, int x) { //increasing upwards
    if (a == x) return 1;
    int e = dep[a] - dep[x];
    //cout << a << " | " << x << '\n';
    //cout << e << " dd\n";
    int last = 0;
    for (int i = MM - 1; i >= 0; i--) {
        if (e & (1 << i)) {
            if (u[a] < last) return 0;
            last = u[a]; a = dp[i][a];
        }
    }
    return 1;
}
bool checkdec (int a, int x) { //decreasing upwards
    if (a == x) return 1;
    //cout << a << " | " << x << '\n';
    int e = dep[a] - dep[x];
    //cout << e << " dd\n";
    int last = 1e9;
    for (int i = MM - 1; i >= 0; i--) {
        if (e & (1 << i)) {
            if (u[a] > last) return 0;
            last = u[a]; a = dp[i][a];
        }
    }
    return 1;
}
int gettop (int a, int x) {
    int uu = dep[a] - dep[x];
    int t = u[a];
    for (int i = MM - 1; i >= 0; i--) {
        if (uu & (1 << i)) {
            t = top[i][a];
            a = dp[i][a];
        }
    }   
    return t;
}
int getmx (int a, int x) {
    int uu = dep[a] - dep[x];
    int t = 0;
    for (int i = MM - 1; i >= 0; i--) {
        if (uu & (1 << i)) {
            t = max(t, mx[i][a]);
            a = dp[i][a];
        }
    }
    return t;
}
bool check (int a, int b, int x) {
    if (!checkinc(b, x)) return 0;
    if (!checkdec(a, x)) return 0;
    if (gettop(b, x) > gettop(a, x)) return 0;
    return 1;
}
int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	int l = 0;
	for (int i = 1; i <= n + q - 1; i++) {
		char x;
		cin >> x;
		if (x == 'S') {
			cnt++;
			int a, b;
			cin >> a >> b;
			adj[a].push_back({b, cnt});
			adj[b].push_back({a, cnt});
		} else if (x == 'Q') {
			t[++l] = cnt;
			int a, b;
			cin >> a >> b;
			queries[l] = {a, b};
		}
	}
	calc(1, 0); 
	for (int i = 1; i < MM; i++) {
		for (int j = 1; j <= n; j++) {
			dp[i][j] = dp[i - 1][dp[i - 1][j]];
            top[i][j] = top[i - 1][dp[i - 1][j]];
            mx[i][j] = max(mx[i - 1][j], mx[i - 1][dp[i - 1][j]]);
            inc[i][j] = inc[i - 1][j] & inc[i - 1][dp[i - 1][j]];
            decc[i][j] = decc[i - 1][j] & decc[i - 1][dp[i - 1][j]];
            inc[i][j] &= (top[i - 1][j] < u[dp[i - 1][j]]);
            decc[i][j] &= (top[i - 1][j] > u[dp[i - 1][j]]);
		}
	}
	for (int i = 1; i <= l; i++) {
		vector <int> pp;
		int x = lca(queries[i].first, queries[i].second);
		int a = queries[i].first, b = queries[i].second;
        //cout << a << " | " << x << " " << b << '\n';
        bool flag = 0;
        if (a == b) {
            flag = 1;
        } else if (a == x) {
            //cout << checkinc(b, x) << "  " << getmx(b, x) << '\n';
            flag = checkinc(b, x) & getmx(b, x) <= t[i];
        } else if (b == x) {
            //cout << checkdec(a, x) << " " << getmx(a, x) << '\n';
            flag = checkdec(a, x) & getmx(a, x) <= t[i];
        } else {
            //cout << check(a, b, x) << " " << getmx(a, x) << " " << getmx(b, x) << '\n';
            flag = check(a, b, x) & getmx(a, x) <= t[i] && getmx(b, x) <= t[i];
        }
        cout << (flag ? "yes\n" : "no\n");
	}
}

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:146:49: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  146 |             flag = checkinc(b, x) & getmx(b, x) <= t[i];
      |                                     ~~~~~~~~~~~~^~~~~~~
servers.cpp:149:49: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  149 |             flag = checkdec(a, x) & getmx(a, x) <= t[i];
      |                                     ~~~~~~~~~~~~^~~~~~~
servers.cpp:152:49: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  152 |             flag = check(a, b, x) & getmx(a, x) <= t[i] && getmx(b, x) <= t[i];
      |                                     ~~~~~~~~~~~~^~~~~~~

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