oj.uz

Submission #521100

# Submission time Handle Problem Language Result Execution time Memory
521100 2022-01-31T18:09:42 Z blue Inside information (BOI21_servers) C++17
50 / 100
 454 ms 29640 KB 
#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];
    }

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

    updates.clear();
    queries.clear();









    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 26 ms 15944 KB Output is correct
2 Correct 43 ms 16260 KB Output is correct
3 Correct 38 ms 16052 KB Output is correct
4 Correct 45 ms 16276 KB Output is correct
5 Correct 41 ms 16452 KB Output is correct
6 Correct 36 ms 16268 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 15944 KB Output is correct
2 Correct 43 ms 16260 KB Output is correct
3 Correct 38 ms 16052 KB Output is correct
4 Correct 45 ms 16276 KB Output is correct
5 Correct 41 ms 16452 KB Output is correct
6 Correct 36 ms 16268 KB Output is correct
7 Correct 30 ms 15944 KB Output is correct
8 Incorrect 44 ms 15784 KB Extra information in the output file
9 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16016 KB Output is correct
2 Correct 154 ms 23540 KB Output is correct
3 Correct 124 ms 23516 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16016 KB Output is correct
2 Correct 154 ms 23540 KB Output is correct
3 Correct 124 ms 23516 KB Output is correct
4 Correct 31 ms 16068 KB Output is correct
5 Incorrect 142 ms 23556 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 15976 KB Output is correct
2 Correct 355 ms 28848 KB Output is correct
3 Correct 343 ms 28856 KB Output is correct
4 Correct 214 ms 29080 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 15976 KB Output is correct
2 Correct 355 ms 28848 KB Output is correct
3 Correct 343 ms 28856 KB Output is correct
4 Correct 214 ms 29080 KB Output is correct
5 Correct 32 ms 15940 KB Output is correct
6 Incorrect 419 ms 29236 KB Extra information in the output file
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 15948 KB Output is correct
2 Correct 216 ms 23088 KB Output is correct
3 Correct 354 ms 22384 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 15948 KB Output is correct
2 Correct 216 ms 23088 KB Output is correct
3 Correct 354 ms 22384 KB Output is correct
4 Correct 30 ms 15940 KB Output is correct
5 Incorrect 259 ms 24000 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16004 KB Output is correct
2 Correct 393 ms 28848 KB Output is correct
3 Correct 373 ms 28920 KB Output is correct
4 Correct 212 ms 29136 KB Output is correct
5 Correct 27 ms 16012 KB Output is correct
6 Correct 224 ms 23056 KB Output is correct
7 Correct 316 ms 22312 KB Output is correct
8 Correct 278 ms 23108 KB Output is correct
9 Correct 338 ms 22996 KB Output is correct
10 Correct 452 ms 26232 KB Output is correct
11 Correct 352 ms 25020 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16004 KB Output is correct
2 Correct 393 ms 28848 KB Output is correct
3 Correct 373 ms 28920 KB Output is correct
4 Correct 212 ms 29136 KB Output is correct
5 Correct 27 ms 16012 KB Output is correct
6 Correct 224 ms 23056 KB Output is correct
7 Correct 316 ms 22312 KB Output is correct
8 Correct 278 ms 23108 KB Output is correct
9 Correct 338 ms 22996 KB Output is correct
10 Correct 452 ms 26232 KB Output is correct
11 Correct 352 ms 25020 KB Output is correct
12 Correct 45 ms 15944 KB Output is correct
13 Incorrect 370 ms 29232 KB Extra information in the output file
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 15940 KB Output is correct
2 Correct 43 ms 16168 KB Output is correct
3 Correct 34 ms 16072 KB Output is correct
4 Correct 42 ms 16248 KB Output is correct
5 Correct 44 ms 16452 KB Output is correct
6 Correct 35 ms 16324 KB Output is correct
7 Correct 36 ms 16040 KB Output is correct
8 Correct 152 ms 23540 KB Output is correct
9 Correct 132 ms 23532 KB Output is correct
10 Correct 58 ms 15980 KB Output is correct
11 Correct 330 ms 29320 KB Output is correct
12 Correct 415 ms 29368 KB Output is correct
13 Correct 210 ms 29640 KB Output is correct
14 Correct 34 ms 16544 KB Output is correct
15 Correct 219 ms 23536 KB Output is correct
16 Correct 320 ms 22852 KB Output is correct
17 Correct 283 ms 23620 KB Output is correct
18 Correct 454 ms 23520 KB Output is correct
19 Correct 435 ms 26680 KB Output is correct
20 Correct 383 ms 25648 KB Output is correct
21 Correct 204 ms 23900 KB Output is correct
22 Correct 173 ms 23616 KB Output is correct
23 Correct 263 ms 23104 KB Output is correct
24 Correct 294 ms 23084 KB Output is correct
25 Correct 386 ms 26012 KB Output is correct
26 Correct 292 ms 21872 KB Output is correct
27 Correct 291 ms 21804 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 15940 KB Output is correct
2 Correct 43 ms 16168 KB Output is correct
3 Correct 34 ms 16072 KB Output is correct
4 Correct 42 ms 16248 KB Output is correct
5 Correct 44 ms 16452 KB Output is correct
6 Correct 35 ms 16324 KB Output is correct
7 Correct 36 ms 16040 KB Output is correct
8 Correct 152 ms 23540 KB Output is correct
9 Correct 132 ms 23532 KB Output is correct
10 Correct 58 ms 15980 KB Output is correct
11 Correct 330 ms 29320 KB Output is correct
12 Correct 415 ms 29368 KB Output is correct
13 Correct 210 ms 29640 KB Output is correct
14 Correct 34 ms 16544 KB Output is correct
15 Correct 219 ms 23536 KB Output is correct
16 Correct 320 ms 22852 KB Output is correct
17 Correct 283 ms 23620 KB Output is correct
18 Correct 454 ms 23520 KB Output is correct
19 Correct 435 ms 26680 KB Output is correct
20 Correct 383 ms 25648 KB Output is correct
21 Correct 204 ms 23900 KB Output is correct
22 Correct 173 ms 23616 KB Output is correct
23 Correct 263 ms 23104 KB Output is correct
24 Correct 294 ms 23084 KB Output is correct
25 Correct 386 ms 26012 KB Output is correct
26 Correct 292 ms 21872 KB Output is correct
27 Correct 291 ms 21804 KB Output is correct
28 Correct 30 ms 16436 KB Output is correct
29 Incorrect 47 ms 16404 KB Extra information in the output file
30 Halted 0 ms 0 KB -