Submission #1093309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093309		Ice_man	Inside information (BOI21_servers)	C++14	0 / 100	54 ms	17096 KiB

servers

/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <iostream>
#include <chrono>
#include <set>
#include <vector>
#include <algorithm>

#define maxn 240005
#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;

using namespace std;


typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef long long ll;
typedef pair <ll, ll> pll;
typedef pair <int, ll> pil;
typedef pair <ll, int> pli;
typedef long double pd;


struct edge
{
    int to, x;

    edge() {};
    edge(int _to, int _x)
    {
        to = _to;
        x = _x;
    }
};

vector <edge> v[maxn];

bool cmp(edge e1, edge e2)
{
    return e2.x < e1.x;
}



struct query
{
    char type;
    int x, y;

    query() {};
    query(char _type, int _x, int _y)
    {
        type = _type;
        x = _x;
        y = _y;
    }
};

vector <query> queries;


int bin_lift[maxn][maxlog];
int depth[maxn];

void dfs_bin(int node, int par)
{
    //sz[node] = 1;

    for(edge nb : v[node])
    {
        if(nb.to == par)
            continue;

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

        dfs_bin(nb.to, node);

        //sz[node] += sz[nb.to];
    }
}

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

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

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

    if(a == b)
        return a;

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

    return bin_lift[a][0];
}



int weight[maxn];
int up[maxn], down[maxn];

int timer , in[maxn] , out[maxn];

void dfs_sort(int node, int par)
{
    timer++;
    in[node] = timer;

    sort(v[node].begin() , v[node].end() , cmp);

    if(par == 1)
    {
        up[node] = par;
        down[node] = par;
    }
    else
        if(weight[node] > weight[par])
        {
            down[node] = down[par];
            up[node] = par;
        }
        else
        {
            up[node] = up[par];
            down[node] = par;
        }

    for(edge nb : v[node])
    {
        if(nb.to == par)
            continue;

        weight[nb.to] = nb.x;
        dfs_sort(nb.to , node);
    }
    out[node] = timer;
}


int tree[maxn * 4];

int query(int node , int l , int r , int ql , int qr)
{
    if(l > qr || r < ql)
        return 0;
    if(l >= ql && r <= qr)
        return tree[node];

    int mid = (l + r) / 2;

    return query(node * 2 , l , mid , ql , qr) +
            query(node * 2 + 1 , mid + 1 , r , ql , qr);
}

void update(int node , int l , int r , int qpos , int qval)
{
    if(l == r)
    {
        tree[node] += qval;
        return;
    }

    int mid = (l + r) / 2;

    if(qpos <= mid)
        update(node * 2 , l , mid , qpos , qval);
    else
        update(node * 2 + 1 , mid + 1 , r , qpos , qval);

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


int used[maxn];
int sz[maxn] , br;
vector <int> qu[maxn];

int find_centroid(int node , int par)
{
    for(edge nb : v[node])
    {
        if(used[nb.to] == true)
            continue;
        if(nb.to == par)
            continue;

        if(sz[nb.to] > br / 2)
            return find_centroid(nb.to , node);
    }
    return node;
}


vector <int> done;
void push_updates(int node , int par , int prev)
{
    update(1 , 1 , maxn * 4 - 1 , prev , 1);
    done.pb(prev);

    for(edge nb : v[node])
    {
        if(nb.to == par)
            continue;
        if(used[nb.to] == true)
            continue;
        if(nb.x < prev)
            continue;

        push_updates(nb.to , node , nb.x);
    }
}


int ans[maxn];
void dfs_update(int node , int par , int fix , int prev)
{
    //cout << "innn" << endl;

    for(int i : qu[node])
    {
        ans[i] += query(1 , 1 , maxn * 4 - 1 , 1 , i);
        if(i > fix)
            ans[i]++;
    }

    for(edge nb : v[node])
    {
        if(used[node] == true)
            continue;
        if(nb.x > prev)
            continue;
        if(nb.to == par)
            continue;

        dfs_update(nb.to , node , fix , nb.x);
    }
}



void calc_sz(int node , int par)
{
    sz[node] = 1;
    for(edge nb : v[node])
    {
        if(used[nb.to] == true)
            continue;
        if(nb.to == par)
            continue;

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


void decompose(int node , int par)
{
    //cout << "in" << endl;

    for(int e : done)
        update(1 , 1 ,maxn * 4 - 1 , e , -1);
    done.clear();

    calc_sz(node , -1);
    br = sz[node];
    int centroid = find_centroid(node , -1);
    used[centroid] = true;

    //cout << "here" << endl;

    for(edge nb : v[centroid])
    {
        if(used[nb.to] == true)
            continue;

        //cout << "0" << endl;

        dfs_update(nb.to , centroid , nb.x , nb.x);

        //cout << "1" << endl;

        push_updates(nb.to , centroid , nb.x);

        //cout << "2" << endl;
    }

    //cout << "here" << endl;

    for(int i : qu[centroid])
        ans[i] += query(1 , 1 , maxn * 4 - 1 , 1 , i);

    for(edge nb : v[centroid])
    {
        if(used[nb.to] == true)
            continue;
        decompose(nb.to , node);
    }
}


int jump(int node , int steps)
{
    for(int power = maxlog - 1; power > -1; power--)
        if(steps >= (1 << power))
        {
            node = bin_lift[node][power];
            steps -= (1 << power);
        }
    return node;
}


bool answer(int x , int y , int time)
{
    if(x == y)
        return true;

    int lca = get_lca(x , y);

    int cx = x , cy = y;
    if(depth[cx] == depth[lca])
    {
        cy = jump(cy , depth[cy] - depth[cx] - 1);
        if(weight[cy] > time)
            return false;
    }

    if(weight[cx] > time)
        return false;

    //cout << "kys" << endl;

    if(depth[down[x]] <= depth[lca] && depth[up[y]] <= depth[lca])
    {
        if(depth[x] == depth[lca])
            return true;
        if(depth[y] == depth[lca])
            return true;

        x = jump(x , depth[x] - depth[lca] - 1);
        y = jump(y , depth[y] - depth[lca] - 1);

        if(weight[x] > weight[y])
            return true;
    }
    return false;
}





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

    char type;
    int x , y;

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

        if(type == 'S')
        {
            cin >> x >> y;
            queries.push_back({type , x , y});

            v[x].push_back({y , i});
            v[y].push_back({x , i});
            continue;
        }

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

            qu[x].pb(i);
            continue;
        }

        cin >> x >> y;
        queries.push_back({type , x , y});
    }

    dfs_sort(1 , 1);
    dfs_bin(1 , -1);
    calc();

    //control

    decompose(1 , -1);

    //control

    for(int i = 1; i <= n + q - 1; i++)
        ans[i]++;

    for(int i = 1; i <= n + q - 1; i++)
        if(queries[i].type == 'C')
            cout << ans[i] << endl;
        else
            if(queries[i].type == 'Q')
                cout << (answer(queries[i].x , queries[i].y , i)? "yes" : "no") << endl;

}







int main()
{

    /**#ifdef ONLINE_JUDGE /// promeni
        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_solve();


    return 0;
}

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 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