Submission #521099

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
521099	2022-01-31T18:07:53 Z	blue	Inside information (BOI21_servers)	C++17	52.5 / 100	3500 ms	32868 KB

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+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];
    }

    // 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

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	16936 KB	Output is correct
2	Correct	83 ms	17172 KB	Output is correct
3	Correct	85 ms	17236 KB	Output is correct
4	Correct	118 ms	17304 KB	Output is correct
5	Correct	95 ms	17508 KB	Output is correct
6	Correct	92 ms	17304 KB	Output is correct

Subtask #2
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	16936 KB	Output is correct
2	Correct	83 ms	17172 KB	Output is correct
3	Correct	85 ms	17236 KB	Output is correct
4	Correct	118 ms	17304 KB	Output is correct
5	Correct	95 ms	17508 KB	Output is correct
6	Correct	92 ms	17304 KB	Output is correct
7	Correct	29 ms	17016 KB	Output is correct
8	Correct	90 ms	16756 KB	Output is correct
9	Correct	84 ms	16984 KB	Output is correct
10	Correct	96 ms	16604 KB	Output is correct
11	Correct	100 ms	17004 KB	Output is correct
12	Correct	85 ms	17064 KB	Output is correct

Subtask #3
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	16892 KB	Output is correct
2	Correct	2798 ms	25412 KB	Output is correct
3	Correct	2837 ms	25564 KB	Output is correct

Subtask #4
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	16892 KB	Output is correct
2	Correct	2798 ms	25412 KB	Output is correct
3	Correct	2837 ms	25564 KB	Output is correct
4	Correct	29 ms	16956 KB	Output is correct
5	Correct	2947 ms	25532 KB	Output is correct
6	Correct	2812 ms	25728 KB	Output is correct
7	Correct	3045 ms	26216 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	16868 KB	Output is correct
2	Correct	3168 ms	31580 KB	Output is correct
3	Correct	3002 ms	31604 KB	Output is correct
4	Correct	3005 ms	31152 KB	Output is correct

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	16868 KB	Output is correct
2	Correct	3168 ms	31580 KB	Output is correct
3	Correct	3002 ms	31604 KB	Output is correct
4	Correct	3005 ms	31152 KB	Output is correct
5	Correct	29 ms	16916 KB	Output is correct
6	Correct	3052 ms	31820 KB	Output is correct
7	Correct	3124 ms	32864 KB	Output is correct
8	Correct	3116 ms	31432 KB	Output is correct
9	Correct	3270 ms	31728 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	16944 KB	Output is correct
2	Correct	3153 ms	25624 KB	Output is correct
3	Correct	3149 ms	25068 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	16944 KB	Output is correct
2	Correct	3153 ms	25624 KB	Output is correct
3	Correct	3149 ms	25068 KB	Output is correct
4	Correct	30 ms	16876 KB	Output is correct
5	Correct	2914 ms	26256 KB	Output is correct
6	Correct	3177 ms	25076 KB	Output is correct

Subtask #9
12.5 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	16884 KB	Output is correct
2	Correct	3044 ms	31652 KB	Output is correct
3	Correct	3038 ms	31568 KB	Output is correct
4	Correct	3314 ms	31136 KB	Output is correct
5	Correct	28 ms	16884 KB	Output is correct
6	Correct	3208 ms	25556 KB	Output is correct
7	Correct	3103 ms	25076 KB	Output is correct
8	Correct	2978 ms	25784 KB	Output is correct
9	Correct	3167 ms	25344 KB	Output is correct
10	Correct	3081 ms	29028 KB	Output is correct
11	Correct	3216 ms	27376 KB	Output is correct

Subtask #10
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	16884 KB	Output is correct
2	Correct	3044 ms	31652 KB	Output is correct
3	Correct	3038 ms	31568 KB	Output is correct
4	Correct	3314 ms	31136 KB	Output is correct
5	Correct	28 ms	16884 KB	Output is correct
6	Correct	3208 ms	25556 KB	Output is correct
7	Correct	3103 ms	25076 KB	Output is correct
8	Correct	2978 ms	25784 KB	Output is correct
9	Correct	3167 ms	25344 KB	Output is correct
10	Correct	3081 ms	29028 KB	Output is correct
11	Correct	3216 ms	27376 KB	Output is correct
12	Correct	28 ms	16952 KB	Output is correct
13	Correct	3202 ms	31900 KB	Output is correct
14	Correct	2833 ms	32868 KB	Output is correct
15	Correct	3258 ms	31480 KB	Output is correct
16	Correct	3174 ms	31364 KB	Output is correct
17	Correct	38 ms	16948 KB	Output is correct
18	Correct	3089 ms	26216 KB	Output is correct
19	Correct	3302 ms	25076 KB	Output is correct
20	Execution timed out	3509 ms	26064 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

Subtask #11
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	16852 KB	Output is correct
2	Correct	93 ms	17172 KB	Output is correct
3	Correct	102 ms	17156 KB	Output is correct
4	Correct	110 ms	17252 KB	Output is correct
5	Correct	142 ms	17540 KB	Output is correct
6	Correct	101 ms	17332 KB	Output is correct
7	Correct	40 ms	16932 KB	Output is correct
8	Correct	3082 ms	25444 KB	Output is correct
9	Correct	3141 ms	25444 KB	Output is correct
10	Correct	57 ms	16888 KB	Output is correct
11	Correct	3258 ms	31108 KB	Output is correct
12	Execution timed out	3537 ms	30688 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-

Subtask #12
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	16852 KB	Output is correct
2	Correct	93 ms	17172 KB	Output is correct
3	Correct	102 ms	17156 KB	Output is correct
4	Correct	110 ms	17252 KB	Output is correct
5	Correct	142 ms	17540 KB	Output is correct
6	Correct	101 ms	17332 KB	Output is correct
7	Correct	40 ms	16932 KB	Output is correct
8	Correct	3082 ms	25444 KB	Output is correct
9	Correct	3141 ms	25444 KB	Output is correct
10	Correct	57 ms	16888 KB	Output is correct
11	Correct	3258 ms	31108 KB	Output is correct
12	Execution timed out	3537 ms	30688 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-

Submission #521099

Compilation message