Submission #848740

#	Time	Username	Problem	Language	Result	Execution time	Memory
848740		danikoynov	Jail (JOI22_jail)	C++14	72 / 100	2077 ms	1048576 KiB

jail

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 2e5 + 10;

int n, m, s[maxn], t[maxn], parent[maxn];
vector < int > adj[maxn], children[maxn];
void input()
{
    cin >> n;
    for (int i = 1; i < n; i ++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    cin >> m;
    for (int i = 1; i <= m; i ++)
    {
        cin >> s[i] >> t[i];
    }

}

int tin[maxn], tout[maxn], occ[2 * maxn], depth[maxn], timer;
int sub[maxn], heavy[maxn];
void euler(int v = 1, int p = -1)
{
    tin[v] = ++ timer;
    occ[timer] = v;
    sub[v] = 1;
    heavy[v] = -1;
    parent[v] = p;
    for (int u : adj[v])
    {
        if (u == p)
            continue;
        children[v].push_back(u);
        depth[u] = depth[v] + 1;
        euler(u, v);
        if (heavy[v] == -1 || sub[u] > sub[heavy[v]])
            heavy[v] = u;
        sub[v] += sub[u];
        occ[++ timer] = v;
    }
    tout[v] = timer;
}

const int maxlog = 20;
int dp[maxlog][maxn * 2], lg[2 * maxn];

void build_sparse_table()
{
    for (int i = 1; i <= timer; i ++)
    {
        dp[0][i] = occ[i];
        lg[i] = lg[i / 2] + 1;
    }

    for (int j = 1; j < lg[timer]; j ++)
    {
        for (int i = 1; i <= timer - (1 << j) + 1; i ++)
        {
            dp[j][i] = dp[j - 1][i + (1 << (j - 1))];
            if (depth[dp[j - 1][i]] < depth[dp[j][i]])
                dp[j][i] = dp[j - 1][i];
        }
    }
}

int get_lca(int v, int u)
{
    int l = tin[v], r = tin[u];
    if (l > r)
        swap(l, r);
    int len = lg[r - l + 1] - 1;
    int lca = dp[len][r - (1 << len) + 1];
    if (depth[dp[len][l]] < depth[lca])
        lca = dp[len][l];
    return lca;
}

vector < int > graph[10 * maxn];
bool is_cycle;

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

bool on_path(int v, int u, int w)
{

    int lca = get_lca(v, u);
    if (in_subtree(lca, w) && in_subtree(w, v))
        return true;
    if (in_subtree(lca, w) && in_subtree(w, u))
        return true;
    return false;
}

void check_prisoners(int i, int j)
{
    /**if (on_path(s[i], t[i], s[j]) && on_path(s[i], t[i], t[j]))
    {
        is_cycle = true;
        return;
    }*/

    if (on_path(s[i], t[i], s[j]))
    {
        graph[i].push_back(j);
        return;
    }

    if (on_path(s[i], t[i], t[j]))
    {
        graph[j].push_back(i);
        return;
    }
}

vector < pair < int, int > > link[maxn];
set < pair < int, int > > loc_set[maxn];

bool cmp(pair < int, int > di, pair < int, int > dj)
{
    int i = di.second, j = dj.second;
    int d1 = depth[s[i]] + depth[t[i]] - 2 * depth[get_lca(s[i], t[i])];
    int d2 = depth[s[j]] + depth[t[j]] - 2 * depth[get_lca(s[j], t[j])];
    return d1 > d2;
}

bool check_range(int idx, int left, int right)
{
    pair < int, int > cur = {left, -1};
    set < pair < int, int > > :: iterator it = loc_set[idx].lower_bound(cur);
    if (it == loc_set[idx].end())
        return false;
    if (it -> first <= right)
        return true;
    return false;
}

int find_child(int v, int u)
{
    int lf = 0, rf = (int)(children[v].size()) - 1;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (tout[children[v][mf]] < tin[u])
            lf = mf + 1;
        else
            rf = mf - 1;
    }
    return children[v][lf];

}
void dfs(int v, int p)
{

    for (int u : adj[v])
    {
        if (u == p)
            continue;
        dfs(u, v);
        if (loc_set[u].size() > loc_set[v].size())
            swap(loc_set[u], loc_set[v]);

        for (pair < int, int > cur : loc_set[u])
        {
            pair < int, int > par = {tin[s[cur.second]], cur.second};
            if (tin[s[cur.second]] == cur.first)
                par.first = tin[t[cur.second]];
            if (loc_set[v].find(par) != loc_set[v].end())
                loc_set[v].erase(par);
            else
                loc_set[v].insert(cur);
        }
    }

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

    for (pair < int, int > cur : link[v])
    {
        pair < int, int > par = {tin[s[cur.second]], cur.second};
        if (tin[s[cur.second]] == cur.first)
            par.first = tin[t[cur.second]];
        ///cout << "here " << cur.first << " " << cur.second << " " << par.first << " " << par.second << " " << tin[s[cur.second]] << endl;
        if (loc_set[v].find(par) != loc_set[v].end())
        {
            loc_set[v].erase(par);
            continue;
        }
        int idx = cur.second, u = s[idx];
        if (u == v)
            u = t[idx];

        if (!in_subtree(u, v))
        {
            if (check_range(v, tin[u], tout[u]))
                is_cycle = true;
        }
        else
        {
            int child = find_child(u, v);
            ///cout << "HERE " << child << " " << u << endl;
            if (check_range(v, 1, tin[child] - 1) || check_range(v, tout[child] + 1, timer))
            {
                ///cout << "FOUND CYCLE " << v << " " << u << " " << child << endl;
                is_cycle = true;
            }
        }
        loc_set[v].insert(cur);
    }
    /**cout << v << " : " << p << endl;
    for (pair < int, int > cur : loc_set[v])
        cout << cur.first << " " << cur.second << endl;
    cout << "cycle " << is_cycle << endl;
        cout << "-------------" << endl;*/
}


struct chain
{
    int top, left, right;

} ch[maxn];

int ord[maxn], ch_idx[maxn], ch_cnt, to, ch_pos[maxn];


void hld(int v)
{
    ch_idx[v] = ch_cnt;
    ord[++ to] = v;
    ch[ch_idx[v]].right = to;
    ch_pos[v] = to;
    if (heavy[v] != -1)
        hld(heavy[v]);

    for (int u : children[v])
    {
        if (u == heavy[v])
            continue;

        ch_cnt ++;
        ch[ch_cnt].top = v;
        ch[ch_cnt].left = to + 1;
        ch[ch_cnt].right = to;
        hld(u);
    }
}

vector < int > ver_start[maxn], ver_end[maxn]; /// might be replaced
void add_edge(int v, int u)
{
    graph[v].push_back(u);
    ///cout << "edge " << v << " " << u << endl;
}
void build_forward_tree(int root, int left, int right)
{
    ///cout << root + m << " : " << left << " " << right << endl;
    if (left == right)
    {
        for (int v : ver_start[left])
            add_edge(root + m, v);
        ///graph[root + m].push_back(v);
        return;
    }

    int mid = (left + right) / 2;
    add_edge(root + m, root * 2 + m);
    add_edge(root + m, root * 2 + 1 + m);
    ///graph[root + m].push_back(root * 2 + m);
    ///graph[root + m].push_back(root * 2  + 1 + m);

    build_forward_tree(root * 2, left, mid);
    build_forward_tree(root * 2 + 1, mid + 1, right);
}

vector < int > bkt[maxn * 4];
void build_backward_tree(int root, int left, int right)
{
    bkt[root].clear();
    if (left == right)
    {
        for (int v : ver_end[left])
        {
            bkt[root].push_back(v);
            add_edge(v, root + m + 4 * n);
            ///graph[v].push_back(root + m + 4 * n);
            ///cout << v << " here " << left << endl;
        }
        return;
    }

    int mid = (left + right) / 2;
    ///add_edge(root * 2 + m + 4 * n, root + m + 4 * n);
    ///add_edge(root * 2 + 1 + m + 4 * n, root + m + 4 * n);

    ///graph[root * 2 + m + 4 * n].push_back(root + m + 4 * n);
    ///graph[root * 2  + 1 + m + 4 * n].push_back(root + m + 4 * n);

    build_backward_tree(root * 2, left, mid);
    build_backward_tree(root * 2 + 1, mid + 1, right);

    for (int v : bkt[root * 2])
        bkt[root].push_back(v);
    for (int v : bkt[root * 2 + 1])
        bkt[root].push_back(v);
    for (int v : bkt[root])
        add_edge(v, root + m + 4 * n);

}

void add_forward(int root, int left, int right, int qleft, int qright, int val)
{
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        add_edge(val, root + m);
        ///graph[val].push_back(root + m);
        return;
    }

    int mid = (left + right) / 2;
    add_forward(root * 2, left, mid, qleft, qright, val);
    add_forward(root * 2 + 1, mid + 1, right, qleft, qright, val);
}

void add_backward(int root, int left, int right, int qleft, int qright, int val)
{
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        for (int cur : bkt[root])
            add_edge(cur, val);
        ///add_edge(root + m + 4 * n, val);

        return;
    }

    int mid = (left + right) / 2;
    add_backward(root * 2, left, mid, qleft, qright, val);
    add_backward(root * 2 + 1, mid + 1, right, qleft, qright, val);
}

void add_path_forward(int v, int lca, int idx)
{

    while(ch_idx[v] != ch_idx[lca])
    {

        add_forward(1, 1, n, ch[ch_idx[v]].left, ch_pos[v], idx);
        ///add_backward(1, 1, n, ch[ch_idx[v]].left, ch_pos[v], idx);
        v = ch[ch_idx[v]].top;
    }
    ///cout << "idx " << idx << " " << ch_pos[lca] << " " << ch_pos[v] << endl;

    add_forward(1, 1, n, ch_pos[lca], ch_pos[v], idx);
    ///add_backward(1, 1, n, ch_pos[lca], ch_pos[v], idx);
}

void add_path_backward(int v, int lca, int idx)
{

    while(ch_idx[v] != ch_idx[lca])
    {

        ///add_forward(1, 1, n, ch[ch_idx[v]].left, ch_pos[v], idx);
        add_backward(1, 1, n, ch[ch_idx[v]].left, ch_pos[v], idx);
        v = ch[ch_idx[v]].top;
    }
    ///cout << "idx " << idx << " " << ch_pos[lca] << " " << ch_pos[v] << endl;

    ///add_forward(1, 1, n, ch_pos[lca], ch_pos[v], idx);
    add_backward(1, 1, n, ch_pos[lca], ch_pos[v], idx);
}
void build_graph()
{


    for (int i = 1; i <= m; i ++)
    {
        link[s[i]].push_back({tin[t[i]], i});
        link[t[i]].push_back({tin[s[i]], i});

    }

    dfs(1, -1);

    ch_cnt = 0;
    to = 0;
    ch[++ ch_cnt].top = 0;
    ch[ch_cnt].left = 1;
    ch[ch_cnt].right = 0;
    hld(1);
    /**for (int i = 1; i <= n; i ++)
        cout << ch_pos[i] << " ";
    cout << endl;*/
    for (int i = 1; i <= m; i ++)
    {
                ver_start[ch_pos[s[i]]].push_back(i);
        ver_end[ch_pos[t[i]]].push_back(i);
    }
    build_backward_tree(1, 1, n);
    build_forward_tree(1, 1, n);

    for (int i = 1; i <= m; i ++)
    {
        int lca = get_lca(s[i], t[i]);

        if (depth[s[i]] + depth[t[i]] - 2 * depth[lca] != 1)
        {

            int v = s[i], u = t[i];
            if (lca != v && lca != u)
            {
                v = parent[v];
                u = parent[u];
            }
            else if (lca == v)
            {
                v = find_child(v, u);
                u = parent[u];
            }
            else if (lca == u)
            {
                u = find_child(u, v);
                v = parent[v];

            }
            lca = get_lca(v, u);
            ///cout << "path " << v << " : " << u << endl;
            add_path_forward(v, lca, i);
            add_path_forward(u, lca, i);
            add_path_backward(v, lca, i);
            add_path_backward(u, lca, i);
        }

        for (pair < int, int > cur : link[s[i]])
        {
            if (i != cur.second)
                check_prisoners(i, cur.second);
        }

        for (pair < int, int > cur : link[t[i]])
        {
            if (i != cur.second)
                check_prisoners(i, cur.second);
        }



    }
    /**for (int i = 1; i <= m; i ++)
    {
        for (int j = 1; j <= m; j ++)
        {
            if (i != j)
                check_prisoners(i, j);
        }
    }*/
}

int used[maxn];

void check_dag(int v)
{
    used[v] = 1;
    for (int u : graph[v])
    {
        if (used[u] == 2)
            continue;
        ///cout << v << " : " << u << endl;
        if (used[u] == 1)
            is_cycle = 1;
        else
        {
            check_dag(u);
        }
    }
    used[v] = 2;
}

void check_graph()
{
    for (int i = 1; i <= m + 8 * n; i ++)
    {
        if (!used[i])
            check_dag(i);
    }

    if (is_cycle)
        cout << "No" << endl;
    else
        cout << "Yes" << endl;
}

void clear_data()
{
    is_cycle = false;
    for (int i = 1; i <= m + 8 * n; i ++)
    {
        bkt[i].clear();

        graph[i].clear(), used[i] = 0;
    }

    for (int i = 1; i <= ch_cnt; i ++)
    {
        ch[i].top = ch[i].left = ch[i].right = 0;
    }

    for (int i = 1; i <= n; i ++)
    {
        ch_pos[i] = 0;
        ch_idx[i]=  0;
        ord[i] = 0;
    }
    ch_cnt = 0;
    to = 0;
    for (int i = 0; i <= n; i ++)
    {
        tin[i] = 0;
        tout[i] = 0;
        adj[i].clear();
        link[i].clear();
        ver_start[i].clear();
        ver_end[i].clear();
        children[i].clear();
        loc_set[i].clear();
    }


    timer = 0;
}

int test_num;
void solve()
{
    test_num ++;
    /**if (test_num <= 6)
    {
        cout << "SKIPPED" << endl;
        return;
    }*/
    input();
    euler();
    build_sparse_table();
    build_graph();
    check_graph();
    clear_data();

}

int main()
{
    speed();
    //freopen("test.txt", "r", stdin);
    int q;
    cin >> q;
    while(q --)
        solve();
    return 0;
}
/**
1
7
1 2
2 3
3 4
4 5
3 6
6 7
2
4 1
5 7

1
4
1 2
2 3
3 4
2
1 3
2 4


1
5
1 2
1 3
2 4
2 5
1
4 5

*/

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 0 / 23