Submission #1113834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113834		MateiKing80	Inside information (BOI21_servers)	C++14	100 / 100	403 ms	38484 KiB

servers

#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()

const int N = 120000;
int n, q;

struct AIB
{
    int aib[2 * N + 5];
    vector<int> descos;
    inline int lsb(int x) {return x & -x;}
    void update(int pos, int val)
    {
        while(pos < n + q)
            aib[pos] += val,
            descos.push_back(pos),
            pos += lsb(pos);
    }
    int query(int pos)
    {
        int ans = 0;
        while(pos)
            ans += aib[pos],
            pos -= lsb(pos);
        return ans;
    }
    void sterge()
    {
        for(auto i : descos)
            aib[i] = 0;
        descos.clear();
    }
} ds;

struct Query
{
    char type;
    int to, time;
};
vector<Query> qry[N + 5];
vector<pii> vec[N + 5];
int ans[2 * N + 5], sz[N + 5], muchtopapa[N + 5];
int crdcr[N + 5], papa[N + 5], papasubc[N + 5];
bool viz[N + 5], amdat[N + 5];

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

int dfsCentroid(int nod, int szinit)
{
    for(auto [i, j] : vec[nod])
        if(!viz[i] && sz[i] < sz[nod] && 2 * sz[i] >= szinit)
            return dfsCentroid(i, szinit);
    return nod;
}

void dfs(int nod, vector<int> &x)
{
    x.push_back(nod);
    amdat[nod] = true;
    for(auto [i, j] : vec[nod])
    {
        if(viz[i] || i == papa[nod])
            continue;
        papa[i] = nod;
        papasubc[i] = papasubc[nod];
        muchtopapa[i] = j;
        crdcr[i] = 0;
        if(j < muchtopapa[nod] && (crdcr[nod] & 1))
            crdcr[i] ++;
        if(j > muchtopapa[nod] && (crdcr[nod] & 2))
            crdcr[i] += 2;
        dfs(i, x);
    }
}

//crdcr[nod] & 1 => crescator de la nod in sus
//crdcr[nod] & 2 => descrescator de la nod in sus

void doCentroid(int nod)
{
    dfssz(nod, 0);
    int centr = dfsCentroid(nod, sz[nod]);
    vector<pair<int, vector<int>>> subarb;
    for(auto [i, j] : vec[centr])
    {
        if(viz[i])
            continue;
        subarb.push_back({i, {}});
        papa[i] = centr;
        papasubc[i] = i;
        muchtopapa[i] = j;
        crdcr[i] = 3;
        dfs(i, subarb.back().sc);
    }
    muchtopapa[centr] = 0;
    sort(all(subarb), [&](pair<int, vector<int>> a, pair<int, vector<int>> b)
    {
        return muchtopapa[a.fr] > muchtopapa[b.fr];
    });
    amdat[centr] = true;
    crdcr[centr] = 3;
    ds.update(1, 1);
    for(auto [i, v] : subarb)
    {
        for(auto j : v)
            for(auto k : qry[j])
            {
                if(k.type == 'c')
                {
                    if(muchtopapa[papasubc[j]] <= k.time && (crdcr[j] & 1))
                        ans[k.time] += ds.query(k.time);
                }
                else
                {
                    if(k.to != centr && amdat[k.to] && muchtopapa[papasubc[k.to]] > muchtopapa[papasubc[j]] &&
                       muchtopapa[k.to] <= k.time && (crdcr[k.to] & 2) && (crdcr[j] & 1))
                        ans[k.time] = -1;
                    else if(k.to == centr && (crdcr[j] & 1) && muchtopapa[papasubc[j]] <= k.time)
                        ans[k.time] = -1;

                }
            }
        for(auto j : v)
            if(crdcr[j] & 2)
                ds.update(muchtopapa[j], 1);
    }
    ds.update(1, -1);
    for(auto i : qry[centr])
    {
        if(i.type == 'c')
            ans[i.time] += ds.query(i.time);
        else
        {
            if(amdat[i.to] && (crdcr[i.to] & 2) && muchtopapa[i.to] <= i.time)
                ans[i.time] = -1;
        }
    }
    ds.sterge();
    amdat[centr] = false;
    for(auto i : subarb)
        for(auto j : i.sc)
            amdat[j] = false;
    viz[centr] = true;
    for(auto [i, j] : vec[centr])
        if(!viz[i])
            doCentroid(i);
}

int main()
{
    cin >> n >> q;
    for(int i = 1; i < n + q; i ++)
    {
        char t;
        cin >> t;
        if(t == 'S')
        {
            int u, v;
            cin >> u >> v;
            vec[u].push_back({v, i});
            vec[v].push_back({u, i});
            ans[i] = -69;
        }
        if(t == 'Q')
        {
            int u, v;
            cin >> u >> v;
            qry[v].push_back({'q', u, i});
            ans[i] = -2;
        }
        if(t == 'C')
        {
            int u;
            cin >> u;
            qry[u].push_back({'c', 0, i});
        }
    }
    doCentroid(1);
    for(int i = 1; i < n + q; i ++)
    {
        if(ans[i] == -1)
            cout << "yes\n";
        else if(ans[i] == -2)
            cout << "no\n";
        else if(ans[i] >= 0)
            cout << ans[i] + 1 << '\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 dfssz(int, int)':
servers.cpp:55:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |     for(auto [i, j] : vec[nod])
      |              ^
servers.cpp: In function 'int dfsCentroid(int, int)':
servers.cpp:62:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |     for(auto [i, j] : vec[nod])
      |              ^
servers.cpp: In function 'void dfs(int, std::vector<int>&)':
servers.cpp:72:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |     for(auto [i, j] : vec[nod])
      |              ^
servers.cpp: In function 'void doCentroid(int)':
servers.cpp:96:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |     for(auto [i, j] : vec[centr])
      |              ^
servers.cpp:115:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  115 |     for(auto [i, v] : subarb)
      |              ^
servers.cpp:156:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  156 |     for(auto [i, j] : vec[centr])
      |              ^

• 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