oj.uz

Submission #912838

# Submission time Handle Problem Language Result Execution time Memory
912838 2024-01-20T02:43:36 Z Ice_man Inside information (BOI21_servers) C++14
5 / 100
 304 ms 524288 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 = 0;
    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(qpos > r || l > qpos)
            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(qpos > r)
            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)
    {
        return qu(1 , 0 , n - 1 , lower_bound(pom.begin() , pom.end() , qpos) - pom.begin());
    }


    void initialise()
    {
        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 << "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);
                    pom++;

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

                }

                pom_node = _prev[pom_node];

            }

            cout << ans << endl;

        }

    }
}




int main()
{

/**#ifdef ONLINE_JUDGE
    freopen("taxi.in", "r", stdin);
    freopen("taxi.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:309:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  309 |     for(int i = 0; i < queries.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~
servers.cpp: In function 'int get_last_from_path(int, int)':
servers.cpp:416:9: warning: unused variable 'ans' [-Wunused-variable]
  416 |     int ans = a;
      |         ^~~
servers.cpp: In function 'void answer()':
servers.cpp:506:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  506 |     for(int i = 0; i < queries.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 138088 KB Output is correct
2 Correct 183 ms 390872 KB Output is correct
3 Correct 183 ms 391096 KB Output is correct
4 Correct 198 ms 391104 KB Output is correct
5 Correct 187 ms 391364 KB Output is correct
6 Correct 185 ms 391036 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 138088 KB Output is correct
2 Correct 183 ms 390872 KB Output is correct
3 Correct 183 ms 391096 KB Output is correct
4 Correct 198 ms 391104 KB Output is correct
5 Correct 187 ms 391364 KB Output is correct
6 Correct 185 ms 391036 KB Output is correct
7 Correct 57 ms 137924 KB Output is correct
8 Correct 220 ms 390752 KB Output is correct
9 Correct 189 ms 390856 KB Output is correct
10 Correct 239 ms 390736 KB Output is correct
11 Correct 231 ms 391172 KB Output is correct
12 Correct 181 ms 390848 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 137924 KB Output is correct
2 Runtime error 263 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 137924 KB Output is correct
2 Runtime error 263 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 137924 KB Output is correct
2 Runtime error 302 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 137924 KB Output is correct
2 Runtime error 302 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 138052 KB Output is correct
2 Runtime error 258 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 138052 KB Output is correct
2 Runtime error 258 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 137920 KB Output is correct
2 Runtime error 304 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 137920 KB Output is correct
2 Runtime error 304 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 137868 KB Output is correct
2 Correct 192 ms 391072 KB Output is correct
3 Correct 189 ms 390936 KB Output is correct
4 Correct 193 ms 391108 KB Output is correct
5 Correct 192 ms 391420 KB Output is correct
6 Correct 194 ms 391048 KB Output is correct
7 Correct 62 ms 137988 KB Output is correct
8 Runtime error 248 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 137868 KB Output is correct
2 Correct 192 ms 391072 KB Output is correct
3 Correct 189 ms 390936 KB Output is correct
4 Correct 193 ms 391108 KB Output is correct
5 Correct 192 ms 391420 KB Output is correct
6 Correct 194 ms 391048 KB Output is correct
7 Correct 62 ms 137988 KB Output is correct
8 Runtime error 248 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -