Submission #561295

#	Time	Username	Problem	Language	Result	Execution time	Memory
561295		wiwiho	Jail (JOI22_jail)	C++14	100 / 100	1742 ms	338600 KiB

jail

#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define pob pop_back()
#define mp make_pair
#define F first
#define S second
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

struct Node{
    int l = -1, r = -1;
};

int n, m;
vector<vector<int>> g, tg;
vector<int> from, to;
vector<int> in, out, pr, dpt;
vector<vector<int>> anc, up, down;
const int SZ = 18;
int node, ts;

#define initarr(a, b) a.clear(); a.resize(b);
#define initarr2(a, b, c) a.clear(); a.resize(b, c);

void init(){
    cin >> n;
    initarr(g, n + 1);
    for(int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        g[u].eb(v);
        g[v].eb(u);
    }
    cin >> m;
    initarr(from, m + 1);
    initarr(to, m + 1);
    for(int i = 1; i <= m; i++) cin >> from[i] >> to[i];
    initarr(tg, 1 + m + 2 * n * SZ);

    initarr(in, n + 1);
    initarr(out, n + 1);
    initarr(pr, n + 1);
    initarr(dpt, n + 1);
    ts = 0;

    node = m;
    initarr2(anc, SZ, vector<int>(n + 1));
    initarr2(up, SZ, vector<int>(n + 1));
    initarr2(down, SZ, vector<int>(n + 1));
}

void dfs(int now, int p){
    pr[now] = p;
    anc[0][now] = p;
    in[now] = ts++;
    dpt[now] = now == p ? 0 : dpt[p] + 1;
    for(int i : g[now]){
        if(i == p) continue;
        dfs(i, now);
    }
    out[now] = ts++;
}

bool isAnc(int a, int b){
    return in[a] <= in[b] && out[b] <= out[a];
}

int jump(int a, int dis){
    for(int i = 0; i < SZ; i++){
        if(1 << i & dis) a = anc[i][a];
    }
    return a;
}

int getlca(int a, int b){
    if(isAnc(a, b)) return a;
    for(int i = SZ - 1; i >= 0; i--){
        if(!isAnc(anc[i][a], b)) a = anc[i][a];
    }
    return anc[0][a];
}

// 0: in, 1: out
void modify(int a, int b, int ty, vector<vector<int>>& st, int v){
    //cerr << "start " << a << " " << b << " " << ty << "\n";
    for(int i = SZ - 1; i >= 0; i--){
        if(isAnc(anc[i][a], b) && anc[i][a] != b) continue;
        //cerr << "modify " << ty << " " << v << " " << mp(i, a) << " " << st[i][a] << "\n";
        if(ty == 0){
            tg[v].eb(st[i][a]);
        }
        else{
            tg[st[i][a]].eb(v);
        }
        a = anc[i][a];
    }
    //cerr << "modify " << ty << " " << v << " " << mp(0, a) << " " << st[0][a] << "\n";
    if(ty == 0){
        tg[v].eb(st[0][a]);
    }
    else{
        tg[st[0][a]].eb(v);
    }
}

void solve(){
    
    init();
    dfs(1, 1);

    for(int i = 0; i < SZ; i++){
        for(int j = 1; j <= n; j++){
            down[i][j] = ++node;
            up[i][j] = ++node;
        }
    }
    //cerr << "node " << node << "\n";
    //cerr << "tg.size " << tg.size() << "\n";
    for(int i = 1; i < SZ; i++){
        for(int j = 1; j <= n; j++){
            anc[i][j] = anc[i - 1][anc[i - 1][j]];
            tg[down[i][j]].eb(down[i - 1][j]);
            tg[down[i][j]].eb(down[i - 1][anc[i - 1][j]]);
            tg[up[i - 1][j]].eb(up[i][j]);
            tg[up[i - 1][anc[i - 1][j]]].eb(up[i][j]);
        }
    }

    for(int i = 1; i <= m; i++){
        int s = from[i], t = to[i];
        modify(s, s, 0, up, i);
        modify(t, t, 1, down, i);

        {
            int tt = t;
            if(isAnc(tt, s)) tt = jump(s, dpt[s] - dpt[tt] - 1);
            else tt = pr[tt];
            int lca = getlca(s, tt);
            modify(s, lca, 0, down, i);
            modify(tt, lca, 0, down, i);
        }
        {
            int ss = s;
            if(isAnc(ss, t)) ss = jump(t, dpt[t] - dpt[ss] - 1);
            else ss = pr[ss];
            int lca = getlca(ss, t);
            modify(ss, lca, 1, up, i);
            modify(t, lca, 1, up, i);
        }
    }

    vector<int> deg(tg.size());
    for(int i = 1; i < tg.size(); i++){
        for(int j : tg[i]){
            //if(i <= m || j <= m) cerr << "edge " << i << "->" << j << "\n";
            deg[j]++;
        }
    }

    queue<int> q;
    for(int i = 1; i < tg.size(); i++){
        if(deg[i] == 0) q.push(i);
    }
    while(!q.empty()){
        int now = q.front();
        //cerr << "ok " << now << "\n";
        q.pop();
        for(int i : tg[now]){
            deg[i]--;
            if(deg[i] == 0){
                q.push(i);
            }
        }
    }
    
    bool ans = true;
    for(int i = 1; i <= m; i++){
        if(deg[i] != 0) ans = false;
    }
    if(ans) cout << "Yes\n";
    else cout << "No\n";

}

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

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

    return 0;
}

Compilation message (stderr)

jail.cpp: In function 'void solve()':
jail.cpp:171:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |     for(int i = 1; i < tg.size(); i++){
      |                    ~~^~~~~~~~~~~
jail.cpp:179:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |     for(int i = 1; i < tg.size(); i++){
      |                    ~~^~~~~~~~~~~

• 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