Submission #738317

# Submission time Handle Problem Language Result Execution time Memory
738317 2023-05-08T12:51:40 Z pls33 Inside information (BOI21_servers) C++17
0 / 100
22 ms 3284 KB
#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);
    }
}

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

    p32 ans = {v, 0};
    for (int bit = 31 - __builtin_clz(k); bit >= 0; bit--)
    {
        if (!(k & (1 << bit)))
        {
            continue;
        }

        if (anc[ans.first][bit].first == -1)
        {
            return {-1, -1};
        }

        ans = anc[ans.first][bit];
    }

    return ans;
}

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

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

    return a;
    for (int bit = (int)anc[0].size() - 1; bit >= 0; bit--)
    {
        if (anc[a][bit] != anc[b][bit])
        {
            tie(a, val_a) = anc[a][bit];
            tie(b, val_b) = anc[b][bit];
        }
    }

    if (a > b)
    {
        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(31 - __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' || type == 'C')
        {
            i++;
            continue;
        }

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

        int lca = find_lca(a, b, depth, anc);

        if (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

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:164:21: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
  164 |     for (int i = 0; auto &[type, a, b] : event)
      |                     ^~~~
servers.cpp:205:21: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
  205 |     for (int i = 0; auto &[type, a, b] : event)
      |                     ^~~~
# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 2132 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 2132 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 2132 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 2132 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 3284 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 3284 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 2104 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 2104 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 3284 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 3284 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 2100 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 2100 KB Output isn't correct
2 Halted 0 ms 0 KB -