Submission #738334

#	Time	Username	Problem	Language	Result	Execution time	Memory
738334		pls33	Inside information (BOI21_servers)	C++17	0 / 100	28 ms	2128 KiB

servers

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#pragma region dalykai
template <typename F>
void _debug(F f)
{
    f();
}

#ifndef _AAAAAAAAA
#define debug(x)
#else
#define debug(x) _debug(x)
#endif
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
using f80 = long double;
#pragma endregion

struct event_t
{
    char type; // s, q, c (kol kas nemoku c)
    int a, b;
};

void dfs(int v, int p, int val, vp32 &dp, vvp32 &adj)
{
    for (auto &[next, index] : adj[v])
    {
        if (next == p)
        {
            continue;
        }

        dp[next].first = (val > index) ? dp[v].first + 1 : 1;
        dp[next].second = (val < index) ? dp[v].second + 1 : 1;

        dfs(next, v, index, dp, adj);
    }
}

void find_lift(int v, int p, vi32 &depth, vvp32 &anc, vvp32 &adj)
{
    for (auto &[next, index] : adj[v])
    {
        if (next == p)
        {
            continue;
        }
        depth[next] = depth[v] + 1;
        anc[next][0] = {v, index};

        find_lift(next, v, depth, anc, adj);
    }
}

int find_ancestor(int v, int k, vvp32 &anc)
{
    if (!k)
    {
        return v;
    }

    if (k + 1 > (int)anc.size())
    {
        return -1;
    }

    for (int i = 0; i <= 31 - __builtin_clz(k); i++)
    {
        if (!(k & (1 << i)))
        {
            continue;
        }

        if (anc[v][i].first == -1)
        {
            continue;
        }

        v = anc[v][i].first;
    }

    return v;
}

int find_lca(int a, int b, vi32 &depth, vvp32 &anc)
{
    if (depth[a] > depth[b])
    {
        a = find_ancestor(a, depth[a] - depth[b], anc);
    }
    else
    {
        b = find_ancestor(b, depth[b] - depth[a], anc);
    }

    if (a == -1)
    {
        return -1;
    }

    if (a == b)
    {
        return a;
    }

    assert(depth[a] == depth[b]);
    for (int bit = (int)anc[0].size() - 1; bit >= 0; bit--)
    {
        if (anc[a][bit].first != anc[b][bit].first && anc[a][bit].first != -1)
        {
            a = anc[a][bit].first;
            b = anc[b][bit].first;
        }
    }

    if (anc[a][0].second > anc[b][0].second)
    {
        return -1;
    }

    return anc[a][0].first;
}

int main()
{
#ifndef _AAAAAAAAA
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#else
    freopen("servers.in", "r", stdin);
#ifndef __linux__
    atexit([]()
           {
        freopen("con", "r", stdin);
        system("pause"); });
#endif
#endif

    int n, query;
    cin >> n >> query;

    vector<event_t> event(n - 1 + query);

    vvp32 adj(n);
    for (int i = 0; auto &[type, a, b] : event)
    {
        cin >> type >> a;
        if (type != 'C')
        {
            cin >> b;
        }

        a--;
        b--;

        if (type == 'S')
        {
            adj[a].emplace_back(b, i);
            adj[b].emplace_back(a, i);
        }

        i++;
    }

    vp32 dp(n);
    dfs(0, -1, INT_MAX, dp, adj);

    vi32 depth(n);
    vvp32 anc(n, vp32(32 - __builtin_clz(n), {-1, -1}));

    find_lift(0, -1, depth, anc, adj);
    anc[0][0] = {-1, INT_MAX};

    for (int level = 1; level < (int)anc[0].size(); level++)
    {
        for (int i = 0; i < n; i++)
        {
            int a = anc[i][level - 1].first;
            if (a == -1)
            {
                continue;
            }
            anc[i][level] = anc[a][level - 1];
        }
    }

    for (int i = 0; auto &[type, a, b] : event)
    {
        if (type == 'S')
        {
            i++;
            continue;
        }

        if (type == 'C')
        {
            cout << "0\n";
            i++;
            continue;
        }

        if (a == b)
        {
            cout << "yes\n";
            i++;
            continue;
        }

        // dabar a - duomenu id, b - virsune
        swap(a, b);

        int lca = find_lca(a, b, depth, anc);
        if (lca == -1 || anc[b][0].second > i)
        {
            cout << "no\n";
            i++;
            continue;
        }

        if (depth[b] - depth[lca] > dp[b].second || depth[a] - depth[lca] > dp[a].first)
        {
            cout << "no\n";
            i++;
            continue;
        }

        cout << "yes\n";

        i++;
    }

    return 0;
}

Compilation message (stderr)

servers.cpp:8: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    8 | #pragma region dalykai
      | 
servers.cpp:43: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   43 | #pragma endregion
      | 
servers.cpp: In function 'int main()':
servers.cpp:172:21: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
  172 |     for (int i = 0; auto &[type, a, b] : event)
      |                     ^~~~
servers.cpp:214:21: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
  214 |     for (int i = 0; auto &[type, a, b] : event)
      |                     ^~~~

• 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