oj.uz

Submission #912877

# Submission time Handle Problem Language Result Execution time Memory
912877 2024-01-20T03:51:56 Z Ice_man Inside information (BOI21_servers) C++14
5 / 100
 307 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++;
                    
                    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("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 56 ms 137176 KB Output is correct
2 Correct 171 ms 389952 KB Output is correct
3 Correct 174 ms 390068 KB Output is correct
4 Correct 176 ms 390084 KB Output is correct
5 Correct 169 ms 390404 KB Output is correct
6 Correct 171 ms 389956 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 137176 KB Output is correct
2 Correct 171 ms 389952 KB Output is correct
3 Correct 174 ms 390068 KB Output is correct
4 Correct 176 ms 390084 KB Output is correct
5 Correct 169 ms 390404 KB Output is correct
6 Correct 171 ms 389956 KB Output is correct
7 Correct 58 ms 137160 KB Output is correct
8 Correct 208 ms 389824 KB Output is correct
9 Correct 193 ms 390108 KB Output is correct
10 Correct 228 ms 389920 KB Output is correct
11 Correct 215 ms 390332 KB Output is correct
12 Correct 185 ms 390080 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 137100 KB Output is correct
2 Runtime error 235 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 57 ms 137100 KB Output is correct
2 Runtime error 235 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 51 ms 137156 KB Output is correct
2 Runtime error 307 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 51 ms 137156 KB Output is correct
2 Runtime error 307 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 65 ms 137156 KB Output is correct
2 Runtime error 235 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 65 ms 137156 KB Output is correct
2 Runtime error 235 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 52 ms 137152 KB Output is correct
2 Runtime error 305 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 52 ms 137152 KB Output is correct
2 Runtime error 305 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 137268 KB Output is correct
2 Correct 170 ms 389984 KB Output is correct
3 Correct 168 ms 390084 KB Output is correct
4 Correct 203 ms 390296 KB Output is correct
5 Correct 179 ms 390312 KB Output is correct
6 Correct 164 ms 390060 KB Output is correct
7 Correct 57 ms 137156 KB Output is correct
8 Runtime error 288 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 137268 KB Output is correct
2 Correct 170 ms 389984 KB Output is correct
3 Correct 168 ms 390084 KB Output is correct
4 Correct 203 ms 390296 KB Output is correct
5 Correct 179 ms 390312 KB Output is correct
6 Correct 164 ms 390060 KB Output is correct
7 Correct 57 ms 137156 KB Output is correct
8 Runtime error 288 ms 524288 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -