oj.uz

Submission #401559

# Submission time Handle Problem Language Result Execution time Memory
401559 2021-05-10T13:29:39 Z johutha Inside information (BOI21_servers) C++17
30 / 100
 552 ms 37712 KB 
#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);
        }

        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 64 ms 5060 KB Output is correct
2 Incorrect 97 ms 5656 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 64 ms 5060 KB Output is correct
2 Incorrect 97 ms 5656 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 64 ms 5060 KB Output is correct
2 Correct 304 ms 25716 KB Output is correct
3 Correct 313 ms 25492 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 64 ms 5060 KB Output is correct
2 Correct 304 ms 25716 KB Output is correct
3 Correct 313 ms 25492 KB Output is correct
4 Incorrect 64 ms 4932 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 5096 KB Output is correct
2 Correct 424 ms 37648 KB Output is correct
3 Correct 440 ms 37656 KB Output is correct
4 Correct 464 ms 37572 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 5096 KB Output is correct
2 Correct 424 ms 37648 KB Output is correct
3 Correct 440 ms 37656 KB Output is correct
4 Correct 464 ms 37572 KB Output is correct
5 Incorrect 63 ms 4876 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 64 ms 5084 KB Output is correct
2 Correct 416 ms 25824 KB Output is correct
3 Correct 343 ms 24880 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 5084 KB Output is correct
2 Correct 416 ms 25824 KB Output is correct
3 Correct 343 ms 24880 KB Output is correct
4 Incorrect 66 ms 4848 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 65 ms 5020 KB Output is correct
2 Correct 409 ms 37652 KB Output is correct
3 Correct 410 ms 37712 KB Output is correct
4 Correct 455 ms 37652 KB Output is correct
5 Correct 64 ms 5144 KB Output is correct
6 Correct 416 ms 25940 KB Output is correct
7 Correct 357 ms 24960 KB Output is correct
8 Correct 379 ms 25668 KB Output is correct
9 Correct 391 ms 26052 KB Output is correct
10 Correct 552 ms 30916 KB Output is correct
11 Correct 534 ms 29660 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 5020 KB Output is correct
2 Correct 409 ms 37652 KB Output is correct
3 Correct 410 ms 37712 KB Output is correct
4 Correct 455 ms 37652 KB Output is correct
5 Correct 64 ms 5144 KB Output is correct
6 Correct 416 ms 25940 KB Output is correct
7 Correct 357 ms 24960 KB Output is correct
8 Correct 379 ms 25668 KB Output is correct
9 Correct 391 ms 26052 KB Output is correct
10 Correct 552 ms 30916 KB Output is correct
11 Correct 534 ms 29660 KB Output is correct
12 Incorrect 64 ms 4912 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 66 ms 5228 KB Output is correct
2 Incorrect 92 ms 5704 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 66 ms 5228 KB Output is correct
2 Incorrect 92 ms 5704 KB Output isn't correct
3 Halted 0 ms 0 KB -