oj.uz

Submission #912891

# Submission time Handle Problem Language Result Execution time Memory
912891 2024-01-20T04:03:38 Z Ice_man Inside information (BOI21_servers) C++14
100 / 100
 1181 ms 181904 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(){_n = 0;};
    /**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 97 ms 137304 KB Output is correct
2 Correct 118 ms 139568 KB Output is correct
3 Correct 108 ms 139396 KB Output is correct
4 Correct 116 ms 139676 KB Output is correct
5 Correct 110 ms 139976 KB Output is correct
6 Correct 114 ms 139444 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 97 ms 137304 KB Output is correct
2 Correct 118 ms 139568 KB Output is correct
3 Correct 108 ms 139396 KB Output is correct
4 Correct 116 ms 139676 KB Output is correct
5 Correct 110 ms 139976 KB Output is correct
6 Correct 114 ms 139444 KB Output is correct
7 Correct 90 ms 137280 KB Output is correct
8 Correct 117 ms 139448 KB Output is correct
9 Correct 111 ms 139556 KB Output is correct
10 Correct 144 ms 139400 KB Output is correct
11 Correct 138 ms 139828 KB Output is correct
12 Correct 108 ms 139452 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 82 ms 137156 KB Output is correct
2 Correct 289 ms 168580 KB Output is correct
3 Correct 322 ms 168728 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 82 ms 137156 KB Output is correct
2 Correct 289 ms 168580 KB Output is correct
3 Correct 322 ms 168728 KB Output is correct
4 Correct 89 ms 137232 KB Output is correct
5 Correct 312 ms 168620 KB Output is correct
6 Correct 171 ms 168896 KB Output is correct
7 Correct 183 ms 168824 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 137076 KB Output is correct
2 Correct 622 ms 181716 KB Output is correct
3 Correct 633 ms 181660 KB Output is correct
4 Correct 413 ms 181660 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 137076 KB Output is correct
2 Correct 622 ms 181716 KB Output is correct
3 Correct 633 ms 181660 KB Output is correct
4 Correct 413 ms 181660 KB Output is correct
5 Correct 78 ms 137156 KB Output is correct
6 Correct 704 ms 181492 KB Output is correct
7 Correct 619 ms 181596 KB Output is correct
8 Correct 989 ms 181408 KB Output is correct
9 Correct 890 ms 181556 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 137300 KB Output is correct
2 Correct 315 ms 169920 KB Output is correct
3 Correct 451 ms 170032 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 137300 KB Output is correct
2 Correct 315 ms 169920 KB Output is correct
3 Correct 451 ms 170032 KB Output is correct
4 Correct 83 ms 137196 KB Output is correct
5 Correct 567 ms 170016 KB Output is correct
6 Correct 428 ms 169892 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 78 ms 137152 KB Output is correct
2 Correct 598 ms 181620 KB Output is correct
3 Correct 643 ms 181592 KB Output is correct
4 Correct 513 ms 181604 KB Output is correct
5 Correct 81 ms 137128 KB Output is correct
6 Correct 321 ms 169984 KB Output is correct
7 Correct 394 ms 170428 KB Output is correct
8 Correct 527 ms 169564 KB Output is correct
9 Correct 551 ms 169644 KB Output is correct
10 Correct 624 ms 174380 KB Output is correct
11 Correct 657 ms 173436 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 78 ms 137152 KB Output is correct
2 Correct 598 ms 181620 KB Output is correct
3 Correct 643 ms 181592 KB Output is correct
4 Correct 513 ms 181604 KB Output is correct
5 Correct 81 ms 137128 KB Output is correct
6 Correct 321 ms 169984 KB Output is correct
7 Correct 394 ms 170428 KB Output is correct
8 Correct 527 ms 169564 KB Output is correct
9 Correct 551 ms 169644 KB Output is correct
10 Correct 624 ms 174380 KB Output is correct
11 Correct 657 ms 173436 KB Output is correct
12 Correct 79 ms 137152 KB Output is correct
13 Correct 856 ms 181564 KB Output is correct
14 Correct 667 ms 181568 KB Output is correct
15 Correct 1040 ms 181524 KB Output is correct
16 Correct 828 ms 181384 KB Output is correct
17 Correct 82 ms 137184 KB Output is correct
18 Correct 446 ms 169940 KB Output is correct
19 Correct 493 ms 170076 KB Output is correct
20 Correct 689 ms 169756 KB Output is correct
21 Correct 537 ms 169404 KB Output is correct
22 Correct 1131 ms 173080 KB Output is correct
23 Correct 1181 ms 174712 KB Output is correct
24 Correct 654 ms 174620 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 94 ms 137092 KB Output is correct
2 Correct 102 ms 139468 KB Output is correct
3 Correct 109 ms 139392 KB Output is correct
4 Correct 114 ms 139472 KB Output is correct
5 Correct 132 ms 139716 KB Output is correct
6 Correct 112 ms 139512 KB Output is correct
7 Correct 87 ms 137224 KB Output is correct
8 Correct 306 ms 168892 KB Output is correct
9 Correct 279 ms 168804 KB Output is correct
10 Correct 84 ms 137272 KB Output is correct
11 Correct 672 ms 181612 KB Output is correct
12 Correct 720 ms 181872 KB Output is correct
13 Correct 428 ms 181544 KB Output is correct
14 Correct 81 ms 137152 KB Output is correct
15 Correct 316 ms 170128 KB Output is correct
16 Correct 419 ms 170056 KB Output is correct
17 Correct 551 ms 169464 KB Output is correct
18 Correct 574 ms 169448 KB Output is correct
19 Correct 557 ms 174176 KB Output is correct
20 Correct 606 ms 173488 KB Output is correct
21 Correct 335 ms 168632 KB Output is correct
22 Correct 265 ms 168636 KB Output is correct
23 Correct 399 ms 168636 KB Output is correct
24 Correct 353 ms 169088 KB Output is correct
25 Correct 698 ms 172624 KB Output is correct
26 Correct 457 ms 169832 KB Output is correct
27 Correct 527 ms 170200 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 94 ms 137092 KB Output is correct
2 Correct 102 ms 139468 KB Output is correct
3 Correct 109 ms 139392 KB Output is correct
4 Correct 114 ms 139472 KB Output is correct
5 Correct 132 ms 139716 KB Output is correct
6 Correct 112 ms 139512 KB Output is correct
7 Correct 87 ms 137224 KB Output is correct
8 Correct 306 ms 168892 KB Output is correct
9 Correct 279 ms 168804 KB Output is correct
10 Correct 84 ms 137272 KB Output is correct
11 Correct 672 ms 181612 KB Output is correct
12 Correct 720 ms 181872 KB Output is correct
13 Correct 428 ms 181544 KB Output is correct
14 Correct 81 ms 137152 KB Output is correct
15 Correct 316 ms 170128 KB Output is correct
16 Correct 419 ms 170056 KB Output is correct
17 Correct 551 ms 169464 KB Output is correct
18 Correct 574 ms 169448 KB Output is correct
19 Correct 557 ms 174176 KB Output is correct
20 Correct 606 ms 173488 KB Output is correct
21 Correct 335 ms 168632 KB Output is correct
22 Correct 265 ms 168636 KB Output is correct
23 Correct 399 ms 168636 KB Output is correct
24 Correct 353 ms 169088 KB Output is correct
25 Correct 698 ms 172624 KB Output is correct
26 Correct 457 ms 169832 KB Output is correct
27 Correct 527 ms 170200 KB Output is correct
28 Correct 89 ms 137172 KB Output is correct
29 Correct 111 ms 139356 KB Output is correct
30 Correct 99 ms 139456 KB Output is correct
31 Correct 155 ms 139532 KB Output is correct
32 Correct 146 ms 139840 KB Output is correct
33 Correct 100 ms 139420 KB Output is correct
34 Correct 88 ms 137156 KB Output is correct
35 Correct 296 ms 168720 KB Output is correct
36 Correct 179 ms 169020 KB Output is correct
37 Correct 239 ms 168840 KB Output is correct
38 Correct 79 ms 137156 KB Output is correct
39 Correct 780 ms 181516 KB Output is correct
40 Correct 741 ms 181904 KB Output is correct
41 Correct 1008 ms 181688 KB Output is correct
42 Correct 1149 ms 181292 KB Output is correct
43 Correct 103 ms 137164 KB Output is correct
44 Correct 447 ms 170148 KB Output is correct
45 Correct 463 ms 169864 KB Output is correct
46 Correct 614 ms 169724 KB Output is correct
47 Correct 644 ms 169544 KB Output is correct
48 Correct 1091 ms 173696 KB Output is correct
49 Correct 1079 ms 175116 KB Output is correct
50 Correct 997 ms 174604 KB Output is correct
51 Correct 224 ms 168996 KB Output is correct
52 Correct 230 ms 168904 KB Output is correct
53 Correct 269 ms 168892 KB Output is correct
54 Correct 197 ms 168876 KB Output is correct
55 Correct 212 ms 168636 KB Output is correct
56 Correct 310 ms 168932 KB Output is correct
57 Correct 571 ms 172416 KB Output is correct
58 Correct 714 ms 169912 KB Output is correct
59 Correct 616 ms 169840 KB Output is correct