oj.uz

Submission #521101

# Submission time Handle Problem Language Result Execution time Memory
521101 2022-01-31T18:11:31 Z blue Inside information (BOI21_servers) C++17
50 / 100
 511 ms 29296 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]++;
    //     }
    // }
 
 
 
 
 
 
 
 
 
    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 15940 KB Output is correct
2 Correct 39 ms 16196 KB Output is correct
3 Correct 35 ms 16000 KB Output is correct
4 Correct 38 ms 16324 KB Output is correct
5 Correct 39 ms 16512 KB Output is correct
6 Correct 34 ms 16300 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 15940 KB Output is correct
2 Correct 39 ms 16196 KB Output is correct
3 Correct 35 ms 16000 KB Output is correct
4 Correct 38 ms 16324 KB Output is correct
5 Correct 39 ms 16512 KB Output is correct
6 Correct 34 ms 16300 KB Output is correct
7 Correct 26 ms 15956 KB Output is correct
8 Incorrect 51 ms 15812 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 27 ms 15948 KB Output is correct
2 Correct 157 ms 23552 KB Output is correct
3 Correct 123 ms 23460 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15948 KB Output is correct
2 Correct 157 ms 23552 KB Output is correct
3 Correct 123 ms 23460 KB Output is correct
4 Correct 27 ms 16068 KB Output is correct
5 Incorrect 140 ms 23656 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 27 ms 15948 KB Output is correct
2 Correct 313 ms 28860 KB Output is correct
3 Correct 323 ms 28856 KB Output is correct
4 Correct 207 ms 29140 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15948 KB Output is correct
2 Correct 313 ms 28860 KB Output is correct
3 Correct 323 ms 28856 KB Output is correct
4 Correct 207 ms 29140 KB Output is correct
5 Correct 34 ms 15932 KB Output is correct
6 Incorrect 370 ms 29224 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 25 ms 15940 KB Output is correct
2 Correct 202 ms 23104 KB Output is correct
3 Correct 342 ms 22352 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 15940 KB Output is correct
2 Correct 202 ms 23104 KB Output is correct
3 Correct 342 ms 22352 KB Output is correct
4 Correct 26 ms 15948 KB Output is correct
5 Incorrect 237 ms 23964 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 27 ms 15928 KB Output is correct
2 Correct 420 ms 28892 KB Output is correct
3 Correct 320 ms 28860 KB Output is correct
4 Correct 211 ms 29212 KB Output is correct
5 Correct 25 ms 15948 KB Output is correct
6 Correct 204 ms 23104 KB Output is correct
7 Correct 279 ms 22372 KB Output is correct
8 Correct 306 ms 23064 KB Output is correct
9 Correct 370 ms 22996 KB Output is correct
10 Correct 511 ms 26180 KB Output is correct
11 Correct 396 ms 25024 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15928 KB Output is correct
2 Correct 420 ms 28892 KB Output is correct
3 Correct 320 ms 28860 KB Output is correct
4 Correct 211 ms 29212 KB Output is correct
5 Correct 25 ms 15948 KB Output is correct
6 Correct 204 ms 23104 KB Output is correct
7 Correct 279 ms 22372 KB Output is correct
8 Correct 306 ms 23064 KB Output is correct
9 Correct 370 ms 22996 KB Output is correct
10 Correct 511 ms 26180 KB Output is correct
11 Correct 396 ms 25024 KB Output is correct
12 Correct 31 ms 15940 KB Output is correct
13 Incorrect 347 ms 29240 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 33 ms 15932 KB Output is correct
2 Correct 67 ms 16264 KB Output is correct
3 Correct 38 ms 16076 KB Output is correct
4 Correct 43 ms 16244 KB Output is correct
5 Correct 41 ms 16452 KB Output is correct
6 Correct 39 ms 16360 KB Output is correct
7 Correct 35 ms 15992 KB Output is correct
8 Correct 196 ms 23524 KB Output is correct
9 Correct 144 ms 23580 KB Output is correct
10 Correct 42 ms 16024 KB Output is correct
11 Correct 352 ms 28844 KB Output is correct
12 Correct 374 ms 28848 KB Output is correct
13 Correct 229 ms 29296 KB Output is correct
14 Correct 33 ms 16136 KB Output is correct
15 Correct 287 ms 23264 KB Output is correct
16 Correct 316 ms 22484 KB Output is correct
17 Correct 354 ms 23256 KB Output is correct
18 Correct 365 ms 23164 KB Output is correct
19 Correct 459 ms 26308 KB Output is correct
20 Correct 374 ms 25164 KB Output is correct
21 Correct 183 ms 23424 KB Output is correct
22 Correct 193 ms 23032 KB Output is correct
23 Correct 323 ms 22868 KB Output is correct
24 Correct 294 ms 22720 KB Output is correct
25 Correct 374 ms 25728 KB Output is correct
26 Correct 325 ms 21508 KB Output is correct
27 Correct 265 ms 21428 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 15932 KB Output is correct
2 Correct 67 ms 16264 KB Output is correct
3 Correct 38 ms 16076 KB Output is correct
4 Correct 43 ms 16244 KB Output is correct
5 Correct 41 ms 16452 KB Output is correct
6 Correct 39 ms 16360 KB Output is correct
7 Correct 35 ms 15992 KB Output is correct
8 Correct 196 ms 23524 KB Output is correct
9 Correct 144 ms 23580 KB Output is correct
10 Correct 42 ms 16024 KB Output is correct
11 Correct 352 ms 28844 KB Output is correct
12 Correct 374 ms 28848 KB Output is correct
13 Correct 229 ms 29296 KB Output is correct
14 Correct 33 ms 16136 KB Output is correct
15 Correct 287 ms 23264 KB Output is correct
16 Correct 316 ms 22484 KB Output is correct
17 Correct 354 ms 23256 KB Output is correct
18 Correct 365 ms 23164 KB Output is correct
19 Correct 459 ms 26308 KB Output is correct
20 Correct 374 ms 25164 KB Output is correct
21 Correct 183 ms 23424 KB Output is correct
22 Correct 193 ms 23032 KB Output is correct
23 Correct 323 ms 22868 KB Output is correct
24 Correct 294 ms 22720 KB Output is correct
25 Correct 374 ms 25728 KB Output is correct
26 Correct 325 ms 21508 KB Output is correct
27 Correct 265 ms 21428 KB Output is correct
28 Correct 26 ms 15996 KB Output is correct
29 Incorrect 43 ms 15840 KB Extra information in the output file
30 Halted 0 ms 0 KB -