oj.uz

Submission #675704

# Submission time Handle Problem Language Result Execution time Memory
675704 2022-12-27T18:23:14 Z stanislavpolyn Inside information (BOI21_servers) C++17
50 / 100
 3500 ms 40288 KB 
#include <bits/stdc++.h>

#define fr(i, a, b) for (int i = (a); i <= (b); i++)
#define rf(i, a, b) for (int i = (a); i >= (b); i--)
#define fe(x, y) for (auto& x : y)

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple

#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

using namespace std;

mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key

template <typename T>
bool umn(T& a, T b) {
    return a > b ? a = b, 1 : 0;
}
template <typename T>
bool umx(T& a, T b) {
    return a < b ? a = b, 1 : 0;
}

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;

const int N = 3e5 + 5;

#define dec abcd

int n, k;
ve<pii> g[N];
ve<array<int, 3>> Q;

int timer;
int tin[N], tout[N];
int up[N][20];
int par[N], val[N];

bool inc[N][20];
bool dec[N][20];
int dep[N];

void dfs(int v = 1, int p = 0) {
    up[v][0] = p;
    fr (i, 1, 19) up[v][i] = up[up[v][i - 1]][i - 1];
    tin[v] = timer++;

    fe (to, g[v]) {
        if (to.fi == p) continue;
        par[to.fi] = v;
        val[to.fi] = to.se;
        dep[to.fi] = dep[v] + 1;
        dfs(to.fi, v);
    }

    tout[v] = timer++;
}

bool isUpper(int a, int b) {
    return tin[a] <= tin[b] && tout[a] >= tin[b];
}

int getLCA(int a, int b) {
    if (isUpper(a, b)) return a;
    if (isUpper(b, a)) return b;
    rf (i, 19, 0) {
        if (up[a][i] && !isUpper(up[a][i], b)) {
            a = up[a][i];
        }
    }
    return up[a][0];
}

int goUp(int v, int d) {
    rf (i, 19, 0) {
        if (d - pw(i) >= 0) {
            v = up[v][i];
            d -= pw(i);
        }
    }
    assert(v);
    return v;
}

bool checkInc(int v, int d) {
    if (d == 0) return 1;
    int p = __lg(d);
    return inc[v][p] && inc[goUp(v, d - pw(p))][p];
}


bool checkDec(int v, int d) {
    if (d == 0) return 1;
    int p = __lg(d);
    return dec[v][p] && dec[goUp(v, d - pw(p))][p];
}

int getLastEdge(int a, int b) {
    if (isUpper(a, b)) {
        return val[b];
    }
    if (isUpper(b, a)) {
        int v = goUp(a, dep[a] - dep[b] - 1);
        return val[v];
    }
    return val[b];
}

int checkPath(int a, int b) {
    if (isUpper(a, b)) {
        return checkDec(b, dep[b] - dep[a]);
    }
    if (isUpper(b, a)) {
        return checkInc(a, dep[a] - dep[b]);
    }
    int c = getLCA(a, b);

    int e1 = val[goUp(a, dep[a] - dep[c] - 1)];
    int e2 = val[goUp(b, dep[b] - dep[c] - 1)];
    if (e1 > e2) return 0;

    return checkInc(a, dep[a] - dep[c]) && checkDec(b, dep[b] - dep[c]);
}

int main() {
#ifndef LOCAL
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
#else
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
#endif

    cin >> n >> k;

    fr (i, 1, n + k - 1) {
        char c;
        cin >> c;
        if (c == 'S') {
            int a, b;
            cin >> a >> b;

            g[a].pb({b, i});
            g[b].pb({a, i});

            // cout << a << " " << b << " " << i << "\n";
        }
        if (c == 'Q') {
            int a, d;
            cin >> a >> d;
            Q.pb({i, a, d});
        }
        if (c == 'C') {
            int x;
            cin >> x;
            Q.pb({i, x, -1});
        }
    }

    dfs();

    fr (i, 1, n) {
        if (par[i]) {
            dec[i][0] = 1;
            inc[i][0] = 1;
        }
    }

    fr (p, 1, 19) {
        fr (i, 1, n) {
            if (up[i][p] && inc[i][p - 1] && inc[up[i][p - 1]][p - 1]) {
                if (val[goUp(i, pw(p - 1) - 1)] < val[up[i][p - 1]]) {
                    inc[i][p] = 1;
                }
            }

            if (up[i][p] && dec[i][p - 1] && dec[up[i][p - 1]][p - 1]) {
                if (val[goUp(i, pw(p - 1) - 1)] > val[up[i][p - 1]]) {
                    dec[i][p] = 1;
                }
            }
        }
    }

    fe (cur, Q) {
        if (cur[2] != -1) {

            if (cur[2] == cur[1]) {
                cout << "yes\n";
                continue;
            }
            // cout << "CHECK PATH " << cur[2] << " " << cur[1] << " " << "t: " << cur[0] << "\n"; 
            // cout << "Last edge: " << getLastEdge(cur[2], cur[1]) << "\n";
            if (checkPath(cur[2], cur[1]) && getLastEdge(cur[2], cur[1]) < cur[0]) {
                cout << "yes\n";
            } else {
                cout << "no\n";
            }
        } else {
            while(1);
        }
    }

    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 9280 KB Output is correct
2 Correct 56 ms 11160 KB Output is correct
3 Correct 41 ms 11316 KB Output is correct
4 Correct 49 ms 11456 KB Output is correct
5 Correct 28 ms 11612 KB Output is correct
6 Correct 42 ms 11248 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 9280 KB Output is correct
2 Correct 56 ms 11160 KB Output is correct
3 Correct 41 ms 11316 KB Output is correct
4 Correct 49 ms 11456 KB Output is correct
5 Correct 28 ms 11612 KB Output is correct
6 Correct 42 ms 11248 KB Output is correct
7 Execution timed out 3561 ms 9792 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9288 KB Output is correct
2 Correct 126 ms 33144 KB Output is correct
3 Correct 132 ms 33148 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9288 KB Output is correct
2 Correct 126 ms 33144 KB Output is correct
3 Correct 132 ms 33148 KB Output is correct
4 Execution timed out 3544 ms 9800 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 9292 KB Output is correct
2 Correct 133 ms 36944 KB Output is correct
3 Correct 146 ms 36972 KB Output is correct
4 Correct 146 ms 36860 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 9292 KB Output is correct
2 Correct 133 ms 36944 KB Output is correct
3 Correct 146 ms 36972 KB Output is correct
4 Correct 146 ms 36860 KB Output is correct
5 Execution timed out 3541 ms 9036 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 9272 KB Output is correct
2 Correct 129 ms 33524 KB Output is correct
3 Correct 137 ms 34048 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 9272 KB Output is correct
2 Correct 129 ms 33524 KB Output is correct
3 Correct 137 ms 34048 KB Output is correct
4 Execution timed out 3535 ms 9748 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 9268 KB Output is correct
2 Correct 128 ms 36896 KB Output is correct
3 Correct 141 ms 36920 KB Output is correct
4 Correct 141 ms 36948 KB Output is correct
5 Correct 32 ms 9360 KB Output is correct
6 Correct 139 ms 33520 KB Output is correct
7 Correct 131 ms 34120 KB Output is correct
8 Correct 179 ms 34516 KB Output is correct
9 Correct 178 ms 34504 KB Output is correct
10 Correct 315 ms 38368 KB Output is correct
11 Correct 450 ms 37780 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 9268 KB Output is correct
2 Correct 128 ms 36896 KB Output is correct
3 Correct 141 ms 36920 KB Output is correct
4 Correct 141 ms 36948 KB Output is correct
5 Correct 32 ms 9360 KB Output is correct
6 Correct 139 ms 33520 KB Output is correct
7 Correct 131 ms 34120 KB Output is correct
8 Correct 179 ms 34516 KB Output is correct
9 Correct 178 ms 34504 KB Output is correct
10 Correct 315 ms 38368 KB Output is correct
11 Correct 450 ms 37780 KB Output is correct
12 Execution timed out 3521 ms 9768 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 9280 KB Output is correct
2 Correct 44 ms 11220 KB Output is correct
3 Correct 42 ms 11340 KB Output is correct
4 Correct 51 ms 11364 KB Output is correct
5 Correct 31 ms 11564 KB Output is correct
6 Correct 41 ms 11336 KB Output is correct
7 Correct 34 ms 10132 KB Output is correct
8 Correct 135 ms 33212 KB Output is correct
9 Correct 161 ms 33108 KB Output is correct
10 Correct 32 ms 10176 KB Output is correct
11 Correct 140 ms 40184 KB Output is correct
12 Correct 128 ms 40288 KB Output is correct
13 Correct 146 ms 40188 KB Output is correct
14 Correct 32 ms 10140 KB Output is correct
15 Correct 132 ms 33632 KB Output is correct
16 Correct 172 ms 34080 KB Output is correct
17 Correct 189 ms 34432 KB Output is correct
18 Correct 173 ms 34440 KB Output is correct
19 Correct 337 ms 38368 KB Output is correct
20 Correct 397 ms 37836 KB Output is correct
21 Correct 141 ms 33672 KB Output is correct
22 Correct 137 ms 33804 KB Output is correct
23 Correct 154 ms 33924 KB Output is correct
24 Correct 177 ms 34084 KB Output is correct
25 Correct 158 ms 35296 KB Output is correct
26 Correct 147 ms 33564 KB Output is correct
27 Correct 146 ms 33736 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 9280 KB Output is correct
2 Correct 44 ms 11220 KB Output is correct
3 Correct 42 ms 11340 KB Output is correct
4 Correct 51 ms 11364 KB Output is correct
5 Correct 31 ms 11564 KB Output is correct
6 Correct 41 ms 11336 KB Output is correct
7 Correct 34 ms 10132 KB Output is correct
8 Correct 135 ms 33212 KB Output is correct
9 Correct 161 ms 33108 KB Output is correct
10 Correct 32 ms 10176 KB Output is correct
11 Correct 140 ms 40184 KB Output is correct
12 Correct 128 ms 40288 KB Output is correct
13 Correct 146 ms 40188 KB Output is correct
14 Correct 32 ms 10140 KB Output is correct
15 Correct 132 ms 33632 KB Output is correct
16 Correct 172 ms 34080 KB Output is correct
17 Correct 189 ms 34432 KB Output is correct
18 Correct 173 ms 34440 KB Output is correct
19 Correct 337 ms 38368 KB Output is correct
20 Correct 397 ms 37836 KB Output is correct
21 Correct 141 ms 33672 KB Output is correct
22 Correct 137 ms 33804 KB Output is correct
23 Correct 154 ms 33924 KB Output is correct
24 Correct 177 ms 34084 KB Output is correct
25 Correct 158 ms 35296 KB Output is correct
26 Correct 147 ms 33564 KB Output is correct
27 Correct 146 ms 33736 KB Output is correct
28 Execution timed out 3571 ms 9808 KB Time limit exceeded
29 Halted 0 ms 0 KB -