Submission #551443

#	Time	Username	Problem	Language	Result	Execution time	Memory
551443		doowey	Jail (JOI22_jail)	C++14	100 / 100	2231 ms	377044 KiB

jail

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 123456;
const int LOG = 18;
vector<int> T[N];

int par[N];
int go[LOG][N];
int S[N], E[N];
int ss[N], ee[N];
int tin[N];
int tout[N];
int dep[N];
int ti;

void dfs(int u, int pp){
    ti ++ ;
    tin[u] = ti;
    par[u] = pp;
    go[0][u] = pp;
    for(int i = 1; i < LOG; i ++ ){
        go[i][u]=go[i-1][go[i-1][u]];
    }
    for(auto x : T[u]){
        if(x == pp) continue;
        dep[x] = dep[u] + 1;
        dfs(x, u);

    }
    tout[u] = ti;
}

bool is_par(int u, int v){
    if(tin[u] <= tin[v] && tout[u] >= tout[v]) return true;
    return false;
}

int lca(int u, int v){
    if(is_par(u, v)) return u;
    for(int lg = LOG - 1; lg >= 0 ; lg -- ){
        if(!is_par(go[lg][u], v)) u = go[lg][u];
    }
    return go[0][u];
}

const int M = 40 * N;
vector<int> G[M];
int vis[M];

int n, m;

int get_id(int node, int v){
    return m + n * v + node;
}

void add_edge(int u, int v){
    G[u].push_back(v);
}

bool cycle;

void dfs1(int u){
    if(vis[u] == 1){
        cycle = true;
        return;
    }
    if(vis[u] == 2){
        return;
    }
    //convert(u);
    //cout << u << "!!\n";
    vis[u] = 1;
    for(auto x : G[u]){
        dfs1(x);
    }
    vis[u] = 2;
}

void solve(){
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        T[i].clear();
        G[i].clear();
        ss[i] = ee[i] = -1;
    }
    for(int j = 1; j <= 40 * n; j ++){
        G[j].clear();
        vis[j] = 0;
    }
    int u, v;
    for(int i = 1; i < n; i ++ ){
        cin >> u >> v;
        T[u].push_back(v);
        T[v].push_back(u);
    }
    ti = 0;
    dep[1] = 0;
    dfs(1, 1);
    cin >> m;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j < LOG; j ++ ){
            add_edge(get_id(i, j - 1), get_id(i, j));
            add_edge(get_id(go[j - 1][i], j - 1), get_id(i, j));
            // ------------
            add_edge(get_id(i, LOG + j), get_id(i, LOG + j - 1));
            add_edge(get_id(i, LOG + j), get_id(go[j - 1][i], LOG + j - 1));
        }
    }
    int lc;
    int pa;
    int nex;
    int dd;
    for(int i = 1; i <= m ; i ++ ){
        cin >> S[i] >> E[i];

        ss[S[i]] = i;
        ee[E[i]] = i;

        lc = lca(S[i], E[i]);
        add_edge(i, get_id(S[i], 0));
        if(S[i] != 1){
            pa = go[0][S[i]];
            dd = dep[pa] - dep[lc] + 1;
            for(int lg = LOG - 1; lg >= 0 ; lg -- ){
                if((dd & (1 << lg))){
                    add_edge(get_id(pa, lg), i);
                    pa = go[lg][pa];
                }
            }
        }
        pa = E[i];
        dd = dep[pa] - dep[lc] + 1;
        if(S[i] == lc) dd -- ;

        for(int lg = LOG - 1; lg >= 0 ; lg -- ){
            if((dd & (1 << lg))){
                add_edge(get_id(pa, lg), i);
                pa = go[lg][pa];
            }
        }

        // --------------
        add_edge(get_id(E[i], LOG), i);

        pa = S[i];
        dd = dep[pa] - dep[lc] + 1;
        if(E[i] == lc) dd -- ;
        for(int lg = LOG - 1; lg >= 0 ; lg -- ){
            if((dd & (1 << lg))){
                add_edge(i, get_id(pa, LOG + lg));
                pa = go[lg][pa];
            }
        }

        if(E[i] != 1){
            pa = go[0][E[i]];
            dd = dep[pa] - dep[lc] + 1;
            for(int lg = LOG - 1; lg >= 0 ; lg -- ){
                if((dd & (1 << lg))){
                    add_edge(i, get_id(pa, LOG + lg));
                    pa = go[lg][pa];
                }
            }
        }



    }
    //return;
    cycle = false;
    for(int i = 1; i <= 40 * n; i ++ ){
        dfs1(i);
    }
    if(cycle){
        cout << "No\n";
    }
    else{
        cout << "Yes\n";
    }

}

int main(){
    fastIO;
    //freopen("in.txt","r",stdin);
    int tc;
    cin >> tc;
    for(int iq = 1; iq <= tc; iq ++ ){
        solve();
    }
    return 0;
}

Compilation message (stderr)

jail.cpp: In function 'void solve()':
jail.cpp:121:9: warning: unused variable 'nex' [-Wunused-variable]
  121 |     int nex;
      |         ^~~

• 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