Submission #401571

#	Time	Username	Problem	Language	Result	Execution time	Memory
401571		johutha	Inside information (BOI21_servers)	C++17	100 / 100	753 ms	41176 KiB

servers

#include <iostream>
#include <vector>
#include <algorithm>

#define int long long

using namespace std;

struct fen
{
    int n;
    vector<int> table;

    fen(int in) : n(in), table(in + 1) {}
    fen() {}

    int query(int r)
    {
        int s = 0;
        for (; r; r -= r & (-r)) s += table[r];
        return s;
    }

    void update(int k, int v)
    {
        k++;
        for (; k <= n; k += k & (-k)) table[k] += v;
    }
};

struct tree
{
    vector<vector<pair<int,int>>> adj;
    vector<int> lvl;
    vector<int> ssz;

    vector<int> qans;
    vector<int> qvs;
    vector<int> qts;
    vector<vector<int>> q1s;
    vector<vector<int>> q2s;

    int subdfs(const int& curr, const int& par, const int& l)
    {
        if (lvl[curr] <= l) return 0;

        ssz[curr] = 1;
        for (auto np : adj[curr])
        {
            if (np.first == par) continue;
            ssz[curr] += subdfs(np.first, curr, l);
        }
        return ssz[curr];
    }

    void find(const int& curr, const int& par, const int& l, const int& sz)
    {
        if (lvl[curr] <= l) return;
        for (auto np : adj[curr])
        {
            if (np.first == par) continue;
            if (lvl[np.first] > l && ssz[np.first] > sz / 2) return find(np.first, curr, l, sz);
        }
        lvl[curr] = l + 1;
        recurse(curr, l + 1);
    }

    vector<int> pis;
    fen f;

    void collect(const int& curr, const int& mw, const int& l)
    {
        if (lvl[curr] <= l) return;
        pis.push_back(mw);
        for (auto np : adj[curr])
        {
            if (np.second <= mw) continue;
            collect(np.first, np.second, l);
        }
    }

    vector<int> lproc;
    vector<int> arrw;

    void add(const int& curr, const int& mw, const int& l, const int& rt)
    {
        if (lvl[curr] <= l) return;
        int ind = lower_bound(pis.begin(), pis.end(), mw) - pis.begin();
        f.update(ind, 1);
        lproc[curr] = rt;
        arrw[curr] = mw;

        for (auto np : adj[curr])
        {
            if (np.second <= mw) continue;
            add(np.first, np.second, l, rt);
        }
    }

    void process(const int& curr, const int& mw, const int& l, const int& rt)
    {
        if (lvl[curr] <= l) return;

        for (auto i : q1s[curr])
        {
            int v = qts[i];
            if (lproc[v] == rt) qans[i] = arrw[v]; 
        }

        for (auto i : q2s[curr])
        {
            int mind = lower_bound(pis.begin(), pis.end(), qvs[i]) - pis.begin();
            qans[i] += f.query(mind);
            if (qvs[i] > arrw[rt]) qans[i]++;
        }

        for (auto np : adj[curr])
        {
            if (np.second >= mw) continue;
            process(np.first, np.second, l, rt);
        }
    }

    void recurse(const int& curr, const int& l)
    {
        sort(adj[curr].begin(), adj[curr].end(), [&](const pair<int,int>& lhs, const pair<int,int>& rhs)
        {
            return lhs.second > rhs.second;
        });

        pis.clear();
        for (auto np : adj[curr]) collect(np.first, np.second, l);
        
        sort(pis.begin(), pis.end());
        pis.erase(unique(pis.begin(), pis.end()), pis.end());

        int m = pis.size();
        f = fen(m);

        lproc[curr] = curr;

        for (auto np : adj[curr])
        {
            arrw[curr] = np.second;
            process(np.first, np.second, l, curr);
            add(np.first, np.second, l, curr);
        }

        arrw[curr] = -100;
        process(curr, -100, l - 1, curr);

        for (auto np : adj[curr])
        {
            subdfs(np.first, curr, l);
            find(np.first, curr, l, ssz[np.first]);
        }
    }

    tree(int in, int ik) : adj(in), lvl(in, in + 1), ssz(in, 0), qans(ik), qvs(ik), qts(ik, -1), q1s(in), q2s(in), lproc(in, in), arrw(in, 1e9) {}
};

signed main()
{
    int n, k;
    cin >> n >> k;

    tree t(n, k);

    int ct = 0;

    for (int i = 0; i < n + k - 1; i++)
    {
        char m;
        cin >> m;
        if (m == 'S')
        {
            int a, b;
            cin >> a >> b;
            a--; b--;
            t.adj[a].emplace_back(b, ct);
            t.adj[b].emplace_back(a, ct);
            ct++;
        }
        if (m == 'Q')
        {
            int a, tg;
            cin >> tg >> a;
            a--; tg--;
            t.q1s[a].push_back(i - ct);
            t.qts[i - ct] = tg;
            t.qvs[i - ct] = ct;
            t.qans[i - ct] = n + 100;
        }
        if (m == 'C')
        {
            int a;
            cin >> a; a--;
            t.q2s[a].push_back(i - ct);
            t.qvs[i - ct] = ct;
        }
    }

    t.subdfs(0, -1, -1);
    t.find(0, -1, -1, t.ssz[0]);

    for (int i = 0; i < k; i++)
    {
        if (t.qts[i] == -1)
        {
            cout << t.qans[i] << "\n";
        }
        else
        {
            if (t.qans[i] < t.qvs[i])
            {
                cout << "yes\n";
            }
            else
            {
                cout << "no\n";
            }
        }
    }
}

• 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