Submission #1116702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116702		Zero_OP	Jail (JOI22_jail)	C++14	100 / 100	3107 ms	1006552 KiB

jail

#include <bits/stdc++.h>

using namespace std;

#define dbg(x) "[" #x " = " << (x) << "]"

bool cycle_detection(vector<vector<int>>& adj){
    int N = (int)adj.size();
    vector<int> vis(N);

    function<bool(int)> dfs = [&](int u){
        vis[u] = 1;
        for(auto v : adj[u]){
            if(!vis[v]){
                if(dfs(v)) return true;
            } else if(vis[v] == 1){
                return true;
            }
        }
        vis[u] = 2;
        return false;
    };

    for(int i = 0; i < N; ++i){
        if(!vis[i] && dfs(i)) return true;
    }
    return false;
}

struct path_decomposition_tree{
    int N, timerHLD, num;
    vector<int> par, depth, sz, tin, tout, head;
    vector<vector<int>> adj;
    vector<pair<int, int>> edges;

    path_decomposition_tree(int N) :
         timerHLD(0), num(0), N(N), depth(N), sz(N), tin(N, -1), tout(N, -1), par(N), head(N), adj(N), edges() {}

    void add_edge(int u, int v){
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    void dfs_sz(int u){
        sz[u] = 1;
        for(auto& v : adj[u]){
            adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
            depth[v] = depth[u] + 1;
            par[v] = u;
            dfs_sz(v);
            if(sz[adj[u][0]] < sz[v]) swap(adj[u][0], v);
            sz[u] += sz[v];
        }
    }

    void dfs_hld(int u, int hd){
        head[u] = hd;
        tin[u] = timerHLD++;
        for(auto v : adj[u]){
            if(v == adj[u][0]) dfs_hld(v, hd);
            else dfs_hld(v, v);
        }
        tout[u] = timerHLD - 1;
    }

    void build(int N){
        num = 2 * N;
        for(int i = N - 1; i > 0; --i){
            edges.emplace_back(i, i << 1);
            edges.emplace_back(i, i << 1 | 1);
        }
    }

    void preprocess(int rt){
        dfs_sz(rt);
        dfs_hld(rt, rt);
        assert(timerHLD == N);
        build(N);
    }

    int auxiliary_nodes(){ return num; }
    bool in_subtree(int u, int v){ return tin[u] <= tin[v] && tout[v] <= tout[u]; }

    void query_auxiliary_nodes(int l, int r, vector<int>& ans){
        l += N;
        r += N + 1;
        for(; l < r; l >>= 1, r >>= 1){
            if(l & 1) ans.emplace_back(l++);
            if(r & 1) ans.emplace_back(--r);
        }
    }

    vector<int> query(int u, int v){ //ignore u, v
        if(u == v) assert(false);
        vector<int> cur;

        if(tin[u] > tin[v]) swap(u, v);

        if(in_subtree(u, v)){
            v = par[v];
            while(head[u] != head[v]){
                if(depth[head[u]] < depth[head[v]]) swap(u, v);
                query_auxiliary_nodes(tin[head[u]], tin[u], cur);
                u = par[head[u]];
            }

            if(tin[u] > tin[v]) swap(u, v);
            if(tin[u] < tin[v]) query_auxiliary_nodes(tin[u] + 1, tin[v], cur);
            return cur;
        } else{
            u = par[u];
            v = par[v];
        }

        while(head[u] != head[v]){
            if(depth[head[u]] < depth[head[v]]) swap(u, v);
            query_auxiliary_nodes(tin[head[u]], tin[u], cur);
            u = par[head[u]];
        }

        if(tin[u] > tin[v]) swap(u, v);
        query_auxiliary_nodes(tin[u], tin[v], cur);
        return cur;
    }

    int get(int u){
        return tin[u] + N;
    }
};

void testcase(){
    int N;
    cin >> N;

    path_decomposition_tree tr(N);
    for(int i = 1; i < N; ++i){
        int u, v;
        cin >> u >> v;
        --u, --v;
        tr.add_edge(u, v);
    }

    int M;
    cin >> M;

    tr.preprocess(0);
    int offset = tr.auxiliary_nodes();
    int nodes = 2 * offset + M;
    vector<vector<int>> G(nodes);

    for(auto [u, v] : tr.edges){
        G[u].emplace_back(v); //for T
        G[v + offset].emplace_back(u + offset); //for S
    }

    for(int i = 0; i < M; ++i){
        int s, t;
        cin >> s >> t;

        --s, --t;
        int loc = 2 * offset + i;
        vector<int> compress_nodes = tr.query(s, t); //auxiliary nodes without s, t
        for(auto it : compress_nodes){
            G[loc].emplace_back(it);
            G[it + offset].emplace_back(loc);
        }

        int pS = tr.get(s);
        G[loc].emplace_back(pS + offset);
        G[loc].emplace_back(pS);

        int pT = tr.get(t);
        G[pT].emplace_back(loc);
        G[pT + offset].emplace_back(loc);
    }

    cout << (cycle_detection(G) ? "No\n" : "Yes\n");
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int T;
    cin >> T;
    while(T--) testcase();

    return 0;
}

Compilation message (stderr)

jail.cpp: In constructor 'path_decomposition_tree::path_decomposition_tree(int)':
jail.cpp:31:22: warning: 'path_decomposition_tree::num' will be initialized after [-Wreorder]
   31 |     int N, timerHLD, num;
      |                      ^~~
jail.cpp:31:9: warning:   'int path_decomposition_tree::N' [-Wreorder]
   31 |     int N, timerHLD, num;
      |         ^
jail.cpp:36:5: warning:   when initialized here [-Wreorder]
   36 |     path_decomposition_tree(int N) :
      |     ^~~~~~~~~~~~~~~~~~~~~~~
jail.cpp:32:38: warning: 'path_decomposition_tree::tout' will be initialized after [-Wreorder]
   32 |     vector<int> par, depth, sz, tin, tout, head;
      |                                      ^~~~
jail.cpp:32:17: warning:   'std::vector<int> path_decomposition_tree::par' [-Wreorder]
   32 |     vector<int> par, depth, sz, tin, tout, head;
      |                 ^~~
jail.cpp:36:5: warning:   when initialized here [-Wreorder]
   36 |     path_decomposition_tree(int N) :
      |     ^~~~~~~~~~~~~~~~~~~~~~~
jail.cpp: In function 'void testcase()':
jail.cpp:151:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  151 |     for(auto [u, v] : tr.edges){
      |              ^

• 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