oj.uz

Submission #521092

# Submission time Handle Problem Language Result Execution time Memory
521092 2022-01-31T17:43:53 Z blue Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 34620 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 30 ms 15800 KB Output is correct
2 Correct 465 ms 17100 KB Output is correct
3 Correct 275 ms 16532 KB Output is correct
4 Correct 678 ms 17756 KB Output is correct
5 Correct 667 ms 17752 KB Output is correct
6 Correct 213 ms 16580 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 15800 KB Output is correct
2 Correct 465 ms 17100 KB Output is correct
3 Correct 275 ms 16532 KB Output is correct
4 Correct 678 ms 17756 KB Output is correct
5 Correct 667 ms 17752 KB Output is correct
6 Correct 213 ms 16580 KB Output is correct
7 Correct 29 ms 15812 KB Output is correct
8 Correct 517 ms 17340 KB Output is correct
9 Correct 351 ms 16768 KB Output is correct
10 Correct 643 ms 17800 KB Output is correct
11 Correct 766 ms 17908 KB Output is correct
12 Correct 456 ms 16708 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 15812 KB Output is correct
2 Execution timed out 3539 ms 29228 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 15812 KB Output is correct
2 Execution timed out 3539 ms 29228 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15824 KB Output is correct
2 Execution timed out 3552 ms 34240 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15824 KB Output is correct
2 Execution timed out 3552 ms 34240 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 15732 KB Output is correct
2 Execution timed out 3558 ms 28152 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 15732 KB Output is correct
2 Execution timed out 3558 ms 28152 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 15832 KB Output is correct
2 Execution timed out 3530 ms 34620 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 15832 KB Output is correct
2 Execution timed out 3530 ms 34620 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15756 KB Output is correct
2 Correct 574 ms 17016 KB Output is correct
3 Correct 279 ms 16480 KB Output is correct
4 Correct 713 ms 17604 KB Output is correct
5 Correct 784 ms 17744 KB Output is correct
6 Correct 190 ms 16608 KB Output is correct
7 Correct 45 ms 16072 KB Output is correct
8 Execution timed out 3597 ms 29636 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15756 KB Output is correct
2 Correct 574 ms 17016 KB Output is correct
3 Correct 279 ms 16480 KB Output is correct
4 Correct 713 ms 17604 KB Output is correct
5 Correct 784 ms 17744 KB Output is correct
6 Correct 190 ms 16608 KB Output is correct
7 Correct 45 ms 16072 KB Output is correct
8 Execution timed out 3597 ms 29636 KB Time limit exceeded
9 Halted 0 ms 0 KB -