oj.uz

Submission #521093

# Submission time Handle Problem Language Result Execution time Memory
521093 2022-01-31T17:44:04 Z blue Inside information (BOI21_servers) C++17
67.5 / 100
 3500 ms 32116 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;


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



    vi alist;
    for(int a: lst)
    {
        if(a == cent || out_good[a]) 
            {
                alist.push_back(a);
                // cerr << "pushing " << a << '\n';
            }
    }

    for(int d: lst)
    {
        if(d == cent)
        {
            for(int t: C[d])
            {
                for(int a: alist)
                    res[t] += (a == cent || par_time[a] < t);
            }
        }
        else 
        {
            if(!in_good[d]) continue;

            for(int t: C[d])
            {
                if(t < root_time[d]) continue;

                for(int a: alist)
                    res[t] += (a == cent || (par_time[a] < t && root_time[a] > root_time[d]));
            }
        }
    }





    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 41 ms 15448 KB Output is correct
2 Correct 57 ms 15692 KB Output is correct
3 Correct 53 ms 15580 KB Output is correct
4 Correct 50 ms 15808 KB Output is correct
5 Correct 39 ms 16016 KB Output is correct
6 Correct 43 ms 15864 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 15448 KB Output is correct
2 Correct 57 ms 15692 KB Output is correct
3 Correct 53 ms 15580 KB Output is correct
4 Correct 50 ms 15808 KB Output is correct
5 Correct 39 ms 16016 KB Output is correct
6 Correct 43 ms 15864 KB Output is correct
7 Correct 35 ms 15436 KB Output is correct
8 Correct 50 ms 15348 KB Output is correct
9 Correct 108 ms 15248 KB Output is correct
10 Correct 57 ms 15404 KB Output is correct
11 Correct 66 ms 15636 KB Output is correct
12 Correct 342 ms 15332 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 15456 KB Output is correct
2 Correct 133 ms 22444 KB Output is correct
3 Correct 149 ms 22988 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 15456 KB Output is correct
2 Correct 133 ms 22444 KB Output is correct
3 Correct 149 ms 22988 KB Output is correct
4 Correct 39 ms 15856 KB Output is correct
5 Execution timed out 3552 ms 24608 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15492 KB Output is correct
2 Correct 328 ms 28384 KB Output is correct
3 Correct 373 ms 28952 KB Output is correct
4 Correct 212 ms 29096 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15492 KB Output is correct
2 Correct 328 ms 28384 KB Output is correct
3 Correct 373 ms 28952 KB Output is correct
4 Correct 212 ms 29096 KB Output is correct
5 Correct 29 ms 15812 KB Output is correct
6 Correct 343 ms 31736 KB Output is correct
7 Correct 2149 ms 32116 KB Output is correct
8 Correct 316 ms 30920 KB Output is correct
9 Correct 299 ms 30964 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15552 KB Output is correct
2 Correct 218 ms 22112 KB Output is correct
3 Correct 309 ms 22384 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15552 KB Output is correct
2 Correct 218 ms 22112 KB Output is correct
3 Correct 309 ms 22384 KB Output is correct
4 Correct 28 ms 15788 KB Output is correct
5 Correct 2283 ms 25504 KB Output is correct
6 Correct 281 ms 25068 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 15548 KB Output is correct
2 Correct 383 ms 28376 KB Output is correct
3 Correct 338 ms 28896 KB Output is correct
4 Correct 279 ms 29096 KB Output is correct
5 Correct 26 ms 16076 KB Output is correct
6 Correct 202 ms 22608 KB Output is correct
7 Correct 347 ms 22392 KB Output is correct
8 Correct 336 ms 23096 KB Output is correct
9 Correct 381 ms 23040 KB Output is correct
10 Correct 414 ms 26044 KB Output is correct
11 Correct 363 ms 24924 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 15548 KB Output is correct
2 Correct 383 ms 28376 KB Output is correct
3 Correct 338 ms 28896 KB Output is correct
4 Correct 279 ms 29096 KB Output is correct
5 Correct 26 ms 16076 KB Output is correct
6 Correct 202 ms 22608 KB Output is correct
7 Correct 347 ms 22392 KB Output is correct
8 Correct 336 ms 23096 KB Output is correct
9 Correct 381 ms 23040 KB Output is correct
10 Correct 414 ms 26044 KB Output is correct
11 Correct 363 ms 24924 KB Output is correct
12 Correct 29 ms 15776 KB Output is correct
13 Correct 357 ms 31740 KB Output is correct
14 Correct 2237 ms 32104 KB Output is correct
15 Correct 332 ms 30904 KB Output is correct
16 Correct 308 ms 30856 KB Output is correct
17 Correct 28 ms 16344 KB Output is correct
18 Correct 2164 ms 25552 KB Output is correct
19 Correct 269 ms 25152 KB Output is correct
20 Correct 316 ms 26028 KB Output is correct
21 Correct 328 ms 25944 KB Output is correct
22 Correct 1298 ms 27396 KB Output is correct
23 Execution timed out 3529 ms 28116 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 15456 KB Output is correct
2 Correct 36 ms 15772 KB Output is correct
3 Correct 38 ms 15564 KB Output is correct
4 Correct 45 ms 15852 KB Output is correct
5 Correct 41 ms 15992 KB Output is correct
6 Correct 33 ms 15796 KB Output is correct
7 Correct 25 ms 15512 KB Output is correct
8 Correct 134 ms 22516 KB Output is correct
9 Correct 156 ms 22956 KB Output is correct
10 Correct 27 ms 16068 KB Output is correct
11 Correct 320 ms 28944 KB Output is correct
12 Correct 355 ms 28892 KB Output is correct
13 Correct 229 ms 29044 KB Output is correct
14 Correct 27 ms 16052 KB Output is correct
15 Correct 240 ms 22592 KB Output is correct
16 Correct 306 ms 22376 KB Output is correct
17 Correct 337 ms 23096 KB Output is correct
18 Correct 331 ms 23036 KB Output is correct
19 Correct 429 ms 26216 KB Output is correct
20 Correct 347 ms 24916 KB Output is correct
21 Correct 173 ms 22440 KB Output is correct
22 Correct 158 ms 22252 KB Output is correct
23 Correct 271 ms 22684 KB Output is correct
24 Correct 232 ms 22636 KB Output is correct
25 Correct 391 ms 25540 KB Output is correct
26 Correct 300 ms 21468 KB Output is correct
27 Correct 266 ms 21420 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 15456 KB Output is correct
2 Correct 36 ms 15772 KB Output is correct
3 Correct 38 ms 15564 KB Output is correct
4 Correct 45 ms 15852 KB Output is correct
5 Correct 41 ms 15992 KB Output is correct
6 Correct 33 ms 15796 KB Output is correct
7 Correct 25 ms 15512 KB Output is correct
8 Correct 134 ms 22516 KB Output is correct
9 Correct 156 ms 22956 KB Output is correct
10 Correct 27 ms 16068 KB Output is correct
11 Correct 320 ms 28944 KB Output is correct
12 Correct 355 ms 28892 KB Output is correct
13 Correct 229 ms 29044 KB Output is correct
14 Correct 27 ms 16052 KB Output is correct
15 Correct 240 ms 22592 KB Output is correct
16 Correct 306 ms 22376 KB Output is correct
17 Correct 337 ms 23096 KB Output is correct
18 Correct 331 ms 23036 KB Output is correct
19 Correct 429 ms 26216 KB Output is correct
20 Correct 347 ms 24916 KB Output is correct
21 Correct 173 ms 22440 KB Output is correct
22 Correct 158 ms 22252 KB Output is correct
23 Correct 271 ms 22684 KB Output is correct
24 Correct 232 ms 22636 KB Output is correct
25 Correct 391 ms 25540 KB Output is correct
26 Correct 300 ms 21468 KB Output is correct
27 Correct 266 ms 21420 KB Output is correct
28 Correct 28 ms 15860 KB Output is correct
29 Correct 50 ms 16432 KB Output is correct
30 Correct 111 ms 16288 KB Output is correct
31 Correct 41 ms 16564 KB Output is correct
32 Correct 39 ms 16692 KB Output is correct
33 Correct 342 ms 16428 KB Output is correct
34 Correct 27 ms 16384 KB Output is correct
35 Execution timed out 3530 ms 24532 KB Time limit exceeded
36 Halted 0 ms 0 KB -