oj.uz

Submission #912888

# Submission time Handle Problem Language Result Execution time Memory
912888 2024-01-20T04:01:54 Z Ice_man Inside information (BOI21_servers) C++14
100 / 100
 1216 ms 183568 KB 
#include <iostream>
#include <chrono>
#include <vector>

#define maxn 1000005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")

using namespace std;

std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}


struct query
{
    char type;
    int u , v;
    query(){};
    query(char _type , int _u , int _v)
    {
        type = _type;
        u = _u;
        v = _v;
    }
};

int n , q;

vector <int> v[maxn];
vector <query> queries;

void read()
{
    cin >> n >> q;

    char type;
    int u , _v;

    for(int i = 0; i < n + q - 1; i++)
    {
        cin >> type;

        if(type == 'S')
        {
            cin >> u >> _v;
            ///v[u].pb(_v);
            ///v[_v].pb(u);
            queries.push_back({type , u , _v});
        }

        if(type == 'Q')
        {
            cin >> u >> _v;
            queries.push_back({type , u , _v});
        }

        if(type == 'C')
        {
            cin >> u;
            queries.push_back({type , u , -1});
        }


    }

}

int bin_lift[maxlog][maxn];
int sz[maxn];
bool used[maxn];
int depth[maxn];

void dfs(int node , int parent)
{
    ///sz[node] = 1;
    ///used[node] = true;

    for(int nb : v[node])
    {
        if(nb == parent)
            continue;

        /**if(used[nb] == true)
            continue;*/

        bin_lift[0][nb] = node;
        depth[nb] = depth[node] + 1;

        dfs(nb , node);

    }

    ///return sz[node];

}

void calc_bin()
{
    for(int power = 1; power < maxlog; power++)
        for(int i = 1; i <= n; i++)
            bin_lift[power][i] = bin_lift[power - 1][bin_lift[power - 1][i]];
}


int get_lca(int a , int b)
{
    if(depth[a] < depth[b])
        swap(a , b);

    for(int power = maxlog - 1; power > -1; power--)
        if((depth[a] - depth[b]) >= (1 << power))
            a = bin_lift[power][a];

    if(a == b)
        return a;

    for(int power = maxlog - 1; power > -1; power--)
        if(bin_lift[power][a] != bin_lift[power][b])
        {
            a = bin_lift[power][a];
            b = bin_lift[power][b];
        }

    return bin_lift[0][a];

}

int calc_sz(int node , int parent)
{
    sz[node] = 1;

    for(int nb : v[node])
    {
        if(nb == parent)
            continue;

        if(used[nb] == true)
            continue;

        sz[node] += calc_sz(nb , node);

    }

    return sz[node];

}

int get_centroid(int node , int parent , int cur_sz)
{
    for(int nb : v[node])
    {
        if(nb == parent)
            continue;

        if(used[nb] == true)
            continue;

        if(sz[nb] > cur_sz / 2)
            return get_centroid(nb , node , cur_sz);

    }

    return node;

}


int _prev[maxn];
int centroid_depth[maxn];

void centroid_decomposition(int node , int parent)
{
    node = get_centroid(node,  -1 , calc_sz(node , -1));

    _prev[node] = parent;
    centroid_depth[node] = parent > 0 ? centroid_depth[parent] + 1 : 0;

    used[node] = true;

    for(int nb : v[node])
    {
        if(used[nb] == true)
            continue;

        centroid_decomposition(nb , node);
    }

    used[node] = false;

}

int /**sz[maxn] , */heavy[maxn];
int leader[maxn];

int hld(int node , int parent)
{
    sz[node] = 1;
    heavy[node] = -1;

    leader[node] = node;

    for(int nb : v[node])
    {
        if(nb == parent)
            continue;

        sz[node] += hld(nb , node);

        if(heavy[node] < 0 || sz[nb] > sz[heavy[node]])
            heavy[node] = nb;
    }

    return sz[node];

}


struct segment_tree
{
    int _n;
    vector <int> tree;
    vector <int> pom;

    segment_tree(){};
    /**segment_tree(int __n)
    {
        _n = __n;
        tree = vector <int> (4 * n , 0);
    }*/

    void update(int node , int l , int r , int qval , int qpos)
    {
        if(r < qpos || qpos < l)
            return;

        if(qpos <= l && r <= qpos)
        {
            tree[node] += qval;
            return;
        }

        int mid = (l + r) / 2;

        update(node * 2 , l , mid , qval , qpos);
        update(node * 2 + 1 , mid + 1 , r , qval , qpos);

        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    int qu(int node , int l , int r , int qpos)
    {
        if(r < qpos)
            return 0;

        if(qpos <= l)
            return tree[node];

        int mid = (l + r) / 2;

        return qu(node * 2 , l , mid , qpos) + qu(node * 2 + 1 , mid + 1 , r , qpos);
    }

    void _update(int qpos)
    {
        update(1 , 0 , _n - 1 , 1 , (lower_bound(pom.begin() , pom.end() , qpos) - pom.begin()));
    }

    int query(int qpos)
    {
        ///cout << (lower_bound(pom.begin() , pom.end() , qpos) - pom.begin()) << endl;
        return qu(1 , 0 , _n - 1 , (lower_bound(pom.begin() , pom.end() , qpos) - pom.begin()));
    }


    void initialise()
    {
        ///cout << _n << endl;
        tree.resize(4 * _n);
        fill(tree.begin() , tree.end() , 0);
    }

};

segment_tree _tree[maxn];

int up[maxn][2] , down[maxn];
int idx[maxn];


void initialisation()
{
    for(int i = 0; i < queries.size(); i++)
    {
        if(queries[i].type != 'S')
            continue;

        v[queries[i].u].pb(queries[i].v);
        v[queries[i].v].pb(queries[i].u);

    }

    /**for(int i = 1; i <= n; i++)
    {
        cout << i << ": ";
        for(int nb : v[i])
            cout << nb << " ";
        cout << endl;
    }*/


    centroid_decomposition(1 , -1);

    /**for(int i = 1; i <= n; i++)
        cout << _prev[i] << " ";
    cout << endl;
    for(int i = 1; i <= n; i++)
        cout << centroid_depth[i] << " ";
    cout << endl;*/

    for(int node = 1; node <= n; node++)
    {
        for(int nb : v[node])
            if(centroid_depth[nb] > centroid_depth[node])
                _tree[node]._n++;

        _tree[node].initialise();

    }

    dfs(1 , -1);
    calc_bin();

    /**for(int i = 1; i <= n; i++)
    {
        cout << i << ": ";
        for(int j = 0; j <= 4; j++)
            cout << bin_lift[j][i] << " ";
        cout << endl;
    }*/



    hld(1 , -1);

    for(int node = 1; node <= n; node++)
        if(bin_lift[0][node] == 0 || heavy[bin_lift[0][node]] != node)
            for(int nb = node; nb != -1; nb = heavy[nb])
                leader[nb] = node;

    /**for(int i = 1; i <= n; i++)
        cout << leader[i] << " ";
    cout << endl;*/

    /**for(int i = 1; i <= n; i++)
        cout << heavy[i] << " ";
    cout << endl;*/

    /**cout << endl;
    for(int i = 1; i <= n; i++)
        cout << _prev[i] << " ";
    cout << endl << endl;*/

    for(int i = 1; i <= n; i++)
    {
        up[i][0] = i;
        up[i][1] = i;
        idx[i] = (maxn + 1);
        down[i] = i;
    }


}

int higher(int a , int b)
{
    return depth[a] < depth[b]? b : a;
}

int lower(int a , int b)
{
    return depth[a] > depth[b]? b : a;
}

int get_idx(int a , int b)
{
    return a == b? 0 : idx[higher(a , b)];
}

int get_last_from_path(int a , int b)
{
    if(a == b)
        return a;

    int lca = get_lca(a , b);

    if(lca != b)
        return bin_lift[0][b];

    int ans = a;

    int dist = depth[a] - depth[lca] - 1;

    for(int power = maxlog - 1; power > -1; power--)
        if(dist >= (1 << power))
        {
            a = bin_lift[power][a];
            dist -= (1 << power);
        }

    return a;

}


bool check_has(int a , int b)
{
    if(a == b)
        return true;

    int lca = get_lca(a , b);

    ///cout << ":: " << lca << endl;

    if(lower(up[a][0] , lca) != up[a][0])
        return false;

    int pom_node = b;
    int pom = -1;


    while(leader[pom_node] != leader[lca])
    {
        pom = leader[pom_node];
        pom_node = bin_lift[0][leader[pom_node]];
    }

    if(b != pom_node && lower(up[b][1] , pom_node) != up[b][1])
        return false;

    /**if(a == 4 && b == 1)
        cout << "|-> " << pom_node << " " << pom << endl;*/

    if(higher(down[lca] , pom_node) != down[lca] || (pom_node != lca && pom != -1 && get_idx(pom , pom_node) > idx[pom_node]))
        return false;

    /**if(a == 4 && b == 1)
        cout << "asdjas" << endl;*/

    if(a == lca)
        return true;

    if(b == lca)
        return true;

    int pom1 = get_last_from_path(a , lca);
    int pom2 = get_last_from_path(b , lca);

    if(idx[pom1] > idx[pom2])
        return true;

    return false;

}


void rec(int a , int b , int c , int val)
{
    up[a][1] = val;

    for(int nb : v[a])
    {
        if(nb == b)
            continue;

        if(get_idx(a , nb) >= c)
            continue;

        rec(nb , a , get_idx(a , nb) , val);
    }

}

int moment = 0;

void answer()
{
    initialisation();

    for(int i = 0; i < queries.size(); i++)
    {
        if(queries[i].type == 'S')
        {
            moment++;

            if(centroid_depth[queries[i].u] > centroid_depth[queries[i].v])
                swap(queries[i].u , queries[i].v);

            if(depth[queries[i].u] > depth[queries[i].v])
                swap(queries[i].u , queries[i].v);

            ///cout << "-> " << queries[i].v << endl;

            idx[queries[i].v] = moment;

            up[queries[i].v][0] = up[queries[i].u][0];

            if(heavy[queries[i].u] != queries[i].v)
                rec(queries[i].v , queries[i].u , moment , queries[i].u);
            else
                down[queries[i].u] = down[queries[i].v];

            /**cout << "----------" << endl;
            for(int i = 1; i <= n; i++)
                cout << idx[i] << " ";
            cout << endl;
            for(int i = 1; i <= n; i++)
                cout << up[i][0] << " ";
            cout << endl;
            for(int i = 1; i <= n; i++)
                cout << up[i][1] << " ";
            cout << endl;
            for(int i = 1; i <= n; i++)
                cout << down[i] << " ";
            cout << endl << "-----------" << endl;*/

            if(centroid_depth[queries[i].u] > centroid_depth[queries[i].v])
                swap(queries[i].u , queries[i].v);

            _tree[queries[i].u].pom.pb(moment);


            int pom_node = queries[i].u;

            while(pom_node > 0)
            {
                ///cout << "__ " << queries[i].u << " " << pom_node << " " << check_has(queries[i].u , pom_node) << endl;

                if(check_has(queries[i].u , pom_node) == true)
                {
                    int first_node = get_last_from_path(queries[i].u , pom_node);

                    if(first_node == pom_node)
                        first_node = queries[i].v;

                    ///cout << "* " << pom_node << " " << first_node << endl;

                    int pom = get_idx(pom_node , first_node);

                    ///cout << pom << endl;


                    _tree[pom_node]._update(pom);

                }

                pom_node = _prev[pom_node];

            }


        }

        if(queries[i].type == 'Q')
        {
            if(check_has(queries[i].u , queries[i].v) == true)
                cout << "yes" << endl;
            else
            {
                ///cout << 1 / 0 << endl;
                cout << "no" << endl;
            }

        }



        if(queries[i].type == 'C')
        {
            ///control

            int pom_node = queries[i].u;
            int ans = 0;

            while(pom_node > 0)
            {
                if(check_has(pom_node , queries[i].u) == true)
                {
                    int _last = get_last_from_path(queries[i].u , pom_node);
                    int pom = get_idx(_last , pom_node) + 1;

                    ///cout << "--< " << pom_node << " " << pom << " " << _tree[pom_node]._n << " ";

                    /**if(_tree[pom_node]._n == 0)
                    {
                        ans++;
                        pom_node = _prev[pom_node];
                        continue;
                    }*/

                    ans += _tree[pom_node].query(pom) + 1;

                }

                pom_node = _prev[pom_node];

            }

            cout << ans << endl;

        }

    }
}




int main()
{

/**#ifdef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif*/

    //ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);

    startT = std::chrono::high_resolution_clock::now();

    read();
    answer();


    return 0;
}

Compilation message

servers.cpp: In function 'void initialisation()':
servers.cpp:310:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  310 |     for(int i = 0; i < queries.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~
servers.cpp: In function 'int get_last_from_path(int, int)':
servers.cpp:417:9: warning: unused variable 'ans' [-Wunused-variable]
  417 |     int ans = a;
      |         ^~~
servers.cpp: In function 'void answer()':
servers.cpp:507:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  507 |     for(int i = 0; i < queries.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 92 ms 137148 KB Output is correct
2 Correct 105 ms 139564 KB Output is correct
3 Correct 100 ms 139456 KB Output is correct
4 Correct 117 ms 139708 KB Output is correct
5 Correct 121 ms 139960 KB Output is correct
6 Correct 104 ms 139596 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 92 ms 137148 KB Output is correct
2 Correct 105 ms 139564 KB Output is correct
3 Correct 100 ms 139456 KB Output is correct
4 Correct 117 ms 139708 KB Output is correct
5 Correct 121 ms 139960 KB Output is correct
6 Correct 104 ms 139596 KB Output is correct
7 Correct 78 ms 137044 KB Output is correct
8 Correct 111 ms 139456 KB Output is correct
9 Correct 103 ms 139456 KB Output is correct
10 Correct 149 ms 139464 KB Output is correct
11 Correct 143 ms 139720 KB Output is correct
12 Correct 102 ms 139420 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 79 ms 137152 KB Output is correct
2 Correct 300 ms 168632 KB Output is correct
3 Correct 325 ms 168584 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 79 ms 137152 KB Output is correct
2 Correct 300 ms 168632 KB Output is correct
3 Correct 325 ms 168584 KB Output is correct
4 Correct 78 ms 137148 KB Output is correct
5 Correct 266 ms 168788 KB Output is correct
6 Correct 183 ms 169084 KB Output is correct
7 Correct 220 ms 168928 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 137148 KB Output is correct
2 Correct 600 ms 181624 KB Output is correct
3 Correct 583 ms 183400 KB Output is correct
4 Correct 405 ms 183476 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 137148 KB Output is correct
2 Correct 600 ms 181624 KB Output is correct
3 Correct 583 ms 183400 KB Output is correct
4 Correct 405 ms 183476 KB Output is correct
5 Correct 75 ms 137988 KB Output is correct
6 Correct 984 ms 183364 KB Output is correct
7 Correct 703 ms 183380 KB Output is correct
8 Correct 729 ms 183028 KB Output is correct
9 Correct 819 ms 182836 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 137076 KB Output is correct
2 Correct 330 ms 170016 KB Output is correct
3 Correct 343 ms 169960 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 137076 KB Output is correct
2 Correct 330 ms 170016 KB Output is correct
3 Correct 343 ms 169960 KB Output is correct
4 Correct 80 ms 137148 KB Output is correct
5 Correct 428 ms 169984 KB Output is correct
6 Correct 458 ms 172152 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 80 ms 137152 KB Output is correct
2 Correct 746 ms 181724 KB Output is correct
3 Correct 585 ms 183372 KB Output is correct
4 Correct 441 ms 183472 KB Output is correct
5 Correct 85 ms 138020 KB Output is correct
6 Correct 347 ms 172112 KB Output is correct
7 Correct 412 ms 171956 KB Output is correct
8 Correct 525 ms 171272 KB Output is correct
9 Correct 530 ms 171444 KB Output is correct
10 Correct 679 ms 176168 KB Output is correct
11 Correct 596 ms 175256 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 80 ms 137152 KB Output is correct
2 Correct 746 ms 181724 KB Output is correct
3 Correct 585 ms 183372 KB Output is correct
4 Correct 441 ms 183472 KB Output is correct
5 Correct 85 ms 138020 KB Output is correct
6 Correct 347 ms 172112 KB Output is correct
7 Correct 412 ms 171956 KB Output is correct
8 Correct 525 ms 171272 KB Output is correct
9 Correct 530 ms 171444 KB Output is correct
10 Correct 679 ms 176168 KB Output is correct
11 Correct 596 ms 175256 KB Output is correct
12 Correct 86 ms 138008 KB Output is correct
13 Correct 818 ms 183316 KB Output is correct
14 Correct 664 ms 183380 KB Output is correct
15 Correct 733 ms 182996 KB Output is correct
16 Correct 874 ms 182972 KB Output is correct
17 Correct 95 ms 137912 KB Output is correct
18 Correct 437 ms 172016 KB Output is correct
19 Correct 593 ms 172064 KB Output is correct
20 Correct 529 ms 171324 KB Output is correct
21 Correct 648 ms 171140 KB Output is correct
22 Correct 1216 ms 174800 KB Output is correct
23 Correct 1104 ms 176684 KB Output is correct
24 Correct 797 ms 176448 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 78 ms 137156 KB Output is correct
2 Correct 102 ms 139448 KB Output is correct
3 Correct 99 ms 139572 KB Output is correct
4 Correct 136 ms 139464 KB Output is correct
5 Correct 101 ms 139856 KB Output is correct
6 Correct 103 ms 139460 KB Output is correct
7 Correct 79 ms 137156 KB Output is correct
8 Correct 314 ms 170396 KB Output is correct
9 Correct 268 ms 170644 KB Output is correct
10 Correct 75 ms 138060 KB Output is correct
11 Correct 624 ms 183568 KB Output is correct
12 Correct 629 ms 183548 KB Output is correct
13 Correct 409 ms 183480 KB Output is correct
14 Correct 80 ms 137920 KB Output is correct
15 Correct 293 ms 171824 KB Output is correct
16 Correct 371 ms 171944 KB Output is correct
17 Correct 528 ms 171308 KB Output is correct
18 Correct 493 ms 171992 KB Output is correct
19 Correct 614 ms 176500 KB Output is correct
20 Correct 550 ms 175380 KB Output is correct
21 Correct 289 ms 170560 KB Output is correct
22 Correct 266 ms 170696 KB Output is correct
23 Correct 373 ms 170588 KB Output is correct
24 Correct 356 ms 170564 KB Output is correct
25 Correct 605 ms 174332 KB Output is correct
26 Correct 471 ms 172128 KB Output is correct
27 Correct 423 ms 171908 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 78 ms 137156 KB Output is correct
2 Correct 102 ms 139448 KB Output is correct
3 Correct 99 ms 139572 KB Output is correct
4 Correct 136 ms 139464 KB Output is correct
5 Correct 101 ms 139856 KB Output is correct
6 Correct 103 ms 139460 KB Output is correct
7 Correct 79 ms 137156 KB Output is correct
8 Correct 314 ms 170396 KB Output is correct
9 Correct 268 ms 170644 KB Output is correct
10 Correct 75 ms 138060 KB Output is correct
11 Correct 624 ms 183568 KB Output is correct
12 Correct 629 ms 183548 KB Output is correct
13 Correct 409 ms 183480 KB Output is correct
14 Correct 80 ms 137920 KB Output is correct
15 Correct 293 ms 171824 KB Output is correct
16 Correct 371 ms 171944 KB Output is correct
17 Correct 528 ms 171308 KB Output is correct
18 Correct 493 ms 171992 KB Output is correct
19 Correct 614 ms 176500 KB Output is correct
20 Correct 550 ms 175380 KB Output is correct
21 Correct 289 ms 170560 KB Output is correct
22 Correct 266 ms 170696 KB Output is correct
23 Correct 373 ms 170588 KB Output is correct
24 Correct 356 ms 170564 KB Output is correct
25 Correct 605 ms 174332 KB Output is correct
26 Correct 471 ms 172128 KB Output is correct
27 Correct 423 ms 171908 KB Output is correct
28 Correct 85 ms 137836 KB Output is correct
29 Correct 107 ms 140232 KB Output is correct
30 Correct 99 ms 140236 KB Output is correct
31 Correct 153 ms 140388 KB Output is correct
32 Correct 136 ms 140484 KB Output is correct
33 Correct 98 ms 140312 KB Output is correct
34 Correct 79 ms 138056 KB Output is correct
35 Correct 387 ms 170356 KB Output is correct
36 Correct 191 ms 170300 KB Output is correct
37 Correct 178 ms 170124 KB Output is correct
38 Correct 75 ms 137932 KB Output is correct
39 Correct 830 ms 183564 KB Output is correct
40 Correct 541 ms 183516 KB Output is correct
41 Correct 783 ms 182848 KB Output is correct
42 Correct 812 ms 182848 KB Output is correct
43 Correct 92 ms 138016 KB Output is correct
44 Correct 460 ms 171956 KB Output is correct
45 Correct 465 ms 171728 KB Output is correct
46 Correct 579 ms 171536 KB Output is correct
47 Correct 770 ms 171504 KB Output is correct
48 Correct 1199 ms 174720 KB Output is correct
49 Correct 1202 ms 176592 KB Output is correct
50 Correct 725 ms 176360 KB Output is correct
51 Correct 245 ms 171064 KB Output is correct
52 Correct 266 ms 170460 KB Output is correct
53 Correct 218 ms 170428 KB Output is correct
54 Correct 233 ms 170832 KB Output is correct
55 Correct 215 ms 170148 KB Output is correct
56 Correct 328 ms 170584 KB Output is correct
57 Correct 463 ms 173612 KB Output is correct
58 Correct 790 ms 171372 KB Output is correct
59 Correct 436 ms 171960 KB Output is correct