oj.uz

Submission #714931

# Submission time Handle Problem Language Result Execution time Memory
714931 2023-03-25T14:09:54 Z stevancv Inside information (BOI21_servers) C++14
50 / 100
 374 ms 39040 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 120000 + 2;
const int inf = 1e9;
vector<array<int, 2>> g[N];
int par[N][17], in[N], out[N], val[N], donji[N], dep[N], tsz;
bool inc[N][17], dek[N][17];
void Dfs(int s, int e) {
    in[s] = ++tsz;
    par[s][0] = e;
    inc[s][0] = 1;
    dek[s][0] = 1;
    for (int i = 1; i < 17; i++) {
        int u = par[s][i - 1];
        par[s][i] = par[u][i - 1];
        inc[s][i] = inc[s][i - 1] & inc[u][i - 1] & (donji[u] < val[u]);
        dek[s][i] = dek[s][i - 1] & dek[u][i - 1] & (donji[u] > val[u]);
    }
    for (auto zz : g[s]) {
        int u = zz[0]; int i = zz[1];
        if (u == e) continue;
        dep[u] = dep[s] + 1;
        donji[s] = i;
        val[u] = i;
        Dfs(u, s);
    }
    out[s] = tsz;
}
bool Ancestor(int u, int v) {
    return in[u] <= in[v] && out[v] <= out[u];
}
int Lca(int u, int v) {
    if (Ancestor(u, v)) return u;
    if (Ancestor(v, u)) return v;
    for (int i = 16; i >= 0; i--) {
        if (par[u][i] && !Ancestor(par[u][i], v)) u = par[u][i];
    }
    return par[u][0];
}
int Kth(int u, int k) {
    for (int i = 16; i >= 0; i--) {
        if ((1 << i) & k) u = par[u][i];
    }
    return u;
}
bool MozeI(int u, int v) {
    if (u == v) return 1;
    int r = dep[u] - dep[v];
    bool ans = 1;
    for (int i = 16; i >= 0 && ans; i--) {
        if ((1 << i) & r) {
            ans &= inc[u][i];
            r -= (1 << i);
            if (r != 0) ans &= (val[Kth(u, (1 << i) - 1)] < val[par[u][i]]);
            u = par[u][i];
        }
    }
    return ans;
}
bool MozeD(int u, int v) {
    if (u == v) return 1;
    int r = dep[u] - dep[v];
    bool ans = 1;
    for (int i = 16; i >= 0 && ans; i--) {
        if ((1 << i) & r) {
            ans &= dek[u][i];
            r -= (1 << i);
            if (r != 0) ans &= (val[Kth(u, (1 << i) - 1)] > val[par[u][i]]);
            u = par[u][i];
        }
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector<array<int, 3>> all;
    int cnt = 0;
    for (int i = 0; i < n + k - 1; i++) {
        char ch; cin >> ch;
        int u, v;
        if (ch == 'C') {
            cin >> u;
            continue;
        }
        cin >> u >> v;
        if (ch == 'S') {
            g[u].push_back({v, cnt});
            g[v].push_back({u, cnt});
            all.push_back({0, u, v});
            cnt += 1;
        }
        else all.push_back({1, u, v});
    }
    Dfs(1, 0);
    cnt = 0;
    for (int i = 0; i < all.size(); i++) {
        if (all[i][0] == 0) {
            cnt += 1;
            continue;
        }
        int u = all[i][1]; int v = all[i][2];
        swap(u, v);
        if (u == v) {
            cout << "yes" << en;
            continue;
        }
        int lca = Lca(u, v);
        int uu, vv; uu = vv = -1;
        if (u != lca) uu = val[Kth(u, dep[u] - dep[lca] - 1)];
        if (v != lca) vv = val[Kth(v, dep[v] - dep[lca] - 1)];
        bool ans = MozeI(u, lca) & MozeD(v, lca);
        if (uu != -1 && vv != -1) ans &= uu < vv;
        int lst = val[v];
        if (v == lca) lst = uu;
        ans &= lst < cnt;
        if (ans) cout << "yes" << en;
        else cout << "no" << en;
    }
    return 0;
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for (int i = 0; i < all.size(); i++) {
      |                     ~~^~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 5952 KB Output is correct
2 Correct 56 ms 6980 KB Output is correct
3 Correct 65 ms 7136 KB Output is correct
4 Correct 72 ms 7096 KB Output is correct
5 Correct 47 ms 7368 KB Output is correct
6 Correct 44 ms 7056 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 5952 KB Output is correct
2 Correct 56 ms 6980 KB Output is correct
3 Correct 65 ms 7136 KB Output is correct
4 Correct 72 ms 7096 KB Output is correct
5 Correct 47 ms 7368 KB Output is correct
6 Correct 44 ms 7056 KB Output is correct
7 Incorrect 61 ms 5784 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 39 ms 5920 KB Output is correct
2 Correct 143 ms 27764 KB Output is correct
3 Correct 145 ms 27684 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5920 KB Output is correct
2 Correct 143 ms 27764 KB Output is correct
3 Correct 145 ms 27684 KB Output is correct
4 Incorrect 36 ms 5836 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 43 ms 5952 KB Output is correct
2 Correct 158 ms 38980 KB Output is correct
3 Correct 146 ms 38976 KB Output is correct
4 Correct 161 ms 38992 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 5952 KB Output is correct
2 Correct 158 ms 38980 KB Output is correct
3 Correct 146 ms 38976 KB Output is correct
4 Correct 161 ms 38992 KB Output is correct
5 Incorrect 31 ms 5820 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 62 ms 5912 KB Output is correct
2 Correct 148 ms 28320 KB Output is correct
3 Correct 133 ms 28884 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 5912 KB Output is correct
2 Correct 148 ms 28320 KB Output is correct
3 Correct 133 ms 28884 KB Output is correct
4 Incorrect 52 ms 5752 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 40 ms 6068 KB Output is correct
2 Correct 150 ms 39004 KB Output is correct
3 Correct 161 ms 39040 KB Output is correct
4 Correct 177 ms 38972 KB Output is correct
5 Correct 42 ms 6004 KB Output is correct
6 Correct 141 ms 28360 KB Output is correct
7 Correct 145 ms 28924 KB Output is correct
8 Correct 255 ms 29184 KB Output is correct
9 Correct 177 ms 29180 KB Output is correct
10 Correct 283 ms 34788 KB Output is correct
11 Correct 303 ms 33912 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 6068 KB Output is correct
2 Correct 150 ms 39004 KB Output is correct
3 Correct 161 ms 39040 KB Output is correct
4 Correct 177 ms 38972 KB Output is correct
5 Correct 42 ms 6004 KB Output is correct
6 Correct 141 ms 28360 KB Output is correct
7 Correct 145 ms 28924 KB Output is correct
8 Correct 255 ms 29184 KB Output is correct
9 Correct 177 ms 29180 KB Output is correct
10 Correct 283 ms 34788 KB Output is correct
11 Correct 303 ms 33912 KB Output is correct
12 Incorrect 31 ms 5820 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 57 ms 5900 KB Output is correct
2 Correct 56 ms 6916 KB Output is correct
3 Correct 50 ms 7124 KB Output is correct
4 Correct 77 ms 7120 KB Output is correct
5 Correct 49 ms 7380 KB Output is correct
6 Correct 51 ms 7064 KB Output is correct
7 Correct 40 ms 5924 KB Output is correct
8 Correct 136 ms 27708 KB Output is correct
9 Correct 146 ms 27672 KB Output is correct
10 Correct 35 ms 5968 KB Output is correct
11 Correct 151 ms 38964 KB Output is correct
12 Correct 128 ms 38996 KB Output is correct
13 Correct 183 ms 38904 KB Output is correct
14 Correct 47 ms 5948 KB Output is correct
15 Correct 146 ms 28340 KB Output is correct
16 Correct 173 ms 28812 KB Output is correct
17 Correct 232 ms 29236 KB Output is correct
18 Correct 180 ms 29152 KB Output is correct
19 Correct 219 ms 34776 KB Output is correct
20 Correct 374 ms 33864 KB Output is correct
21 Correct 160 ms 28216 KB Output is correct
22 Correct 152 ms 28568 KB Output is correct
23 Correct 246 ms 28596 KB Output is correct
24 Correct 209 ms 28688 KB Output is correct
25 Correct 298 ms 31368 KB Output is correct
26 Correct 216 ms 28628 KB Output is correct
27 Correct 226 ms 28580 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 5900 KB Output is correct
2 Correct 56 ms 6916 KB Output is correct
3 Correct 50 ms 7124 KB Output is correct
4 Correct 77 ms 7120 KB Output is correct
5 Correct 49 ms 7380 KB Output is correct
6 Correct 51 ms 7064 KB Output is correct
7 Correct 40 ms 5924 KB Output is correct
8 Correct 136 ms 27708 KB Output is correct
9 Correct 146 ms 27672 KB Output is correct
10 Correct 35 ms 5968 KB Output is correct
11 Correct 151 ms 38964 KB Output is correct
12 Correct 128 ms 38996 KB Output is correct
13 Correct 183 ms 38904 KB Output is correct
14 Correct 47 ms 5948 KB Output is correct
15 Correct 146 ms 28340 KB Output is correct
16 Correct 173 ms 28812 KB Output is correct
17 Correct 232 ms 29236 KB Output is correct
18 Correct 180 ms 29152 KB Output is correct
19 Correct 219 ms 34776 KB Output is correct
20 Correct 374 ms 33864 KB Output is correct
21 Correct 160 ms 28216 KB Output is correct
22 Correct 152 ms 28568 KB Output is correct
23 Correct 246 ms 28596 KB Output is correct
24 Correct 209 ms 28688 KB Output is correct
25 Correct 298 ms 31368 KB Output is correct
26 Correct 216 ms 28628 KB Output is correct
27 Correct 226 ms 28580 KB Output is correct
28 Incorrect 45 ms 5864 KB Extra information in the output file
29 Halted 0 ms 0 KB -