Submission #1196251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196251		anmattroi	Inside information (BOI21_servers)	C++20	100 / 100	1084 ms	114848 KiB

servers

#include <bits/stdc++.h>
#define maxn 120005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

const int INF = 1'000'000'000;

int n, k;
vector<ii> adj[maxn];

struct query {
    char type; int u, v;
    query() {}
} queries[maxn+maxn];

int pe[maxn], d[maxn], f[17][maxn], g[17][maxn], nho[maxn], par[maxn], sz[maxn], tsz = 0, start[maxn], stop[maxn], id = 0;
vector<int> lis[maxn];
int ASC[maxn], DESC[maxn];

int isAncestor(int u, int v) {
    return start[u] <= start[v] && stop[v] <= stop[u];
}


int jump(int x, int k) {
    for (int i = 0; i < 17; i++) if (k>>i&1) x = f[i][x];
    return x;
}

int LCA(int u, int v) {
    if (d[u] > d[v]) swap(u, v);
    if (d[u] < d[v]) v = jump(v, d[v]-d[u]);
    if (u == v) return u;
    for (int i = 16; i >= 0; i--)
    if (f[i][u] != f[i][v]) {
        u = f[i][u];
        v = f[i][v];
    }
    return f[0][u];
}

void pfs(int u, int dad) {
    start[u] = ++id;
    f[0][u] = dad; g[0][u] = pe[u];
    for (int i = 1; i < 17; i++) {
        f[i][u] = f[i-1][f[i-1][u]];
        g[i][u] = max(g[i-1][u], g[i-1][f[i-1][u]]);
    }
    ASC[u] = (pe[u] < pe[dad] ? ASC[dad] : dad);
    DESC[u] = (pe[u] > pe[dad] ? DESC[dad] : dad);

    for (auto [v, l] : adj[u])
    if (v != dad) {
        pe[v] = l;
        d[v] = d[u]+1;
        pfs(v, u);
    }
    stop[u] = id;
}

int ASCENSION(int u, int w) {
    return d[ASC[u]] <= d[w];
}

int DECENSION(int u, int w) {
    return d[DESC[u]] <= d[w];
}

int MAXIMUS(int u, int v, int w, int TIME) {
    int k, ans = 0;
    k = d[u]-d[w];
    for (int i = 0; i < 17; i++) if (k>>i&1) {
        ans = max(ans, g[i][u]);
        u = f[i][u];
    }
    k = d[v]-d[w];
    for (int i = 0; i < 17; i++) if (k>>i&1) {
        ans = max(ans, g[i][v]);
        v = f[i][v];
    }
    return ans < TIME;
}

int possiblePath(int u, int v, int TIME) {
     int w = LCA(u, v);
    int condition = 1;
    condition &= ASCENSION(u, w);
    condition &= DECENSION(v, w);
    if (w != u && w != v) condition &= (pe[jump(u, d[u]-d[w]-1)] < pe[jump(v, d[v]-d[w]-1)]);
    condition &= MAXIMUS(u, v, w, TIME);
    return condition;
}

int lastEdge(int u, int v) {
    if (isAncestor(v, u)) return pe[jump(u, d[u]-d[v]-1)];
    return pe[v];
}

int firstEdge(int u, int v) {
    if (isAncestor(u, v)) return pe[jump(v, d[v]-d[u]-1)];
    return pe[u];
}

void queryQ(int u, int v, int TIME) {
    cout << (possiblePath(u, v, TIME) ? "yes\n" : "no\n");
}

void resz(int u, int dad) {
    ++tsz; sz[u] = 1;
    for (auto [v, l] : adj[u])
    if (!nho[v] && v != dad) {
        resz(v, u);
        sz[u] += sz[v];
    }
}

int findCentroid(int u, int dad) {
    for (auto [v, l] : adj[u])
        if (v != dad && !nho[v] && sz[v] > tsz/2) return findCentroid(v, u);
    return u;
}

void dcp(int u, int r) {
    tsz = 0;
    resz(u, 0);
    int C = findCentroid(u, 0);
    nho[C] = 1;
    par[C] = r;
    for (auto [v, l] : adj[C])
        if (!nho[v]) dcp(v, C);
}

struct node {
    int val = 0;
    node *leftChild = nullptr, *rightChild = nullptr;

    node() {}
    node(int _val) : val(_val) {}

    void extendLeft() {
        if (leftChild == nullptr) leftChild = new node;
    }
    void extendRight() {
        if (rightChild == nullptr) rightChild = new node;
    }
};

node *st[maxn];
void upd(int u, int d, node *cur, int lo = 1, int hi = n+k-1) {
    if (lo == hi) {
        cur->val += d;
        return;
    }
    int mid = (lo + hi) >> 1;
    if (u <= mid) {
        cur->extendLeft();
        upd(u, d, cur->leftChild, lo, mid);
    } else {
        cur->extendRight();
        upd(u, d, cur->rightChild, mid+1, hi);
    }
    cur->val = (cur->leftChild == nullptr ? 0 : cur->leftChild->val)
            +  (cur->rightChild == nullptr ? 0 : cur->rightChild->val);
}

int get(int u, int v, node *cur, int lo = 1, int hi = n+k-1) {
    if (u <= lo && hi <= v) return cur->val;
    int mid = (lo + hi) >> 1;
    return ((u <= mid && cur->leftChild != nullptr) ? get(u, v, cur->leftChild, lo, mid) : 0)
        +  ((v > mid && cur->rightChild != nullptr) ? get(u, v, cur->rightChild, mid+1, hi) : 0);
}

int ID = 0;

struct pizza {
    int x, y, z;
    pizza() {}
    pizza(int _x, int _y, int _z) : x(_x), y(_y), z(_z) {}
    bool operator < (const pizza &other) const {
        return y < other.y;
    }

} skibidi[17*maxn];

void init() {
    for (int i = 1; i <= n; i++) st[i] = new node(0);

    for (int i = 1; i <= n; i++) {
        int j = par[i];
        while (j) {
            if (!possiblePath(j, i, INT_MAX)) {
                j = par[j];
                continue;
            }
            skibidi[++ID] = pizza(j, lastEdge(j, i), firstEdge(j, i));
            j = par[j];
        }
    }
    sort(skibidi + 1, skibidi + ID + 1);

}


void queryC(int x, int TIME) {
    int ans = st[x]->val+1;
    for (int y = x; y = par[y];) {
        if (!possiblePath(x, y, TIME)) continue;
        ++ans;
        int xd = lastEdge(x, y);
        if (xd < n+k-1) ans += get(xd+1, n+k-1, st[y]);
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;
    for (int i = 1; i < n+k; i++) {
        cin >> queries[i].type >> queries[i].u;
        if (queries[i].type != 'C') cin >> queries[i].v;
        if (queries[i].type == 'S') {
            adj[queries[i].u].emplace_back(queries[i].v, i);
            adj[queries[i].v].emplace_back(queries[i].u, i);
        }
    }

    pfs(1, 0);
    dcp(1, 0);
    init();
    for (int i = 1, it = 1; i < n+k; i++) {
        while (it <= ID && skibidi[it].y < i) {
            auto [x, y, z] = skibidi[it];
            upd(z, 1, st[x]);
            ++it;
        }
        if (queries[i].type == 'Q') queryQ(queries[i].v, queries[i].u, i);
        else if (queries[i].type == 'C') queryC(queries[i].u, i);
    }
}

• Subtask 1-1: 2 / 2
• Subtask 1-2: 3 / 3
• Subtask 2-1: 2 / 2
• Subtask 2-2: 3 / 3
• Subtask 3-1: 5 / 5
• Subtask 3-2: 5 / 5
• Subtask 4-1: 10 / 10
• Subtask 4-2: 10 / 10
• Subtask 5-1: 12 / 12
• Subtask 5-2: 13 / 13
• Subtask 6-1: 17 / 17
• Subtask 6-2: 18 / 18