Submission #588757

#	Time	Username	Problem	Language	Result	Execution time	Memory
588757		maomao90	Inside information (BOI21_servers)	C++17	100 / 100	761 ms	162796 KiB

servers

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 300005;
const int MAXL = 20;

struct Qry {
    char t;
    int a, b;
};

struct Edge {
    int v, lo, hi;
    bool inc, dec;
    Edge operator+ (const Edge &o) const {
        if (v == -1) {
            return o;
        }
        if (o.v == -1) {
            return *this;
        }
        Edge res;
        res.v = o.v;
        res.lo = lo;
        res.hi = o.hi;
        res.inc = inc && o.inc && hi < o.lo;
        res.dec = dec && o.dec && hi > o.lo;
        return res;
    }
    Edge operator~ () const {
        return {v, hi, lo, dec, inc};
    }
    friend ostream& operator<< (ostream &os, const Edge &o) {
        return os << "(" << o.v << ' ' << o.lo << ' ' << o.hi << ' ' << o.inc << ' ' << o.dec << ")";
    }
};

int n, k;
vector<Edge> adj[MAXN];
Qry qry[MAXN];
int ans[MAXN];

Edge p[MAXL][MAXN];
int lvl[MAXN];
void dfs(int u) {
    REP (k, 1, MAXL) {
        if (p[k - 1][u].v == -1 || p[k - 1][p[k - 1][u].v].v == -1) {
            p[k][u] = {-1, -1, -1, 0, 0};
        } else {
            p[k][u] = p[k - 1][u] + p[k - 1][p[k - 1][u].v];
        }
    }
    for (Edge e : adj[u]) {
        if (e.v == p[0][u].v) {
            continue;
        }
        lvl[e.v] = lvl[u] + 1;
        p[0][e.v] = {u, e.lo, e.hi, 1, 1};
        dfs(e.v);
    }
}

int sub[MAXN], cp[MAXN];
Edge pth[MAXL][MAXN];
vii ev[MAXN];
void getst(int u, int p, int l) {
    sub[u] = 1;
    for (Edge e : adj[u]) {
        if (e.v == p || lvl[e.v] != -1) {
            continue;
        }
        if (l > 0) {
            pth[l - 1][e.v] = e + pth[l - 1][u];
        }
        getst(e.v, u, l);
        sub[u] += sub[e.v];
    }
}
int getcent(int u, int p, int s) {
    for (Edge e : adj[u]) {
        if (e.v == p || lvl[e.v] != -1) {
            continue;
        }
        if (sub[e.v] > s / 2) {
            return getcent(e.v, u, s);
        }
    }
    return u;
}
void build(int u, int p, int l) {
    getst(u, -1, l);
    int cent = getcent(u, -1, sub[u]);
    cp[cent] = p;
    lvl[cent] = l;
    for (Edge e : adj[cent]) {
        if (e.v == p || lvl[e.v] != -1) {
            continue;
        }
        pth[l][e.v] = e;
        build(e.v, cent, l + 1);
    }
}

int st[MAXN * 40], lc[MAXN * 40], rc[MAXN * 40], ptr;
void incre(int p, int x, int u, int lo = 1, int hi = n + k) {
    if (lo == hi) {
        st[u] += x;
        return;
    }
    int mid = lo + hi >> 1;
    if (p <= mid) {
        if (lc[u] == 0) {
            lc[u] = ptr++;
        }
        incre(p, x, lc[u], lo, mid);
    } else {
        if (rc[u] == 0) {
            rc[u] = ptr++;
        }
        incre(p, x, rc[u], mid + 1, hi);
    }
    st[u] = st[lc[u]] + st[rc[u]];
}
int qsm(int s, int e, int u, int lo = 1, int hi = n + k) {
    if (lo >= s && hi <= e) {
        return st[u];
    }
    int mid = lo + hi >> 1;
    int res = 0;
    if (s <= mid) {
        res += qsm(s, e, lc[u], lo, mid);
    }
    if (e > mid) {
        res += qsm(s, e, rc[u], mid + 1, hi);
    }
    return res;
}

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> n >> k;
    REP (i, 1, n + k) {
        char t; cin >> t;
        if (t == 'S') {
            int a, b; cin >> a >> b;
            adj[a].pb({b, i, i, 1, 1});
            adj[b].pb({a, i, i, 1, 1});
            qry[i] = {t, a, b};
        } else if (t == 'Q') {
            int a, b; cin >> a >> b;
            qry[i] = {t, a, b};
        } else {
            int a; cin >> a;
            qry[i] = {t, a, -1};
        }
    }
    REP (k, 0, MAXL) {
        p[k][1] = {-1, -1, -1, 0, 0};
    }
    dfs(1);
    REP (i, 1, n + k) {
        auto [t, a, b] = qry[i];
        if (t == 'S') {
        } else if (t == 'Q') {
            if (a == b) {
                ans[i] = 1;
                continue;
            }
            Edge lft = {-1, -1, -1, 0, 0}, rht = {-1, -1, -1, 0, 0};
            bool swp = 0;
            if (lvl[a] < lvl[b]) {
                swap(a, b);
                swp = 1;
            }
            RREP (k, MAXL - 1, 0) {
                if (p[k][a].v != -1 && lvl[p[k][a].v] >= lvl[b]) {
                    lft = lft + p[k][a];
                    a = p[k][a].v;
                }
            }
            if (a != b) {
                RREP (k, MAXL - 1, 0) {
                    if (p[k][a].v != p[k][b].v) {
                        lft = lft + p[k][a];
                        a = p[k][a].v;
                        rht = rht + p[k][b];
                        b = p[k][b].v;
                    }
                }
                lft = lft + p[0][a];
                a = p[0][a].v;
                rht = rht + p[0][b];
                b = p[0][b].v;
            }
            assert(a == b);
            if (swp) {
                swap(lft, rht);
                swap(a, b);
            }
            Edge res = rht + ~lft;
            if (res.inc && res.hi <= i) {
                ans[i] = 1;
            } else {
                ans[i] = 0;
            }
        } else {
        }
    }
    memset(lvl, -1, sizeof lvl);
    build(1, -1, 0);
    ptr = n + 1;
    REP (i, 1, n + 1) {
        int a = i;
        cerr << i << '\n';
        ev[0].pb({n + k, i});
        RREP (j, lvl[i] - 1, 0) {
            a = cp[a];
            if (pth[j][i].dec) {
                ev[pth[j][i].lo].pb({pth[j][i].hi, a});
                cerr << ' ' << a << ' ' << pth[j][i].lo << ' ' << pth[j][i].hi << '\n';
            }
        }
        assert(cp[a] == -1);
    }
    REP (i, 0, n + k) {
        auto [t, a, b] = qry[i];
        if (i == 0 || t == 'S') {
            for (auto [x, y] : ev[i]) {
                incre(x, 1, y);
            }
        } else if (t == 'Q') {
        } else {
            cerr << a << '\n';
            ans[i] = st[a];
            cerr << ' ' << st[a] << '\n';
            int u = a;
            RREP (l, lvl[a] - 1, 0) {
                u = cp[u];
                Edge e = pth[l][a];
                if (e.inc && e.hi <= i) {
                    int tmp = qsm(e.hi + 1, n + k, u);
                    ans[i] += tmp;
                    cerr << ' ' << u << ' ' << e.hi << ' ' << tmp << '\n';
                }
            }
            assert(cp[u] == -1);
        }
    }
    REP (i, 1, n + k) {
        auto [t, a, b] = qry[i];
        if (t == 'S') {
        } else if (t == 'Q') {
            if (ans[i]) {
                cout << "yes\n";
            } else {
                cout << "no\n"; 
            }
        } else {
            cout << ans[i] << '\n';
        }
    }
    return 0;
}

Compilation message (stderr)

servers.cpp: In function 'void incre(int, int, int, int, int)':
servers.cpp:142:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  142 |     int mid = lo + hi >> 1;
      |               ~~~^~~~
servers.cpp: In function 'int qsm(int, int, int, int, int)':
servers.cpp:160:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  160 |     int mid = lo + hi >> 1;
      |               ~~~^~~~

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5