Submission #1108637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108637		MateiKing80	Inside information (BOI21_servers)	C++14	0 / 100	49 ms	11240 KiB

servers

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()

using pii = pair<int, int>;
#define fr first
#define sc second

struct Fenwick
{
    int aib[120005];
    vector<int> descos;
    inline int lsb(int x)
    {
        return x & -x;
    }
    void update(int pos, int val)
    {
        descos.push_back(pos);
        while(pos <= 120000)
            aib[pos] += val, pos += lsb(pos);
    }
    int query(int pos)
    {
        int ans = 0;
        while(pos)
            ans += aib[pos], pos -= lsb(pos);
        return ans;
    }
    void clean()
    {
        for(auto i : descos)
            while(i <= 120000 && aib[i] != 0)
                aib[i] = 0, i += lsb(i);
        descos.clear();
    }
} ds;

struct Intrebare
{
    char ch;
    int time, val; //daca e cazu
};

vector<Intrebare> qry[120005];
vector<pii> vec[120005];
bool viz[120005];
int answer[120005], sz[120005];

void dfsz(int nod, int papa)
{
    int nsz = 1;
    for(auto i : vec[nod])
        if(i.fr != papa && !viz[i.fr])
            dfsz(i.fr, nod), nsz += sz[i.fr];
    sz[nod] = nsz;
}

int find_centroid(int nod, int szmx, int papa)
{
    for(auto i : vec[nod])
        if(!viz[i.fr] && i.fr != papa && sz[i.fr] >= (szmx + 1) / 2)
            return find_centroid(i.fr, szmx, nod);
    return nod;
}

int crdcr[120005], spretata[120005]; // &1 daca crescator, &2 daca descrescator

void dfs(int nod, int papa, vector<int> &baga, int primu = 0)
{
    if(!primu)
    {
        //cout << nod << " " << papa << " " << spretata[nod] << " " << spretata[papa] << '\n';
        crdcr[nod] = 0;
        if(spretata[nod] <= spretata[papa])
            crdcr[nod] += (1 & crdcr[papa]);
        if(spretata[nod] >= spretata[papa])
            crdcr[nod] += (2 & crdcr[papa]);
    }
    baga.push_back(nod);
    for(auto i : vec[nod])
        if(!viz[i.fr] && i.fr != papa)
            spretata[i.fr] = i.sc, dfs(i.fr, nod, baga, 0);
}

void dfs_centroid(int nod)
{
    dfsz(nod, 0);
    int centr = find_centroid(nod, sz[nod], 0);

    crdcr[centr] = 3;

    vector<pair<int, vector<int>>> realvec;

    for(auto i : vec[centr])
        if(!viz[i.fr])
        {
            realvec.push_back({i.fr, vector<int>(0)});
            spretata[i.fr] = i.sc;
            crdcr[i.fr] = 3;
            dfs(i.fr, centr, realvec.back().sc, 1);
        }

    sort(all(realvec), [&](pair<int, vector<int>> a, pair<int, vector<int>> b)
    {
        return spretata[a.fr] < spretata[b.fr];
    });

    //cout << centr << ": \n";

    map<int, int> papsubctr, pospap;
    for(auto i : realvec)
        for(auto j : i.sc)
        {
            papsubctr[j] = i.fr;
     //       cout << j << " papa: " << i.fr << " spretata: " << spretata[j] << " crdcr: "  << crdcr[j] << '\n';
        }
   // cout << '\n';
    for(int i = 0; i < realvec.size(); i ++)
        pospap[realvec[i].fr] = i + 1;

    for(int sus = realvec.size() - 1; sus >= 0; sus --)
    {
        auto i = realvec[sus];
        ds.update(spretata[i.fr], 1);
        if(sus != realvec.size() - 1)
            ds.update(spretata[realvec[sus + 1].fr], -1);

        for(auto j : i.sc)
            for(auto k : qry[j])
            {
                if(k.ch == 'Q')
                {
                    if(pospap[papsubctr[j]] < pospap[papsubctr[k.val]] && (crdcr[j] & 1) && (crdcr[k.val] & 2) && spretata[k.val] <= k.time)
                        answer[k.time] = -2;
                   // cout << centr << " " << k.ch << " " << j << " " << k.val << " " << k.time << " " << answer[k.time] << '\n';
                }
                else if(crdcr[j] & 1)
                    answer[k.time] += ds.query(k.time);
            }
        for(auto j : i.sc)
            if(crdcr[j] & 2)
                ds.update(spretata[j], 1);
    }

    //ar fi cazu sa verificam si pentru centroid queryurile

    for(auto k : qry[centr])
    {
        if(k.ch == 'Q')
        {
            if(pospap[papsubctr[k.val]] && (crdcr[k.val] & 2) && spretata[k.val] <= k.time)
                answer[k.time] = -2;
        }
        else
            answer[k.time] += ds.query(k.time) + 1; //ca se poate lua si pe el
    }

    ds.clean();

    viz[centr] = true;
    for(auto i : vec[centr])
        if(!viz[i.fr])
            dfs_centroid(i.fr);
}

signed main()
{

    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= q + n - 1; i ++)
    {
        char ch;
        cin >> ch;
        if(ch == 'S')
        {
            int u, v;
            cin >> u >> v;
            vec[u].push_back({v, i});
            vec[v].push_back({u, i});
            answer[i] = -1;
        }
        if(ch == 'Q')
        {
            int u, v;
            cin >> u >> v;
            qry[v].push_back({'Q', i, u});
            answer[i] = -3;
        }
        if(ch == 'C')
        {
            int u;
            cin >> u;
            qry[u].push_back({'C', i, 0});
        }
    }
    dfs_centroid(1);
    for(int i = 1; i <= q + n - 1; i ++)
        if(answer[i] != -1)
        {
            if(answer[i] >= 0)
                cout << answer[i] + 1 << '\n';
            else if(answer[i] == -2)
                cout << "yes\n";
            else
                cout << "no\n";
        }
}
/*
6 9
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
C 1
C 2
C 3
C 4
C 5
C 6
*/

Compilation message (stderr)

servers.cpp: In function 'void dfs_centroid(int)':
servers.cpp:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for(int i = 0; i < realvec.size(); i ++)
      |                    ~~^~~~~~~~~~~~~~~~
servers.cpp:128:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |         if(sus != realvec.size() - 1)
      |            ~~~~^~~~~~~~~~~~~~~~~~~~~

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