제출 #541818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
541818		Stickfish	Inside information (BOI21_servers)	C++17	100 / 100	624 ms	47880 KiB

servers

#include <iostream>
#include <algorithm>
#include <bitset>
#include <vector>
using namespace std;

struct way {
    int mnt = -177013;
    int mxt = -177013;
    bool incr = true;
    bool dcr = true;
    
    way() {}

    way(int t): mnt(t), mxt(t) {}

    way reverse() {
        way ans;
        ans.mnt = mnt;
        ans.mxt = mxt;
        ans.dcr = incr;
        ans.incr = dcr;
        return ans;
    }

    way operator+(way w) {
        if (mnt == -177013)
            return w;
        if (w.mnt == -177013)
            return *this;
        way ans;
        ans.mnt = min(mnt, w.mnt);
        ans.mxt = max(mxt, w.mxt);
        ans.incr = (incr && w.incr && mxt <= w.mnt);
        ans.dcr = (dcr && w.dcr && mnt >= w.mxt);
        return ans;
    }

    friend ostream& operator<<(ostream& o, way w) {
        o << "[" << w.incr << ' ' << w.dcr << ' ' << w.mnt << ' ' << w.mxt << "]";
        return o;
    }
};

const int MAXN = 120008;
vector<pair<int, int>> edg[MAXN];
int depth[MAXN];
pair<int, int> rt[MAXN];
pair<int, way> crt[MAXN];

void dfs(int v) {
    auto [rtv, tmv] = rt[v];
    int par = crt[rtv].first;
    int parpar = crt[par].first;
    if (depth[rtv] - depth[par] == depth[par] - depth[parpar]) {
        crt[v] = {parpar, way(tmv) + crt[rtv].second + crt[par].second};
    } else {
        crt[v] = {rtv, way(tmv)};
    }
    for (auto [u, t] : edg[v]) {
        if (u == rtv)
            continue;
        rt[u] = {v, t};
        depth[u] = depth[v] + 1;
        dfs(u);
    }
}

pair<int, way> lift(int v, int d) {
    way ans = rt[v].second;
    while (d) {
        if (depth[v] - depth[crt[v].first] <= d) {
            ans = ans + crt[v].second;
            d -= depth[v] - depth[crt[v].first];
            v = crt[v].first;
        } else {
            ans = ans + rt[v].second;
            --d;
            v = rt[v].first;
        }
    }
    return {v, ans};
}

pair<int, pair<way, way>> lca(int v, int u) {
    way ansv = -177013;
    way ansu = -177013;
    if (depth[v] > depth[u]) {
        pair<int, way> vlift = lift(v, depth[v] - depth[u]);
        ansv = ansv + vlift.second;
        v = vlift.first;
    } else if (depth[v] < depth[u]) {
        pair<int, way> ulift = lift(u, depth[u] - depth[v]);
        ansu = ansu + ulift.second;
        u = ulift.first;
    }
    while (u != v) {
        if (crt[v].first != crt[u].first) {
            ansv = ansv + crt[v].second;
            ansu = ansu + crt[u].second;
            v = crt[v].first;
            u = crt[u].first;
        } else {
            ansv = ansv + rt[v].second;
            ansu = ansu + rt[u].second;
            v = rt[v].first;
            u = rt[u].first;
        }
    }
    return {v, {ansv, ansu}};
}

way get_way(int v, int u) {
    auto ans = lca(v, u);
    return ans.second.first + ans.second.second.reverse();
}

int centrt[MAXN];
int sz[MAXN];
bitset<MAXN> used;
vector<pair<int, int>> ways[MAXN];

void sz_dfs(int v, int rtv) {
    sz[v] = 1;
    for (auto [u, t] : edg[v]) {
        if (u == rtv || used[u])
            continue;
        sz_dfs(u, v);
        sz[v] += sz[u];
    }
}

int centr_dfs(int v, int sz0) {
    for (auto [u, t] : edg[v]) {
        if (sz[u] > sz[v] || used[u])
            continue;
        if (sz[u] * 2 > sz0)
            return centr_dfs(u, sz0);
    }
    return v;
}

void centrinit_dfs(int v, int rtv, int grt, way w, vector<pair<int, int>>& remilia) {
    if (w.incr)
        remilia.push_back({w.mnt, w.mxt});
    centrt[v] = grt;
    for (auto [u, t] : edg[v]) {
        if (used[u] || u == rtv)
            continue;
        centrinit_dfs(u, v, grt, w + t, remilia);
    }
}

void centr_decompose(int v) {
    sz_dfs(v, -1);
    v = centr_dfs(v, sz[v]);
    //cout << v << endl;
    used[v] = 1;
    for (auto [u, t] : edg[v]) {
        if (used[u])
            continue;
        centrinit_dfs(u, v, v, t, ways[v]);
        centr_decompose(u);
    }
}

vector<pair<pair<int, int>, int>> subqr[MAXN];

int ans_qr2(int v, int qrnum, int mxt) {
    int ans = 0;
    int u = v;
    while (u > -1) {
        //cout << "(" << u << ' ' << v << ") ";
        way w = get_way(v, u);
        if (w.incr && w.mxt <= mxt) {
            //cout << u << ' ' << v << ": ";
            //cout << "{" << w.mnt << ' ' << w.mxt << "} ";
            ++ans;
            subqr[u].push_back({{w.mxt + 1, mxt}, qrnum});
            //for (auto [mnt0, mxt0] : ways[u]) {
                //if (mnt0 > w.mxt && mxt0 <= mxt) {
                    //cout << "(" << mnt0 << ' ' << mxt0 << ") ";
                    //++ans;
                //} else {
                    //cout << "[" << mnt0 << ' ' << mxt0 << "] ";
                //}
            //}
            //cout << endl;
        }
        u = centrt[u];
    }
    return ans;
}

struct fenwick {
    void resize(int n) {
        t.resize(n);
    }

    void add(int i, int x) {
        while (i < t.size()) {
            t[i] += x;
            i |= i + 1;
        }
    }

    int get(int i) {
        int ans = 0;
        while (i >= 0) {
            ans += t[i];
            i &= i + 1;
            --i;
        }
        return ans;
    }
 private:
     vector<int> t;
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<pair<int, pair<int, int>>> qrs;
    int timer = -1;
    for (int i = 0; i < n + k - 1; ++i) {
        char ch;
        cin >> ch;
        if (ch == 'S') {
            int u, v;
            cin >> u >> v;
            --u, --v;
            edg[u].push_back({v, ++timer});
            edg[v].push_back({u, timer});
        } else if (ch == 'Q') {
            int u, v;
            cin >> u >> v;
            --u, --v;
            qrs.push_back({timer, {v, u}});
        } else {
            int v;
            cin >> v;
            --v;
            qrs.push_back({timer, {v, -1}});
        }
    }
    rt[0] = {0, -177013};
    dfs(0);
    for (int i = 0; i < n; ++i)
        centrt[i] = -1;
    centr_decompose(0);
    vector<int> anss(k);
    for (int i = 0; i < k; ++i) {
        auto [t, qri] = qrs[i];
        auto [v, u] = qri;
        if (u == -1) {
            anss[i] = ans_qr2(v, i, t);
        } else {
            way w = get_way(v, u);
            if (w.incr && w.mxt <= t) {
                anss[i] = -1;
            } else {
                anss[i] = -2;
            }
        }
    }
    fenwick tr;
    tr.resize(n);
    for (int v = 0; v < n; ++v) {
        sort(subqr[v].rbegin(), subqr[v].rend());
        sort(ways[v].begin(), ways[v].end());
        int j = ways[v].size();
        for (auto [hey, qi] : subqr[v]) {
            auto [l, r] = hey;
            while (j > 0 && ways[v][j - 1].first >= l) {
                --j;
                tr.add(ways[v][j].second, 1);
            }
            anss[qi] += tr.get(r);
            //for (auto [l0, r0] : ways[v]) {
                //if (l <= l0 && r0 <= r) {
                    //++anss[qi];
                //}
            //}
        }
        while (j < ways[v].size()) {
            tr.add(ways[v][j].second, -1);
            ++j;
        }
    }
    for (int i = 0; i < k; ++i) {
        if (anss[i] == -1)
            cout << "yes\n";
        else if (anss[i] == -2)
            cout << "no\n";
        else
            cout << anss[i] << '\n';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

servers.cpp: In member function 'void fenwick::add(int, int)':
servers.cpp:201:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |         while (i < t.size()) {
      |                ~~^~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:288:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  288 |         while (j < ways[v].size()) {
      |                ~~^~~~~~~~~~~~~~~~

• 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