Submission #521103

#	Time	Username	Problem	Language	Result	Execution time	Memory
521103		blue	Inside information (BOI21_servers)	C++17	100 / 100	597 ms	33492 KiB

servers

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
using vi = vector<int>;
using pii = pair<int, int>;
#define sz(x) int(x.size())
 
const int mx = 120'000;
 
 
 
 
struct edge
{
    int v;
    int t;
};
 
vector<edge> S[1+mx];
 
 
 
 
 
struct query
{
    int a;
    int t;
};
 
vector<query> Q[1+mx]; //stored by d
 
 
 
 
 
vector<int> C[1+mx]; //stored by d
 
 
 
int N, K;
 
vi res(2*mx + 5);
 
 
 
 
 
 
 
 
 
 
 
 
vi banned(1+mx, 0);
 
vi st_count(1+mx, 0);
 
vi lst;
 
 
 
 
void dfs(int u, int p)
{
    lst.push_back(u);
 
    st_count[u] = 1;
    for(auto e: S[u])
    {
        int v = e.v;
        if(v == p) continue;
 
        if(banned[v]) continue;
 
        dfs(v, u);
        st_count[u] += st_count[v];
    }
}
 
 
vi out_good(1+mx); //going out from centroid
vi in_good(1+mx); //coming in to centroid
vi root_time(1+mx);
vi par_time(1+mx);
 
 
vi st_index(1+mx);
 
vi exists(1+mx, 0);
 
 
 
void dfs2(int u, int p)
{
    for(auto e: S[u])
    {
        int v = e.v;
        int t = e.t;
 
        if(v == p) continue;
 
        if(banned[v]) continue;
 
        root_time[v] = root_time[u];
        par_time[v] = t;
 
        out_good[v] = out_good[u] && (par_time[v] > par_time[u]);
        in_good[v] = in_good[u] && (par_time[v] < par_time[u]);
 
        st_index[v] = st_index[u];
 
        dfs2(v, u);
    }
}
 
 
vector<pii> obj_list;
 
vi BIT(1+2*mx, 0);
 
 
void solve(int src)
{
    lst.clear();
 
    dfs(src, src);
 
    int cent = -1;
 
 
    for(int u: lst)
    {
        exists[u] = 1;
 
        if(2 * st_count[u] < st_count[src]) continue;
 
        if(cent == -1) cent = u;
        else if(st_count[u] < st_count[cent]) cent = u;
    }
 
 
    // cerr << "\n\n\n\n";
    // for(int l: lst) cerr << l << ' ';
    // cerr << ": centroid = " << cent << '\n';
 
    // for(int l: lst) cerr << l << " : " << out_good[l] << ' ' << in_good[l] << ' ' << root_time[l] << ' ' << par_time[l] << '\n';
 
 
    int stid = 0;
    st_index[cent] = 0;
 
    in_good[cent] = 1;
    out_good[cent] = 1;
 
    for(auto e: S[cent])
    {
        int v = e.v;
        int t = e.t;
 
        if(banned[v]) continue;
 
        st_index[v] = ++stid;
        in_good[v] = out_good[v] = 1;
        root_time[v] = par_time[v] = t;
 
        dfs2(v, cent);
    }
 
 
 
    for(int d: lst)
    {
        for(query qr: Q[d])
        {
            int a = qr.a;
            int t = qr.t;
 
            if(!exists[a]) continue;
 
            if(d == cent)
            {
                if(a == cent)
                    res[t] = 1;
                else 
                    res[t] |= (out_good[a] && par_time[a] < t);
            }
            else
            {
                if(a == cent)
                    res[t] |= (in_good[d] && root_time[d] < t);
                else
                    res[t] |= (in_good[d] && out_good[a] && root_time[d] < root_time[a] && par_time[a] < t);
            }
        }
    }
 
 
 
    vector<pii> queries, updates;
 
    root_time[cent] = 0;
 
    for(int d: lst)
    {
        if(in_good[d] == 0) continue;
 
        for(int t: C[d])
        {
            if(root_time[d] > t) continue;
 
            queries.push_back({root_time[d], t});
        }
    }
 
    for(int a: lst)
    {
        if(out_good[a] == 0) continue;
 
        if(a == cent) continue;
 
        updates.push_back({root_time[a], par_time[a]});
    }
 
    sort(queries.begin(), queries.end(), [] (pii u, pii v)
    {
        return u.first > v.first;
    });
    sort(updates.begin(), updates.end(), [] (pii u, pii v)
    {
        return u.first > v.first;
    });
 
    int ui = -1;
 
    // BIT = vi(N+K, 0);
 
    for(pii z: queries)
    {
        while(ui+1 < sz(updates) && updates[ui+1].first > z.first)
        {
            ui++;
            for(int q = updates[ui].second; q <= N+K-1; q += q&-q)
                BIT[q]++;
        }
 
        res[z.second]++;
        for(int q = z.second-1; q >= 1; q -= q&-q)
            res[z.second] += BIT[q];
    }

    while(ui >= 0)
    {
        for(int q = updates[ui].second; q <= N+K-1; q += q&-q)
            BIT[q]--;
        ui--;
    }
 
    // vi BIT(N+K, 0);
 
    // for(pii z: obj)
    // {
    //     if(z.second > 0) //count query
    //     {
    //         int t = z.second;
    //         res[t]++; //centroid
 
    //         for(int q = t-1; q >= 1; q -= q&-q)
    //             res[t] += BIT[q];
    //     }
    //     else //node
    //     {
    //         int t = -z.second;
 
    //         for(int q = t; q <= N+K-1; q += q&-q)
    //             BIT[q]++;
    //     }
    // }
 
 
 
 
 
 
 
 
 
    for(int u: lst) exists[u] = 0;
 
    banned[cent] = 1;
 
    for(auto e: S[cent])
    {
        if(banned[e.v]) continue;
        solve(e.v);
    }
 
 
    banned[cent] = 0;
 
    
}
 
 
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> N >> K;
 
    char c[N+K];
 
    for(int q = 1; q <= N+K-1; q++)
    {
        cin >> c[q];
        if(c[q] == 'S')
        {
            int a, b;
            cin >> a >> b;
            S[a].push_back({b, q});
            S[b].push_back({a, q});
        }
        else if(c[q] == 'Q')
        {
            int a, d;
            cin >> a >> d;
            Q[d].push_back({a, q});
        }
        else
        {
            int d;
            cin >> d;
 
            C[d].push_back(q);
        }
    }
 
 
 
 
    solve(1);
 
 
 
 
    for(int q = 1; q <= N+K-1; q++)
    {
        if(c[q] == 'S') continue;
        else if(c[q] == 'Q')
        {
            if(res[q] == 1) cout << "yes\n";
            else cout << "no\n";
        }
        else cout << res[q] << '\n';
    }
}

• 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