oj.uz

답안 #848714

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
848714 2023-09-13T10:59:34 Z danikoynov Jail (JOI22_jail) C++14
5 / 100
 684 ms 239296 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);
    }


    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 (s[i] != lca)
            add_path_forward(parent[s[i]], lca, i);
        if (s[i] != lca)
        {
            add_path_forward(t[i], lca, i);
        }
        else
        {
            add_path_forward(t[i], find_child(lca, t[i]), i);
        }

        if (lca != t[i])
        {
            add_path_backward(s[i], lca, i);
        }
        else
        {
            add_path_backward(s[i], find_child(lca, s[i]), i);
        }
        if (t[i] != lca)
            add_path_backward(parent[t[i]], lca, i);
    }
    /**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();
    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
2
1 2
1
1 2

*/

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 117344 KB Output is correct
2 Correct 25 ms 117336 KB Output is correct
3 Correct 23 ms 113240 KB Output is correct
4 Correct 36 ms 123992 KB Output is correct
5 Correct 47 ms 124248 KB Output is correct
6 Correct 25 ms 123480 KB Output is correct
7 Correct 25 ms 123480 KB Output is correct
8 Correct 26 ms 123728 KB Output is correct
9 Correct 70 ms 135764 KB Output is correct
10 Correct 88 ms 165712 KB Output is correct
11 Correct 31 ms 119516 KB Output is correct
12 Correct 69 ms 124400 KB Output is correct
13 Correct 196 ms 194404 KB Output is correct
14 Correct 195 ms 194508 KB Output is correct
15 Correct 370 ms 199372 KB Output is correct
16 Correct 684 ms 239296 KB Output is correct
17 Correct 229 ms 205488 KB Output is correct
18 Correct 254 ms 217456 KB Output is correct
19 Correct 220 ms 202412 KB Output is correct
20 Correct 209 ms 202212 KB Output is correct
21 Correct 267 ms 205356 KB Output is correct
22 Correct 180 ms 195012 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 117336 KB Output is correct
2 Correct 22 ms 113240 KB Output is correct
3 Correct 24 ms 123480 KB Output is correct
4 Incorrect 25 ms 123480 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 117336 KB Output is correct
2 Correct 22 ms 113240 KB Output is correct
3 Correct 24 ms 123480 KB Output is correct
4 Incorrect 25 ms 123480 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 117336 KB Output is correct
2 Correct 22 ms 113240 KB Output is correct
3 Correct 24 ms 123480 KB Output is correct
4 Incorrect 25 ms 123480 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 117336 KB Output is correct
2 Correct 22 ms 113240 KB Output is correct
3 Correct 24 ms 123480 KB Output is correct
4 Incorrect 25 ms 123480 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 117328 KB Output is correct
2 Correct 23 ms 117336 KB Output is correct
3 Correct 23 ms 117420 KB Output is correct
4 Correct 23 ms 113240 KB Output is correct
5 Correct 30 ms 119636 KB Output is correct
6 Correct 24 ms 123484 KB Output is correct
7 Incorrect 24 ms 123484 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 117344 KB Output is correct
2 Correct 25 ms 117336 KB Output is correct
3 Correct 23 ms 113240 KB Output is correct
4 Correct 36 ms 123992 KB Output is correct
5 Correct 47 ms 124248 KB Output is correct
6 Correct 25 ms 123480 KB Output is correct
7 Correct 25 ms 123480 KB Output is correct
8 Correct 26 ms 123728 KB Output is correct
9 Correct 70 ms 135764 KB Output is correct
10 Correct 88 ms 165712 KB Output is correct
11 Correct 31 ms 119516 KB Output is correct
12 Correct 69 ms 124400 KB Output is correct
13 Correct 196 ms 194404 KB Output is correct
14 Correct 195 ms 194508 KB Output is correct
15 Correct 370 ms 199372 KB Output is correct
16 Correct 684 ms 239296 KB Output is correct
17 Correct 229 ms 205488 KB Output is correct
18 Correct 254 ms 217456 KB Output is correct
19 Correct 220 ms 202412 KB Output is correct
20 Correct 209 ms 202212 KB Output is correct
21 Correct 267 ms 205356 KB Output is correct
22 Correct 180 ms 195012 KB Output is correct
23 Correct 25 ms 117336 KB Output is correct
24 Correct 22 ms 113240 KB Output is correct
25 Correct 24 ms 123480 KB Output is correct
26 Incorrect 25 ms 123480 KB Output isn't correct
27 Halted 0 ms 0 KB -