Submission #1108678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108678		MateiKing80	Inside information (BOI21_servers)	C++14	2.50 / 100	433 ms	46912 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[240005];
    vector<int> descos;
    inline int lsb(int x)
    {
        return x & -x;
    }
    void update(int pos, int val)
    {
        descos.push_back(pos);
        while(pos <= 240000)
            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 <= 240000)
                aib[i] = 0, i += lsb(i);
        descos.clear();
    }
} ds;

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

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

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[240005], spretata[240005]; // &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;

    ds.update(1, 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);
        else
            ds.update(1, -1);

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

    ds.clean();

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

signed main()
{
    //ifstream cin("sus.in");
    //ofstream cout("sus.out");
    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;
            if(u == v)
                answer[i] = -2;
            else
            {
                qry[u].push_back({'Q', i, v});
                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 <= n; i ++)
        for(auto j : qry[i])
            if(j.ch == 'Q')
                assert(answer[j.time] < 0);
    for(int i = 1; i <= q + n - 1; i ++)
        if(answer[i] != -1)
        {
            if(answer[i] >= 0)
                cout << answer[i] << '\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
*/
/*
7 5
S 1 7
S 1 5
S 1 4
C 1
S 1 2
Q 1 2
Q 2 6
C 2
S 1 6
S 1 3
C 2
*/

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:130: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]
  130 |         if(sus != realvec.size() - 1)
      |            ~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 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