Submission #876462

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
876462	2023-11-21T19:17:23 Z	Ice_man	Jail (JOI22_jail)	C++14	Compilation error	0 ms	0 KB

jail

#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
 
#define maxn 120005
#define maxlog 20
#define pb(x) push_back(x)
 
#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];

bool cmp(int a , int b)
{
    return start[a] < start[b];
}

bool cmp1(int a , int b)
{
    return _final[a] < _final[b];
}

int pomm1[maxn] , pomm2[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; i++)
    {
        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];
    
    if(n > 500)
    {
        for(int i = 1; i <= m; i++) pomm1[i] = pomm2[i] = i;
        sort(pomm1 + 1 , pomm1 + 1 + m , cmp);
        sort(pomm2 + 1 , pomm2 + 1 + m , cmp1);
        
        for(int i = 1; i <= m; i++)
        {
            if(pomm1[i] != pomm2[i])
            {
                cout << "No" << endl;
                return;
            }
        }
        
        cout << "Yes" << endl;
        return;
        
    }
    
    
}  
 
///int bin_lift[maxn][maxlog];
int depth[maxn];
 
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);
        }
    }
 
}
 
 
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];
 
}
 
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;
 
}
 
//vector <int> new_tree[maxn];
 
void solve()
{
 
    calc_bin(1, 0);
 
    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;
 
        }
    }
 
    /**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;
 
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]);
        }
    }
 
    if(pom1[node] == pom2[node])
    {
        br++;
        while(!s.empty() && s.top() != node)
        {
            pom2[s.top()] = -1;
            s.pop();
        }
        pom2[node] = -1;
        s.pop();
    }
 
 
}
 
void combine()
{
    cin >> q;
    while(q--)
    {
        br = 0;
        _time = 0;
 
        read();
        solve();
 
        /**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 <= m; i++) if(!pom2[i]) count_ssc(i, -1);
 
        if(br == m) 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

jail.cpp:11:20: warning: '#pragma GCC option' is not a string [-Wpragmas]
   11 | #pragma GCC target(avx2)
      |                    ^~~~
jail.cpp: In function 'void read()':
jail.cpp:72:9: error: 'sort' was not declared in this scope; did you mean 'qsort'?
   72 |         sort(pomm1 + 1 , pomm1 + 1 + m , cmp);
      |         ^~~~
      |         qsort