답안 #848730

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
848730 2023-09-13T11:55:34 Z danikoynov Jail (JOI22_jail) C++14
5 / 100
867 ms 247788 KB
/**
 ____ ____ ____ ____ ____ ____
||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 << 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)
    {
        add_edge(root + m + 4 * n, val);
        ///graph[root + m + 4 * n].push_back(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});
        ver_start[s[i]].push_back(i);
        ver_end[t[i]].push_back(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);

    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 ++)
        graph[i].clear(), used[i] = 0;

    for (int i = 1; i <= n; i ++)
    {
        adj[i].clear();
        link[i].clear();
        ver_start[i].clear();
        ver_end[i].clear();
        children[i].clear();
        loc_set[i].clear();
    }


    timer = 0;
}

void solve()
{
    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

*/
# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 117592 KB Output is correct
2 Correct 23 ms 117336 KB Output is correct
3 Correct 22 ms 113240 KB Output is correct
4 Correct 35 ms 123480 KB Output is correct
5 Correct 49 ms 123480 KB Output is correct
6 Correct 24 ms 123484 KB Output is correct
7 Correct 29 ms 123732 KB Output is correct
8 Correct 27 ms 123992 KB Output is correct
9 Correct 69 ms 134740 KB Output is correct
10 Correct 94 ms 171796 KB Output is correct
11 Correct 31 ms 119512 KB Output is correct
12 Correct 79 ms 123680 KB Output is correct
13 Correct 208 ms 200708 KB Output is correct
14 Correct 203 ms 200664 KB Output is correct
15 Correct 385 ms 206272 KB Output is correct
16 Correct 867 ms 247788 KB Output is correct
17 Correct 268 ms 212076 KB Output is correct
18 Correct 217 ms 218392 KB Output is correct
19 Correct 239 ms 208552 KB Output is correct
20 Correct 243 ms 208736 KB Output is correct
21 Correct 289 ms 211640 KB Output is correct
22 Correct 159 ms 198456 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 117336 KB Output is correct
2 Correct 22 ms 113240 KB Output is correct
3 Correct 24 ms 123484 KB Output is correct
4 Incorrect 28 ms 123736 KB Output isn't correct
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 117336 KB Output is correct
2 Correct 22 ms 113240 KB Output is correct
3 Correct 24 ms 123484 KB Output is correct
4 Incorrect 28 ms 123736 KB Output isn't correct
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 117336 KB Output is correct
2 Correct 22 ms 113240 KB Output is correct
3 Correct 24 ms 123484 KB Output is correct
4 Incorrect 28 ms 123736 KB Output isn't correct
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 117336 KB Output is correct
2 Correct 22 ms 113240 KB Output is correct
3 Correct 24 ms 123484 KB Output is correct
4 Incorrect 28 ms 123736 KB Output isn't correct
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 117336 KB Output is correct
2 Correct 23 ms 117336 KB Output is correct
3 Correct 23 ms 117336 KB Output is correct
4 Correct 23 ms 113244 KB Output is correct
5 Correct 32 ms 119388 KB Output is correct
6 Correct 24 ms 123480 KB Output is correct
7 Incorrect 25 ms 123484 KB Output isn't correct
8 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 117592 KB Output is correct
2 Correct 23 ms 117336 KB Output is correct
3 Correct 22 ms 113240 KB Output is correct
4 Correct 35 ms 123480 KB Output is correct
5 Correct 49 ms 123480 KB Output is correct
6 Correct 24 ms 123484 KB Output is correct
7 Correct 29 ms 123732 KB Output is correct
8 Correct 27 ms 123992 KB Output is correct
9 Correct 69 ms 134740 KB Output is correct
10 Correct 94 ms 171796 KB Output is correct
11 Correct 31 ms 119512 KB Output is correct
12 Correct 79 ms 123680 KB Output is correct
13 Correct 208 ms 200708 KB Output is correct
14 Correct 203 ms 200664 KB Output is correct
15 Correct 385 ms 206272 KB Output is correct
16 Correct 867 ms 247788 KB Output is correct
17 Correct 268 ms 212076 KB Output is correct
18 Correct 217 ms 218392 KB Output is correct
19 Correct 239 ms 208552 KB Output is correct
20 Correct 243 ms 208736 KB Output is correct
21 Correct 289 ms 211640 KB Output is correct
22 Correct 159 ms 198456 KB Output is correct
23 Correct 23 ms 117336 KB Output is correct
24 Correct 22 ms 113240 KB Output is correct
25 Correct 24 ms 123484 KB Output is correct
26 Incorrect 28 ms 123736 KB Output isn't correct
27 Halted 0 ms 0 KB -