oj.uz

답안 #521099

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
521099 2022-01-31T18:07:53 Z blue Inside information (BOI21_servers) C++17
52.5 / 100
 3500 ms 32868 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];
    }

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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -