Submission #1113836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113836		MateiKing80	Inside information (BOI21_servers)	C++14	100 / 100	363 ms	35812 KiB

servers

#pragma GCC optimize("Ofast")
#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;

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

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

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;
    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] += 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)
                update(muchtopapa[j], 1);
    }
    update(1, -1);
    for(auto i : qry[centr])
    {
        if(i.type == 'c')
            ans[i.time] += query(i.time);
        else
        {
            if(amdat[i.to] && (crdcr[i.to] & 2) && muchtopapa[i.to] <= i.time)
                ans[i.time] = -1;
        }
    }
    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()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    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] = -3;
        }
        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';
    }
}

Compilation message (stderr)

servers.cpp: In function 'void dfssz(int, int)':
servers.cpp:57:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |     for(auto [i, j] : vec[nod])
      |              ^
servers.cpp: In function 'int dfsCentroid(int, int)':
servers.cpp:64:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |     for(auto [i, j] : vec[nod])
      |              ^
servers.cpp: In function 'void dfs(int, std::vector<int>&)':
servers.cpp:74:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |     for(auto [i, j] : vec[nod])
      |              ^
servers.cpp: In function 'void doCentroid(int)':
servers.cpp:95:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |     for(auto [i, j] : vec[centr])
      |              ^
servers.cpp:114:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  114 |     for(auto [i, v] : subarb)
      |              ^
servers.cpp:154:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  154 |     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