제출 #573849

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
573849		talant117408	Inside information (BOI21_servers)	C++17	50 / 100	212 ms	40288 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;
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
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5