oj.uz

Submission #848694

# Submission time Handle Problem Language Result Execution time Memory
848694 2023-09-13T09:57:58 Z danikoynov Jail (JOI22_jail) C++14
5 / 100
 16 ms 43608 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];
vector < int > adj[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;
void euler(int v = 1, int p = -1)
{
    tin[v] = ++ timer;
    occ[timer] = v;
    for (int u : adj[v])
    {
        if (u == p)
            continue;

        depth[u] = depth[v] + 1;
        euler(u, v);
        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[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)(adj[v].size()) - 1;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (tout[adj[v][mf]] < tin[u])
            lf = mf + 1;
        else
            rf = mf - 1;
    }
    return adj[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);
            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;*/
}
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);

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

    for (int i = 1; i <= n; i ++)
    {
        adj[i].clear();
        link[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

*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35160 KB Output is correct
2 Correct 6 ms 35160 KB Output is correct
3 Correct 6 ms 31068 KB Output is correct
4 Incorrect 16 ms 41304 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35160 KB Output is correct
2 Correct 5 ms 31064 KB Output is correct
3 Correct 9 ms 43608 KB Output is correct
4 Correct 8 ms 43352 KB Output is correct
5 Correct 8 ms 43352 KB Output is correct
6 Correct 8 ms 43352 KB Output is correct
7 Correct 8 ms 43356 KB Output is correct
8 Correct 8 ms 43352 KB Output is correct
9 Correct 8 ms 43352 KB Output is correct
10 Correct 8 ms 43352 KB Output is correct
11 Correct 8 ms 43352 KB Output is correct
12 Correct 8 ms 43352 KB Output is correct
13 Correct 7 ms 43352 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35160 KB Output is correct
2 Correct 5 ms 31064 KB Output is correct
3 Correct 9 ms 43608 KB Output is correct
4 Correct 8 ms 43352 KB Output is correct
5 Correct 8 ms 43352 KB Output is correct
6 Correct 8 ms 43352 KB Output is correct
7 Correct 8 ms 43356 KB Output is correct
8 Correct 8 ms 43352 KB Output is correct
9 Correct 8 ms 43352 KB Output is correct
10 Correct 8 ms 43352 KB Output is correct
11 Correct 8 ms 43352 KB Output is correct
12 Correct 8 ms 43352 KB Output is correct
13 Correct 7 ms 43352 KB Output is correct
14 Correct 7 ms 35160 KB Output is correct
15 Correct 7 ms 35160 KB Output is correct
16 Correct 8 ms 43608 KB Output is correct
17 Correct 8 ms 43356 KB Output is correct
18 Correct 8 ms 43352 KB Output is correct
19 Incorrect 6 ms 37208 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35160 KB Output is correct
2 Correct 5 ms 31064 KB Output is correct
3 Correct 9 ms 43608 KB Output is correct
4 Correct 8 ms 43352 KB Output is correct
5 Correct 8 ms 43352 KB Output is correct
6 Correct 8 ms 43352 KB Output is correct
7 Correct 8 ms 43356 KB Output is correct
8 Correct 8 ms 43352 KB Output is correct
9 Correct 8 ms 43352 KB Output is correct
10 Correct 8 ms 43352 KB Output is correct
11 Correct 8 ms 43352 KB Output is correct
12 Correct 8 ms 43352 KB Output is correct
13 Correct 7 ms 43352 KB Output is correct
14 Correct 7 ms 35160 KB Output is correct
15 Correct 7 ms 35160 KB Output is correct
16 Correct 8 ms 43608 KB Output is correct
17 Correct 8 ms 43356 KB Output is correct
18 Correct 8 ms 43352 KB Output is correct
19 Incorrect 6 ms 37208 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35160 KB Output is correct
2 Correct 5 ms 31064 KB Output is correct
3 Correct 9 ms 43608 KB Output is correct
4 Correct 8 ms 43352 KB Output is correct
5 Correct 8 ms 43352 KB Output is correct
6 Correct 8 ms 43352 KB Output is correct
7 Correct 8 ms 43356 KB Output is correct
8 Correct 8 ms 43352 KB Output is correct
9 Correct 8 ms 43352 KB Output is correct
10 Correct 8 ms 43352 KB Output is correct
11 Correct 8 ms 43352 KB Output is correct
12 Correct 8 ms 43352 KB Output is correct
13 Correct 7 ms 43352 KB Output is correct
14 Correct 7 ms 35160 KB Output is correct
15 Correct 7 ms 35160 KB Output is correct
16 Correct 8 ms 43608 KB Output is correct
17 Correct 8 ms 43356 KB Output is correct
18 Correct 8 ms 43352 KB Output is correct
19 Incorrect 6 ms 37208 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35160 KB Output is correct
2 Correct 6 ms 35160 KB Output is correct
3 Correct 7 ms 35160 KB Output is correct
4 Correct 6 ms 31064 KB Output is correct
5 Incorrect 13 ms 39516 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35160 KB Output is correct
2 Correct 6 ms 35160 KB Output is correct
3 Correct 6 ms 31068 KB Output is correct
4 Incorrect 16 ms 41304 KB Output isn't correct
5 Halted 0 ms 0 KB -