oj.uz

Submission #864120

# Submission time Handle Problem Language Result Execution time Memory
864120 2023-10-22T05:37:32 Z TAhmed33 Inside information (BOI21_servers) C++
50 / 100
 139 ms 63372 KB 
#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;
            if (!inc[i][a]) return 0;
            last = top[i][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;
            if (!decc[i][a]) return 0;
            last = top[i][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

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

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 48476 KB Output is correct
2 Correct 38 ms 50000 KB Output is correct
3 Correct 40 ms 50000 KB Output is correct
4 Correct 47 ms 50004 KB Output is correct
5 Correct 41 ms 50176 KB Output is correct
6 Correct 40 ms 49900 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 48476 KB Output is correct
2 Correct 38 ms 50000 KB Output is correct
3 Correct 40 ms 50000 KB Output is correct
4 Correct 47 ms 50004 KB Output is correct
5 Correct 41 ms 50176 KB Output is correct
6 Correct 40 ms 49900 KB Output is correct
7 Incorrect 31 ms 49236 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 48520 KB Output is correct
2 Correct 88 ms 53448 KB Output is correct
3 Correct 81 ms 53444 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 48520 KB Output is correct
2 Correct 88 ms 53448 KB Output is correct
3 Correct 81 ms 53444 KB Output is correct
4 Incorrect 33 ms 48472 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 48408 KB Output is correct
2 Correct 93 ms 63316 KB Output is correct
3 Correct 91 ms 63316 KB Output is correct
4 Correct 119 ms 63060 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 48408 KB Output is correct
2 Correct 93 ms 63316 KB Output is correct
3 Correct 91 ms 63316 KB Output is correct
4 Correct 119 ms 63060 KB Output is correct
5 Incorrect 25 ms 49244 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 48468 KB Output is correct
2 Correct 83 ms 56656 KB Output is correct
3 Correct 88 ms 57204 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 48468 KB Output is correct
2 Correct 83 ms 56656 KB Output is correct
3 Correct 88 ms 57204 KB Output is correct
4 Incorrect 28 ms 49360 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 48476 KB Output is correct
2 Correct 91 ms 63372 KB Output is correct
3 Correct 85 ms 63312 KB Output is correct
4 Correct 130 ms 63188 KB Output is correct
5 Correct 29 ms 49252 KB Output is correct
6 Correct 89 ms 56504 KB Output is correct
7 Correct 84 ms 57172 KB Output is correct
8 Correct 120 ms 57604 KB Output is correct
9 Correct 93 ms 57492 KB Output is correct
10 Correct 112 ms 61596 KB Output is correct
11 Correct 137 ms 60844 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 48476 KB Output is correct
2 Correct 91 ms 63372 KB Output is correct
3 Correct 85 ms 63312 KB Output is correct
4 Correct 130 ms 63188 KB Output is correct
5 Correct 29 ms 49252 KB Output is correct
6 Correct 89 ms 56504 KB Output is correct
7 Correct 84 ms 57172 KB Output is correct
8 Correct 120 ms 57604 KB Output is correct
9 Correct 93 ms 57492 KB Output is correct
10 Correct 112 ms 61596 KB Output is correct
11 Correct 137 ms 60844 KB Output is correct
12 Incorrect 24 ms 49252 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 48468 KB Output is correct
2 Correct 37 ms 49988 KB Output is correct
3 Correct 40 ms 50140 KB Output is correct
4 Correct 50 ms 50000 KB Output is correct
5 Correct 45 ms 50268 KB Output is correct
6 Correct 40 ms 50004 KB Output is correct
7 Correct 38 ms 49376 KB Output is correct
8 Correct 83 ms 56260 KB Output is correct
9 Correct 81 ms 56260 KB Output is correct
10 Correct 26 ms 49236 KB Output is correct
11 Correct 87 ms 63312 KB Output is correct
12 Correct 83 ms 63312 KB Output is correct
13 Correct 104 ms 63056 KB Output is correct
14 Correct 29 ms 49228 KB Output is correct
15 Correct 82 ms 56656 KB Output is correct
16 Correct 83 ms 57160 KB Output is correct
17 Correct 109 ms 57624 KB Output is correct
18 Correct 95 ms 57492 KB Output is correct
19 Correct 124 ms 61600 KB Output is correct
20 Correct 139 ms 60728 KB Output is correct
21 Correct 87 ms 56696 KB Output is correct
22 Correct 86 ms 56864 KB Output is correct
23 Correct 91 ms 57048 KB Output is correct
24 Correct 97 ms 57172 KB Output is correct
25 Correct 94 ms 58320 KB Output is correct
26 Correct 79 ms 56596 KB Output is correct
27 Correct 74 ms 56660 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 48468 KB Output is correct
2 Correct 37 ms 49988 KB Output is correct
3 Correct 40 ms 50140 KB Output is correct
4 Correct 50 ms 50000 KB Output is correct
5 Correct 45 ms 50268 KB Output is correct
6 Correct 40 ms 50004 KB Output is correct
7 Correct 38 ms 49376 KB Output is correct
8 Correct 83 ms 56260 KB Output is correct
9 Correct 81 ms 56260 KB Output is correct
10 Correct 26 ms 49236 KB Output is correct
11 Correct 87 ms 63312 KB Output is correct
12 Correct 83 ms 63312 KB Output is correct
13 Correct 104 ms 63056 KB Output is correct
14 Correct 29 ms 49228 KB Output is correct
15 Correct 82 ms 56656 KB Output is correct
16 Correct 83 ms 57160 KB Output is correct
17 Correct 109 ms 57624 KB Output is correct
18 Correct 95 ms 57492 KB Output is correct
19 Correct 124 ms 61600 KB Output is correct
20 Correct 139 ms 60728 KB Output is correct
21 Correct 87 ms 56696 KB Output is correct
22 Correct 86 ms 56864 KB Output is correct
23 Correct 91 ms 57048 KB Output is correct
24 Correct 97 ms 57172 KB Output is correct
25 Correct 94 ms 58320 KB Output is correct
26 Correct 79 ms 56596 KB Output is correct
27 Correct 74 ms 56660 KB Output is correct
28 Incorrect 31 ms 49232 KB Extra information in the output file
29 Halted 0 ms 0 KB -