Submission #521080

#	Time	Username	Problem	Language	Result	Execution time	Memory
521080		blue	Inside information (BOI21_servers)	C++17	50 / 100	404 ms	31780 KiB

servers

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using vi = vector<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);
    }
}



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;

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




    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: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5