Submission #669278

#	Time	Username	Problem	Language	Result	Execution time	Memory
669278		fatemetmhr	Jail (JOI22_jail)	C++17	100 / 100	1794 ms	434708 KiB

jail

// ~ Be Name Khoda ~

#include<bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  2e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const int lg    =  18;
const ll  inf   =  1e18;

int mark[maxn5 * lg * 2], s[maxn5], t[maxn5], h[maxn5];
int par[lg][maxn5], newnode = 0, in[lg][maxn5], out[lg][maxn5];
vector <int> adj[maxn5], ed[maxn5 * lg * 2];
bool cy = false;


void dfs_lca(int v){
    if(!out[0][v])
        out[0][v] = newnode++;
    if(!in[0][v])
        in[0][v] = newnode++;
    for(int i = 1; i < lg && par[i - 1][v] != -1; i++){
        par[i][v] = par[i - 1][par[i - 1][v]];
        out[i][v] = newnode++;
        in[i][v] = newnode++;
        ed[out[i][v]].pb(out[i - 1][v]);
        ed[out[i][v]].pb(out[i - 1][par[i - 1][v]]);
        ed[in[i - 1][v]].pb(in[i][v]);
        ed[in[i - 1][par[i - 1][v]]].pb(in[i][v]);
    }
    for(auto u : adj[v]) if(u != par[0][v]){
        par[0][u] = v;
        h[u] = h[v] + 1;
        dfs_lca(u);
    }
}

void dfs(int v){
    mark[v] = 1;
    for(auto u : ed[v]){
        if(mark[u] == 0)
            dfs(u);
        else if(mark[u] == 1)
            cy = true;
    }
    mark[v] = 2;
}

inline int lca(int a, int b){
    if(h[a] < h[b])
        swap(a, b);
    int d = h[a] - h[b];
    for(int i = 0; i < lg; i++) if((d >> i)&1)
        a = par[i][a];
    if(a == b)
        return a;
    for(int i = lg - 1; i >= 0; i--) if(par[i][a] != par[i][b]){
        a = par[i][a];
        b = par[i][b];
    }
    return par[0][a];
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
 
    int tt; cin >> tt;
    while(tt--){
        int n; cin >> n;
        for(int i = 0; i < n; i++){
            adj[i].clear(); 
            for(int j = 0; j < lg; j++){
                par[j][i] = -1;
                in[j][i] = out[j][i] = 0;
            }
        }
        for(int i = 0; i < n - 1; i++){
            int a, b; cin >> a >> b;
            a--; b--;
            adj[a].pb(b);
            adj[b].pb(a);
        }
        int m; cin >> m;
        newnode = m;
        for(int i = 0; i < m; i++){
            cin >> s[i] >> t[i];
            s[i]--; t[i]--;
            if(!in[0][s[i]])
                in[0][s[i]] = newnode++;
            if(!out[0][t[i]])
                out[0][t[i]] = newnode++;
            ed[i].pb(in[0][s[i]]);
            ed[out[0][t[i]]].pb(i);
        }
        h[0] = 0;
        dfs_lca(0);
        for(int i = 0; i < m; i++){
            int v = s[i], u = t[i];
            if(v == u)
                continue;
            ed[i].pb(out[0][v]);
            ed[in[0][u]].pb(i);
            if(h[v] < h[u])
                swap(u, v);
            int c = lca(u, v);
            bool re = true;
            if(c == u){
                re = false;
                v = par[0][v];
            }
            else{
                u = par[0][u];
                v = par[0][v];
            }
            int d = h[v] - h[u];
            for(int j = 0; j < lg; j++) if((d >> j)&1){
                ed[i].pb(out[j][v]);
                ed[in[j][v]].pb(i);
                v = par[j][v];
            }
            if(u == v){
                if(re){
                    ed[i].pb(out[0][v]);
                    ed[in[0][v]].pb(i);
                }
                continue;
            }
            for(int j = lg - 1; j >= 0; j--) if(par[j][v] != par[j][u]){
                ed[i].pb(out[j][v]);
                ed[i].pb(out[j][u]);
                ed[in[j][v]].pb(i);
                ed[in[j][u]].pb(i);
                v = par[j][v];
                u = par[j][u];
            }
            ed[i].pb(out[0][v]);
            ed[i].pb(out[0][u]);
            ed[i].pb(out[0][par[0][v]]);
            ed[in[0][v]].pb(i);
            ed[in[0][u]].pb(i);
            ed[in[0][par[0][v]]].pb(i);
        }
        cy = false;
        for(int i = 0; i < newnode; i++) if(!mark[i])
            dfs(i);
        cout << (cy ? "No\n" : "Yes\n");
        for(int i = 0; i < newnode; i++){
            ed[i].clear();
            mark[i] = 0;
        }
    }
}

/*
Why so fast...? 
Hold on...
Hold your breath...
Need anything else?

Nein, Kein Problem...
Das Leben war schon immer so grausam :)
*/

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