Submission #912858

#	Time	Username	Problem	Language	Result	Execution time	Memory
912858		Ice_man	Inside information (BOI21_servers)	C++14	2.50 / 100	298 ms	277680 KiB

servers

#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(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()
    {
        ///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);
                    pom++;

                    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 (stderr)

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: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5