Submission #1116682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116682		Zero_OP	Jail (JOI22_jail)	C++14	5 / 100	399 ms	114616 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);

//    cout << "edges ;;;;;\n";
//    for(int i = 0; i < N; ++i){
//        for(int j : adj[i]){
//            cout << i << " " << j << '\n';
//        }
//    }
//    cout << '\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, idx, ln, rn;
    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(), idx(N),
         ln(4 * N, -1), rn(4 * N, -1) {}

    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;
    }

    int build(int l, int r){
        if(l == r){
            idx[l] = num++;
            return idx[l];
        } else{
            int mid = l + r >> 1, cur = num++;
            ln[cur] = build(l, mid);
            rn[cur] = build(mid + 1, r);

            edges.emplace_back(cur, ln[cur]);
            edges.emplace_back(cur, rn[cur]);
            return cur;
        }
    }

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

    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 cur, int l, int r, int u, int v, vector<int>& ans){
        if(u <= l && r <= v){
            ans.emplace_back(cur);
        } else{
            int mid = l + r >> 1;
            if(u <= mid) query_auxiliary_nodes(ln[cur], l, mid, u, v, ans);
            if(mid < v) query_auxiliary_nodes(rn[cur], mid + 1, r, u, v, ans);
        }
    }

    vector<int> query(int u, int v){ //ignore u, v
        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(0, 0, N - 1, tin[head[u]], tin[u], cur);
                u = par[head[u]];
            }

            if(tin[u] < tin[v]) query_auxiliary_nodes(0, 0, N - 1, 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(0, 0, N - 1, tin[head[u]], tin[u], cur);
            u = par[head[u]];
        }

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

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.idx[s];
        G[loc].emplace_back(pS + offset);
        G[loc].emplace_back(pS);

        int pT = tr.idx[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);
  
    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:39:22: warning: 'path_decomposition_tree::num' will be initialized after [-Wreorder]
   39 |     int N, timerHLD, num;
      |                      ^~~
jail.cpp:39:9: warning:   'int path_decomposition_tree::N' [-Wreorder]
   39 |     int N, timerHLD, num;
      |         ^
jail.cpp:44:5: warning:   when initialized here [-Wreorder]
   44 |     path_decomposition_tree(int N) :
      |     ^~~~~~~~~~~~~~~~~~~~~~~
jail.cpp:40:38: warning: 'path_decomposition_tree::tout' will be initialized after [-Wreorder]
   40 |     vector<int> par, depth, sz, tin, tout, head, idx, ln, rn;
      |                                      ^~~~
jail.cpp:40:17: warning:   'std::vector<int> path_decomposition_tree::par' [-Wreorder]
   40 |     vector<int> par, depth, sz, tin, tout, head, idx, ln, rn;
      |                 ^~~
jail.cpp:44:5: warning:   when initialized here [-Wreorder]
   44 |     path_decomposition_tree(int N) :
      |     ^~~~~~~~~~~~~~~~~~~~~~~
jail.cpp:42:28: warning: 'path_decomposition_tree::edges' will be initialized after [-Wreorder]
   42 |     vector<pair<int, int>> edges;
      |                            ^~~~~
jail.cpp:40:50: warning:   'std::vector<int> path_decomposition_tree::idx' [-Wreorder]
   40 |     vector<int> par, depth, sz, tin, tout, head, idx, ln, rn;
      |                                                  ^~~
jail.cpp:44:5: warning:   when initialized here [-Wreorder]
   44 |     path_decomposition_tree(int N) :
      |     ^~~~~~~~~~~~~~~~~~~~~~~
jail.cpp: In member function 'int path_decomposition_tree::build(int, int)':
jail.cpp:80:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |             int mid = l + r >> 1, cur = num++;
      |                       ~~^~~
jail.cpp: In member function 'void path_decomposition_tree::query_auxiliary_nodes(int, int, int, int, int, std::vector<int>&)':
jail.cpp:104:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |             int mid = l + r >> 1;
      |                       ~~^~~
jail.cpp: In function 'void testcase()':
jail.cpp:164:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  164 |     for(auto [u, v] : tr.edges){
      |              ^

• Subtask 1: 5 / 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