oj.uz

Submission #401557

# Submission time Handle Problem Language Result Execution time Memory
401557 2021-05-10T13:28:24 Z johutha Inside information (BOI21_servers) C++17
30 / 100
 513 ms 32964 KB 
#include <iostream>
#include <vector>
#include <algorithm>

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);
        }

        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
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 63 ms 2808 KB Output is correct
2 Incorrect 95 ms 4788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 63 ms 2808 KB Output is correct
2 Incorrect 95 ms 4788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2852 KB Output is correct
2 Correct 296 ms 22916 KB Output is correct
3 Correct 294 ms 22940 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2852 KB Output is correct
2 Correct 296 ms 22916 KB Output is correct
3 Correct 294 ms 22940 KB Output is correct
4 Incorrect 63 ms 3736 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 2788 KB Output is correct
2 Correct 389 ms 32944 KB Output is correct
3 Correct 384 ms 32964 KB Output is correct
4 Correct 433 ms 32868 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 2788 KB Output is correct
2 Correct 389 ms 32944 KB Output is correct
3 Correct 384 ms 32964 KB Output is correct
4 Correct 433 ms 32868 KB Output is correct
5 Incorrect 62 ms 3612 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2796 KB Output is correct
2 Correct 395 ms 22704 KB Output is correct
3 Correct 334 ms 22212 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2796 KB Output is correct
2 Correct 395 ms 22704 KB Output is correct
3 Correct 334 ms 22212 KB Output is correct
4 Incorrect 63 ms 3780 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2852 KB Output is correct
2 Correct 401 ms 32568 KB Output is correct
3 Correct 396 ms 32580 KB Output is correct
4 Correct 439 ms 32728 KB Output is correct
5 Correct 64 ms 3688 KB Output is correct
6 Correct 388 ms 22716 KB Output is correct
7 Correct 329 ms 22140 KB Output is correct
8 Correct 366 ms 23152 KB Output is correct
9 Correct 361 ms 22988 KB Output is correct
10 Correct 513 ms 27560 KB Output is correct
11 Correct 499 ms 26204 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2852 KB Output is correct
2 Correct 401 ms 32568 KB Output is correct
3 Correct 396 ms 32580 KB Output is correct
4 Correct 439 ms 32728 KB Output is correct
5 Correct 64 ms 3688 KB Output is correct
6 Correct 388 ms 22716 KB Output is correct
7 Correct 329 ms 22140 KB Output is correct
8 Correct 366 ms 23152 KB Output is correct
9 Correct 361 ms 22988 KB Output is correct
10 Correct 513 ms 27560 KB Output is correct
11 Correct 499 ms 26204 KB Output is correct
12 Incorrect 64 ms 3608 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 2856 KB Output is correct
2 Incorrect 91 ms 4836 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 2856 KB Output is correct
2 Incorrect 91 ms 4836 KB Output isn't correct
3 Halted 0 ms 0 KB -