Submission #573837

#	Time	Username	Problem	Language	Result	Execution time	Memory
573837		talant117408	Inside information (BOI21_servers)	C++17	0 / 100	233 ms	11972 KiB

servers

#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;

struct query {
    char type;
    vector <int> inds;
};

vector <pii> graph[N];
int tin[N], tout[N], timer, up[N][20];
int n, k;
int cur_pos;
int parent[N], depth[N], heavy[N], head[N], pos[N];
int tree[N*4][3];

// 0 - edge max, 1 - edge min, 2 - time max

void update(int v, int l, int r, int pos, int val, int i) {
    if (l == r) {
        tree[v][i] = val;
        return;
    }
    int mid = (l+r) >> 1;
    if (pos <= mid) update(v*2, l, mid, pos, val, i);
    else update(v*2+1, mid+1, r, pos, val, i);
    tree[v][0] = max(tree[v*2][0], tree[v*2+1][0]);
    tree[v][1] = min(tree[v*2][1], tree[v*2+1][1]);
    tree[v][2] = max(tree[v*2][2], tree[v*2+1][2]);
}

int get(int v, int l, int r, int ql, int qr, int i) {
    if (ql > r || l > qr) return (i == 1 ? 2e9 : -2e9);
    if (ql <= l && r <= qr) return tree[v][i];
    int mid = (l+r) >> 1;
    if (i == 1) return min(get(v*2, l, mid, ql, qr, i), get(v*2+1, mid+1, r, ql, qr, i));
    else        return max(get(v*2, l, mid, ql, qr, i), get(v*2+1, mid+1, r, ql, qr, i));
}

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

int get_lca(int a, int b) {
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;
    for (int i = 19; i >= 0; i--) {
        if (!upper(up[a][i], b)) {
            a = up[a][i];
        }
    }
    return up[a][0];
}

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

void decompose(int v, int h) {
    head[v] = h; pos[v] = ++cur_pos;
    if (heavy[v]) {
        decompose(heavy[v], h);
    }
    for (auto to : graph[v]) {
        if (to.first != up[v][0] && to.first != heavy[v]) {
            decompose(to.first, to.first);
        }
    }
}

int get(int a, int b, int i) {
    int res = 0;
    for (; head[a] != head[b]; b = up[head[b]][0]) {
        if (depth[head[a]] > depth[head[b]]) swap(a, b);
        res = max(res, get(1, 1, n, pos[head[b]], pos[b], i));
    }
    if (depth[a] > depth[b]) swap(a, b);
    return max(res, get(1, 1, n, pos[a], pos[b], i));
}

void init() {
    dfs(1, 1);
    decompose(1, 1);
}

int get_anc(int n, int x) {
    for (int bit = 0; bit < 20; bit++) {
        if (x & (1 << bit)) {
            n = up[n][bit];
        }
    }
    return n;
}

void solve() {
    cin >> n >> k;
    int edges = 0;
    vector <query> q;
    for (int i = 0; i < n+k-1; i++) {
        query tmp;
        cin >> tmp.type;
        if (tmp.type == 'C') {
            int a;
            cin >> a;
            tmp.inds.pb(a);
        }
        else {
            int a, b;
            cin >> a >> b;
            tmp.inds.pb(a);
            tmp.inds.pb(b);
            if (tmp.type == 'S') {
                edges++;
                graph[a].pb(mp(b, edges));
                graph[b].pb(mp(a, edges));
            }
        }
        q.pb(tmp);
    }
    init();
    for (int i = 1; i <= n; i++) {
        update(1, 1, n, pos[i], parent[i], 2);
        if (depth[i] == 1) {
            update(1, 1, n, pos[i], parent[i], 0);
            update(1, 1, n, pos[i], -parent[i], 1);
        }
        else if (depth[i] > 1) {
            int val = parent[i]-parent[up[i][0]];
            update(1, 1, n, pos[i], val, 0);
            update(1, 1, n, pos[i], val, 1);
        }
    }
    edges = 0;
    for (int i = 0; i < n+k-1; i++) {
        if (q[i].type == 'S') {
            edges++;
        }
        else if (q[i].type == 'Q') {
            int a = q[i].inds[1];
            int b = q[i].inds[0];
            int lca = get_lca(a, b);
            int val_lca0 = get(lca, lca, 0), val_lca1 = get(lca, lca, 1), time_lca = get(lca, lca, 2);
            //~ cout << a << ' ' << b << endl;
            //~ cout << lca << endl;
            update(1, 1, n, pos[lca], 0, 0);
            update(1, 1, n, pos[lca], 0, 1);
            update(1, 1, n, pos[lca], 0, 2);
            if (a == lca) {
                int B = get_anc(b, depth[b]-depth[a]-1);
                int val_B0 = get(B, B, 0), val_B1 = get(B, B, 1);
                update(1, 1, n, pos[B], 0, 0);
                update(1, 1, n, pos[B], 0, 1);
                
                auto res = get(a, b, 1), time = get(a, b, 2);
                if (res >= 0 && time <= edges) {
                    cout << "yes" << endl;
                }
                else {
                    cout << "no" << endl;
                }
                
                update(1, 1, n, pos[B], val_B0, 0);
                update(1, 1, n, pos[B], val_B1, 1);
            }
            else if (b == lca) {
                int A = get_anc(a, depth[a]-depth[b]-1);
                int val_A0 = get(A, A, 0), val_A1 = get(A, A, 1);
                update(1, 1, n, pos[A], 0, 0);
                update(1, 1, n, pos[A], 0, 1);
                
                auto res = get(a, b, 0), time = get(a, b, 2);
                if (res <= 0 && time <= edges) {
                    cout << "yes" << endl;
                }
                else {
                    cout << "no" << endl;
                }
                
                update(1, 1, n, pos[A], val_A0, 0);
                update(1, 1, n, pos[A], val_A1, 1);
            }
            else {
                int A = get_anc(a, depth[a]-depth[lca]-1);
                int val_A0 = get(A, A, 0), val_A1 = get(A, A, 1);
                int B = get_anc(b, depth[b]-depth[lca]-1);
                int val_B0 = get(B, B, 0), val_B1 = get(B, B, 1);
                update(1, 1, n, pos[A], -parent[A]+parent[B], 0);
                update(1, 1, n, pos[A], -parent[A]+parent[B], 1);
                update(1, 1, n, pos[B], -parent[B]+parent[A], 0);
                update(1, 1, n, pos[B], -parent[B]+parent[A], 1);
                //~ cout << a << ' ' << b << endl;
                //~ cout << A << ' ' << B << endl;
                //~ cout << parent[A] << ' ' << parent[B] << endl;
                //~ cout << lca << endl;
                auto res_max = get(b, lca, 1), res_min = get(lca, a, 0), time = get(a, b, 2);
                //~ cout << res_max << ' ' << res_min << ' ' << time << endl;
                if (res_min >= 0 && res_max <= 0 && time <= edges) {
                    cout << "yes" << endl;
                }
                else {
                    cout << "no" << endl;
                }
                
                update(1, 1, n, pos[B], val_B0, 0);
                update(1, 1, n, pos[B], val_B1, 1);
                update(1, 1, n, pos[A], val_A0, 0);
                update(1, 1, n, pos[A], val_A1, 1);
            }
            update(1, 1, n, pos[lca], val_lca0, 0);
            update(1, 1, n, pos[lca], val_lca1, 1);
            update(1, 1, n, pos[lca], time_lca, 2);
        }
        else {
            cout << 1 << 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: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 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