Submission #555926

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
555926	2022-05-01T19:57:00 Z	Zhora_004	Inside information (BOI21_servers)	C++17	7.5 / 100	3500 ms	41172 KB

servers

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <string>
#include <sstream>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <stack>
#include <cstdio>
#include <climits>
#include <tuple>
#include <ctime>
#include <cstring>
#include <numeric>
#include <functional>
#include <chrono>
#include <cassert>
#include <bitset>
#include <fstream>
#define sz(a) ((int)((a).size()))
// printf("%.10f\n", ans);
using ll = long long;
using namespace std;
const ll mod = 1e9 + 7;
const int N = 2e5 + 1, inf = 1e9;

struct Query {
    char t;
    int u, v;
};

int n, q, timer;
vector<int> par, cap, tin, tout, head, arr, binc, bdec, depth;
vector<Query> qu;
vector<vector<int>> tree, up;

void dfs(int u, int p)
{
    par[u] = p;
    int id = -1;
    cap[u] = 1;
    for (int i = 0; i < sz(tree[u]); i++)
    {
        int v = tree[u][i];
        if (v == p) id = i;
        else
        {
            dfs(v, u);
            cap[u] += cap[v];
        }
    }
    if (id != -1)
    {
        swap(tree[u][id], tree[u].back());
        tree[u].pop_back();
    }
    for (int i = 1; i < sz(tree[u]); i++)
    {
        int v = tree[u][i];
        if (cap[v] > cap[tree[u][0]]) swap(tree[u][i], tree[u][0]);
    }
}

void hld(int u, int h)
{
    tin[u] = timer++;
    if (u != 0) depth[u] = depth[par[u]] + 1;
    head[u] = h;
    up[u][0] = par[u];
    for (int i = 1; i < 20; i++) up[u][i] = up[up[u][i - 1]][i - 1];
    for (int i = 0; i < sz(tree[u]); i++)
    {
        int v = tree[u][i];
        if (i == 0) hld(v, h);
        else hld(v, v);
    }
    tout[u] = timer;
}

bool ok(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int find_lca(int u, int v)
{
    if (ok(u, v)) return u;
    if (ok(v, u)) return v;
    for (int i = 19; i >= 0; i--) if (!ok(up[u][i], v)) u = up[u][i];
    return up[u][0];
}

int go_up(int u, int k)
{
    for (int i = 19; i >= 0; i--)
    {
        if ((1 << i) <= k)
        {
            k -= (1 << i);
            u = up[u][i];
        }
    }
    return u;
}

bool ok_inc(int l, int r)
{
    return l >= binc[r];
}

bool is_inc(int u, int v)
{
    while (depth[u] >= depth[v])
    {
        int h = head[u];
        if (depth[h] < depth[v]) h = v;
        int l = tin[h], r = tin[u];
        if (!ok_inc(l, r)) return 0;
        if (h == v) break;
        if (arr[tin[par[h]]] < arr[tin[h]]) return 0;
        u = par[h];
    }
    return 1;
}

bool ok_dec(int l, int r)
{
    return l >= bdec[r];
}

bool is_dec(int u, int v)
{
    while (depth[u] >= depth[v])
    {
        int h = head[u];
        if (depth[h] < depth[v]) h = v;
        int l = tin[h], r = tin[u];
        if (!ok_dec(l, r)) return 0;
        if (h == v) break;
        if (arr[tin[par[h]]] > arr[tin[h]]) return 0;
        u = par[h];
    }
    return 1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    par = cap = tin = tout = head = arr = binc = bdec = depth = vector<int>(n);
    qu = vector<Query>(n + q - 1);
    tree = vector<vector<int>>(n);
    up = vector<vector<int>>(n, vector<int>(20));
    for (int i = 0; i < n + q - 1; i++)
    {
        cin >> qu[i].t >> qu[i].u >> qu[i].v;
        qu[i].u--, qu[i].v--;
        if (qu[i].t == 'S')
        {
            tree[qu[i].u].push_back(qu[i].v);
            tree[qu[i].v].push_back(qu[i].u);
        }
    }
    dfs(0, 0);
    hld(0, 0);
    for (int i = 0; i < n + q - 1; i++)
    {
        if (qu[i].t == 'S')
        {
            if (par[qu[i].u] == qu[i].v) swap(qu[i].u, qu[i].v);
            arr[tin[qu[i].v]] = i;
        }
    }
    binc[0] = 0;
    bdec[0] = 0;
    for (int i = 1; i < n; i++)
    {
        if (arr[i] < arr[i - 1]) binc[i] = i;
        else binc[i] = binc[i - 1];
        if (arr[i] > arr[i - 1]) bdec[i] = i;
        else bdec[i] = bdec[i - 1];
    }
    for (int i = 0; i < n + q - 1; i++)
    {
        if (qu[i].t == 'Q')
        {
            int u = qu[i].u, v = qu[i].v;
            if (u == v)
            {
                cout << "yes\n";
                continue;
            }
            int lca = find_lca(u, v);
            if (u == lca)
            {
                int dist = depth[v] - depth[u];
                int k = go_up(v, dist - 1);
                if (arr[tin[k]] < i && is_dec(v, k)) cout << "yes\n";
                else cout << "no\n";
            }
            else if (v == lca)
            {
                int dist = depth[u] - depth[v];
                int k = go_up(u, dist - 1);
                if (arr[tin[u]] < i && is_inc(u, k)) cout << "yes\n";
                else cout << "no\n";
            }
            else
            {
                int dist = depth[v] - depth[lca];
                int v1 = go_up(v, dist - 1);
                dist = depth[u] - depth[lca];
                int u1 = go_up(u, dist - 1);
                if (arr[tin[u]] < i && arr[tin[u1]] > arr[tin[v1]] && is_dec(v, v1) && is_inc(u, u1)) cout << "yes\n";
                else cout << "no\n";
            }
        }
    }

    /*
        3 1
        S 1 3
        S 3 2
        Q 1 2
    */

    return 0;
}

Subtask #1
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	28 ms	2764 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	28 ms	2764 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
2.5 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	2996 KB	Output is correct
2	Correct	149 ms	31848 KB	Output is correct
3	Correct	161 ms	31812 KB	Output is correct

Subtask #4
0 / 2.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	2996 KB	Output is correct
2	Correct	149 ms	31848 KB	Output is correct
3	Correct	161 ms	31812 KB	Output is correct
4	Execution timed out	3560 ms	1748 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	2752 KB	Output is correct
2	Correct	132 ms	41148 KB	Output is correct
3	Correct	137 ms	41172 KB	Output is correct
4	Correct	157 ms	41088 KB	Output is correct

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	2752 KB	Output is correct
2	Correct	132 ms	41148 KB	Output is correct
3	Correct	137 ms	41172 KB	Output is correct
4	Correct	157 ms	41088 KB	Output is correct
5	Execution timed out	3569 ms	1748 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #7
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	29 ms	2892 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	29 ms	2892 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	2788 KB	Output is correct
2	Correct	142 ms	41152 KB	Output is correct
3	Correct	164 ms	41108 KB	Output is correct
4	Correct	158 ms	41108 KB	Output is correct
5	Incorrect	27 ms	2940 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #10
0 / 12.5

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	2788 KB	Output is correct
2	Correct	142 ms	41152 KB	Output is correct
3	Correct	164 ms	41108 KB	Output is correct
4	Correct	158 ms	41108 KB	Output is correct
5	Incorrect	27 ms	2940 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #11
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	28 ms	2776 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #12
0 / 17.5

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	28 ms	2776 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Submission #555926

Compilation message