Submission #876835

#	Time	Username	Problem	Language	Result	Execution time	Memory
876835		Ice_man	Jail (JOI22_jail)	C++14	0 / 100	29 ms	14684 KiB

jail

#include <iostream>
#include <vector>
#include <cstring>
#include <stack>

#define maxn 120005
#define maxlog 20
#define pb(x) push_back(x)
#define control cout<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops")
#pragma GCC target(avx2)

using namespace std;

int n, m,  q;
vector <int> v[maxn];
int start[maxn], _final[maxn];
vector <int> new_tree[maxn];
int bin_lift[maxn][maxlog];
int pom1[maxn];
int pom2[maxn];
int chain[maxn];

void read()
{
    cin >> n;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < maxlog; j++) bin_lift[i][j] = 0;
    }

    for(int i = 1; i <= n * 12; i++)
    {
        pom1[i] = 0;
        pom2[i] = 0;
        v[i].clear();
        new_tree[i].clear();
    }

    int from, to;
    for(int i = 1; i <= (n - 1); i++)
    {
        cin >> from >> to;

        v[from].pb(to);
        v[to].pb(from);
    }

    cin >> m;

    for(int i = 1; i <= m; i++)
    {
        pom1[i] = 0;
        pom2[i] = 0;
    }

    for(int i = 1; i <= m; i++) cin >> start[i] >> _final[i];

}

int tree[12 * maxn];

void build_seg(int node , int l , int r)
{
    if(l == r)
    {
        tree[l] = node;
        return;
    }

    int mid = (r - l) / 2 + l;

    build_seg(node * 2 , l , mid);
    build_seg(node* 2 + 1 , mid + 1 , r);

    new_tree[node].pb(node * 2);
    new_tree[node].pb(node * 2 + 1);

    new_tree[node * 2 + 4 * n].pb(node + 4 * n);
    new_tree[node * 2 + 1 + 4 * n].pb(node + 4 * n);
}

void _add(int node , int l , int r , int ql , int qr , int val)
{

    if(ql <= l && r <= qr)
    {
        new_tree[node + n * 4].pb(val + n * 8);

        new_tree[node + n * 8].pb(node);

        return;
    }

    if(qr < l || r < ql) return;

    int mid = (r - l) / 2 + l;

    _add(node * 2 , l , mid , ql , qr , val);
    _add(node * 2 + 1 , mid + 1 , r , ql , qr , val);

}


///int bin_lift[maxn][maxlog];
int depth[maxn];
int subtree[maxn];
int help[maxn * 12];

void calc_bin(int node, int parent)
{
    for(int nb : v[node])
    {
        if(nb != parent)
        {

            bin_lift[nb][0] = node;
            for(int i = 1; i < maxlog; i++) bin_lift[nb][i] = bin_lift[bin_lift[nb][i - 1]][i - 1];

            depth[nb] = depth[node] + 1;
            calc_bin(nb, node);

            subtree[node] += subtree[nb];

            if(subtree[v[node][0]] < subtree[nb] || v[node][0] == parent) swap(v[node][0] , nb);

        }
    }

}


int get_lca(int a, int b)
{
    if(depth[a] < depth[b]) swap(a, b);

    ///cout << a << "-" << b << endl;

    int levels = depth[a] - depth[b];
    ///cout << "** " << levels << endl;;
    for(int i = maxlog - 1; i >= 0; i--)
    {
        if(levels >> i & 1)
        {
            ///cout  << ">< "<< (1 << i) << endl;
            a = bin_lift[a][i];
            ///levels -= (1 << i);
            ///cout << (1 << i) << endl;
        }
    }

    ///cout << a << "-" << b << endl;
    if(a == b) return a;

    for(int i = maxlog - 1; i >= 0; i--)
    {
        if(!bin_lift[a][i]) continue;
        if(!bin_lift[b][i]) continue;

        if(bin_lift[a][i] != bin_lift[b][i])
        {
            a = bin_lift[a][i];
            b = bin_lift[b][i];
        }

    }

    return bin_lift[a][0];

}

int heads[maxn];

void add_edges(int node , int from , int to)
{
    bool lamp1 = true;
    bool lamp2 = true;

    while(heads[from] != heads[to])
    {
        ///cout << from << " " << to << endl;
        if(heads[from] == heads[to]) break;

        if(depth[heads[to]] > depth[heads[from]])
        {
            swap(from , to);
            swap(lamp1 , lamp2);
        }

        _add(1 , 1 , n , chain[heads[from]] , chain[from] - lamp1 , node);

        lamp1 = false;
        from = bin_lift[heads[from]][0];
    }


    if(chain[from] > chain[to])
    {
        swap(from , to);
        swap(lamp1 , lamp2);
    }

    _add(1 , 1 , n , chain[from] + lamp1 , chain[to] - lamp2 , node);

}


bool check(int a, int b, int c)
{
    int lca = get_lca(a, b);
    ///int pom = get_lca(lca , c);

    if(get_lca(lca, c) == lca && get_lca(c, a) == c) return true;
    if(get_lca(lca, c) == lca && get_lca(c, b) == c) return true;

    return false;

}

int cur_chain = 0;
///int heads[maxn];

void dfs_hld(int node , int parent , int leader)
{

    cur_chain++;

    chain[node] = cur_chain;
    heads[node] = leader;

    if(v[node][0] != parent) dfs_hld(v[node][0] , node , leader);

    for(int nb : v[node]) if(nb != parent && nb != v[node][0])
    {
        dfs_hld(nb , node , nb);
    }

}



//vector <int> new_tree[maxn];

void solve()
{

    calc_bin(1, 0);

    ///control

    /**for(int a = 1; a <= m; a++)
    {
        for(int b = 1; b <= m; b++)
        {
            if(a == b) continue;
            ///int lca1 = get_lca(start[a], _final[a]);

            if(check(start[a], _final[a], start[b]) == true) new_tree[b].pb(a);
            if(check(start[a], _final[a], _final[b]) == true) new_tree[a].pb(b);

            ///cout << check(start[a] , _final[a] , start[b]) << " " <<  check(start[a] , _final[a] , _final[b]) << endl;

        }
    }*/

    cur_chain = 0;
    ///_time = 0;
    dfs_hld(1 , 0 , 1);

    /**cout << "--------------" << endl;
    for(int i = 1; i <= n; i++) cout << heads[i] << " ";
    cout << endl << "--------------" << endl;*/


    ///control

    build_seg(1 , 1 , n);

    ///cout << "sd;inkmsad" << endl;
    ///control

    for(int i = 1; i <= n * 12; i++) help[i] = 0;

    for(int i = 1; i <= m; i++)
    {
        new_tree[tree[chain[_final[i]]]].pb(8 * n + i);
        new_tree[i + n * 8].pb(n * 4 + tree[chain[start[i]]]);

        help[_final[i]] = i;
        add_edges(i , start[i] , _final[i]);

        ///cout << "passed " << i << endl;

    }


    ///cout << "-----------------" << endl;
    ///control

    for(int i = 1; i <= m; i++) if(help[start[i]])
    {
        new_tree[i + 8 * n].pb(help[start[i]] + 8 * n);
    }

    /**for(int i = 1; i <= n; i++)
    {
       cout << i << ": ";
       for(int nb : new_tree[i]) cout << nb << " ";
       cout << endl;
    }*/

}

stack <int> s;
///int pom1[maxn] , pom2[maxn];
int _time = 0;
int br = 0;
bool ans = true;

void count_ssc(int node, int parent)
{
    s.push(node);
    _time++;

    pom1[node] = _time;
    pom2[node] = _time;

    for(int nb : new_tree[node])
    {
        if(pom2[nb] == -1) continue;
        if(pom2[nb])
        {
            pom1[node] = min(pom1[node], pom1[nb]);
        }
        else
        {
            count_ssc(nb, node);
            pom1[node] = min(pom1[node], pom1[nb]);
        }
    }

    int h;

    if(pom1[node] == pom2[node])
    {
        br++;

        h = 0;

        while(!s.empty() && s.top() != node)
        {
            pom2[s.top()] = -1;

            h += s.top() > 8 * n? 1 : 0;

            s.pop();
        }

        h += node > 8 * n? 1 : 0;

        pom2[node] = -1;
        if(h > 1) ans = false;

        s.pop();
    }


}

int _pom[maxn];

void combine()
{
    cin >> q;
    while(q--)
    {
        br = 0;
        _time = 0;
        ans = true;

        read();

        ///control

        solve();

        ///control

        /**for(int i = 1; i <= n; i++)
        {
            cout << i << ": ";
            for(int power = 0; power < maxlog; power++)
            {
                cout << bin_lift[i][power] << " ";
            }
            cout << endl;
        }*/

        ///cout << "-> " << get_lca(1 , 5) << endl;
        while(s.size()) s.pop();
        for(int i = 1; i <= 12 * n + m; i++) if(!pom2[i]) count_ssc(i, -1);

        if(ans == true) cout << "Yes" << endl;
        else cout << "No" << endl;

    }
}

int main()
{
    /**ios_base::sync_with_stdio(false);
    cin.tie(nullptr);*/

    combine();

    return 0;

}
/**

3
3
1 2
2 3
2
2 1
3 2
7
1 2
2 3
3 4
4 5
5 6
6 7
3
1 3
4 2
2 5
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4
1 5
2 6
3 7
4 8


*/

Compilation message (stderr)

jail.cpp:12:20: warning: '#pragma GCC option' is not a string [-Wpragmas]
   12 | #pragma GCC target(avx2)
      |                    ^~~~

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