oj.uz

Submission #573849

# Submission time Handle Problem Language Result Execution time Memory
573849 2022-06-07T10:26:34 Z talant117408 Inside information (BOI21_servers) C++17
50 / 100
 212 ms 40288 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'
 
int mod = 1e9+7;
 
ll modulo(ll a) {
    return ((a % mod) + mod) % mod;
}
 
ll add(ll a, ll b) {
    return modulo(a + b);
}
 
ll mult(ll a, ll b) {
    return modulo(a * b);
}
 
ll binpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b&1) {
            res = mult(res, a);
        }
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

const int N = 120007;
vector <pii> graph[N];
int tin[N], tout[N], timer, up[N][20], parent[N], lift[N][20];
int depth[N];
int n, k;

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

bool get(int a, int b, int time) {
    if (a == b) return true;
    if (upper(a, b)) {
        int lca = b, sum = 0;
        for (int bit = 19; ~bit; bit--) {
            if (!upper(up[lca][bit], a)) {
                sum += lift[lca][bit];
                lca = up[lca][bit];
            }
        }
        return (sum == 0 && parent[lca] <= time);
    }
    else if (upper(b, a)) {
        swap(a, b);
        int left = b, sum = 0;
        for (int bit = 19; ~bit; bit--) {
            if (!upper(up[b][bit], a)) {
                sum += lift[b][bit];
                b = up[b][bit];
            }
        }
        return (sum == depth[left]-depth[b] && parent[left] <= time);
    }
    int suma = 0, sumb = 0, left = a;
    for (int bit = 19; ~bit; bit--) {
        if (!upper(up[b][bit], a)) {
            sumb += lift[b][bit];
            b = up[b][bit];
        }
        if (!upper(up[a][bit], b)) {
            suma += lift[a][bit];
            a = up[a][bit];
        }
    }
    return (suma == depth[left]-depth[a] && sumb == 0 && parent[a] > parent[b] && parent[left] <= time);
}

void dfs(int v, int p) {
    tin[v] = ++timer;
    up[v][0] = p;
    lift[v][0] = (parent[v] > parent[up[v][0]]);
    for (int i = 1; i < 20; i++) {
        up[v][i] = up[up[v][i-1]][i-1];
        lift[v][i] = lift[v][i-1] + lift[up[v][i-1]][i-1];
    }
    for (auto x : graph[v]) {
        if (x.first == p) continue;
        parent[x.first] = x.second;
        depth[x.first] = depth[v] + 1;
        dfs(x.first, v);
    }
    tout[v] = ++timer;
}

void solve() {
    cin >> n >> k;
    vector <array <int, 3>> q;
    for (int i = 1; i < n+k; i++) {
        char tmp;
        cin >> tmp;
        if (tmp == 'C') {
            int a;
            cin >> a;
        }
        else {
            int a, b;
            cin >> a >> b;
            if (tmp == 'S') {
                graph[a].pb(mp(b, i));
                graph[b].pb(mp(a, i));
            }
            else {
                q.pb({a, b, i});
            }
        }
    }
    dfs(1, 1);
    for (auto to : q) {
        if (get(to[0], to[1], to[2])) cout << "yes" << endl;
        else cout << "no" << endl;
    }
}

int main() {
    do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}
/*
4 4
S 1 2
S 1 3
S 3 4
Q 2 1
Q 2 2
Q 2 3
Q 2 4
*/

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5064 KB Output is correct
2 Correct 48 ms 7224 KB Output is correct
3 Correct 36 ms 7216 KB Output is correct
4 Correct 48 ms 7252 KB Output is correct
5 Correct 48 ms 7428 KB Output is correct
6 Correct 51 ms 7124 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5064 KB Output is correct
2 Correct 48 ms 7224 KB Output is correct
3 Correct 36 ms 7216 KB Output is correct
4 Correct 48 ms 7252 KB Output is correct
5 Correct 48 ms 7428 KB Output is correct
6 Correct 51 ms 7124 KB Output is correct
7 Incorrect 33 ms 5788 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 31 ms 5040 KB Output is correct
2 Correct 112 ms 30296 KB Output is correct
3 Correct 115 ms 30256 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5040 KB Output is correct
2 Correct 112 ms 30296 KB Output is correct
3 Correct 115 ms 30256 KB Output is correct
4 Incorrect 32 ms 4924 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 32 ms 5088 KB Output is correct
2 Correct 135 ms 40288 KB Output is correct
3 Correct 137 ms 40188 KB Output is correct
4 Correct 175 ms 40100 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5088 KB Output is correct
2 Correct 135 ms 40288 KB Output is correct
3 Correct 137 ms 40188 KB Output is correct
4 Correct 175 ms 40100 KB Output is correct
5 Incorrect 32 ms 5812 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 33 ms 5052 KB Output is correct
2 Correct 118 ms 33560 KB Output is correct
3 Correct 133 ms 34044 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5052 KB Output is correct
2 Correct 118 ms 33560 KB Output is correct
3 Correct 133 ms 34044 KB Output is correct
4 Incorrect 34 ms 5856 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 32 ms 5064 KB Output is correct
2 Correct 131 ms 40208 KB Output is correct
3 Correct 138 ms 40188 KB Output is correct
4 Correct 200 ms 40060 KB Output is correct
5 Correct 33 ms 5960 KB Output is correct
6 Correct 113 ms 33568 KB Output is correct
7 Correct 115 ms 34048 KB Output is correct
8 Correct 181 ms 34464 KB Output is correct
9 Correct 147 ms 34472 KB Output is correct
10 Correct 165 ms 38272 KB Output is correct
11 Correct 212 ms 37624 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5064 KB Output is correct
2 Correct 131 ms 40208 KB Output is correct
3 Correct 138 ms 40188 KB Output is correct
4 Correct 200 ms 40060 KB Output is correct
5 Correct 33 ms 5960 KB Output is correct
6 Correct 113 ms 33568 KB Output is correct
7 Correct 115 ms 34048 KB Output is correct
8 Correct 181 ms 34464 KB Output is correct
9 Correct 147 ms 34472 KB Output is correct
10 Correct 165 ms 38272 KB Output is correct
11 Correct 212 ms 37624 KB Output is correct
12 Incorrect 33 ms 5756 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 31 ms 5064 KB Output is correct
2 Correct 42 ms 7104 KB Output is correct
3 Correct 37 ms 7292 KB Output is correct
4 Correct 50 ms 7248 KB Output is correct
5 Correct 53 ms 7536 KB Output is correct
6 Correct 43 ms 7124 KB Output is correct
7 Correct 31 ms 5896 KB Output is correct
8 Correct 122 ms 33060 KB Output is correct
9 Correct 118 ms 33132 KB Output is correct
10 Correct 33 ms 5972 KB Output is correct
11 Correct 140 ms 40168 KB Output is correct
12 Correct 135 ms 40136 KB Output is correct
13 Correct 168 ms 40128 KB Output is correct
14 Correct 36 ms 5876 KB Output is correct
15 Correct 117 ms 33724 KB Output is correct
16 Correct 126 ms 33992 KB Output is correct
17 Correct 174 ms 34432 KB Output is correct
18 Correct 148 ms 34392 KB Output is correct
19 Correct 187 ms 38224 KB Output is correct
20 Correct 207 ms 37628 KB Output is correct
21 Correct 126 ms 33596 KB Output is correct
22 Correct 149 ms 33712 KB Output is correct
23 Correct 134 ms 33884 KB Output is correct
24 Correct 129 ms 33984 KB Output is correct
25 Correct 169 ms 35296 KB Output is correct
26 Correct 136 ms 33500 KB Output is correct
27 Correct 131 ms 33584 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5064 KB Output is correct
2 Correct 42 ms 7104 KB Output is correct
3 Correct 37 ms 7292 KB Output is correct
4 Correct 50 ms 7248 KB Output is correct
5 Correct 53 ms 7536 KB Output is correct
6 Correct 43 ms 7124 KB Output is correct
7 Correct 31 ms 5896 KB Output is correct
8 Correct 122 ms 33060 KB Output is correct
9 Correct 118 ms 33132 KB Output is correct
10 Correct 33 ms 5972 KB Output is correct
11 Correct 140 ms 40168 KB Output is correct
12 Correct 135 ms 40136 KB Output is correct
13 Correct 168 ms 40128 KB Output is correct
14 Correct 36 ms 5876 KB Output is correct
15 Correct 117 ms 33724 KB Output is correct
16 Correct 126 ms 33992 KB Output is correct
17 Correct 174 ms 34432 KB Output is correct
18 Correct 148 ms 34392 KB Output is correct
19 Correct 187 ms 38224 KB Output is correct
20 Correct 207 ms 37628 KB Output is correct
21 Correct 126 ms 33596 KB Output is correct
22 Correct 149 ms 33712 KB Output is correct
23 Correct 134 ms 33884 KB Output is correct
24 Correct 129 ms 33984 KB Output is correct
25 Correct 169 ms 35296 KB Output is correct
26 Correct 136 ms 33500 KB Output is correct
27 Correct 131 ms 33584 KB Output is correct
28 Incorrect 30 ms 5820 KB Extra information in the output file
29 Halted 0 ms 0 KB -