Submission #665284

#	Time	Username	Problem	Language	Result	Execution time	Memory
665284		ParsaS	Jail (JOI22_jail)	C++17	5 / 100	133 ms	48552 KiB

jail

// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 2e5 + 5, L = 20;
int n, m, par[N], deg[N];
vector<pair<int, int> > S[N], T[N];
set<int> st[N];
pair<int, int> P[N];
vector<int> G[N], adj[N];
int up[N][L], Tp, tin[N], tout[N];

void dfs(int v, int p) {
    up[v][0] = p;
    for (int l = 1; l < L; l++)
        up[v][l] = up[up[v][l - 1]][l - 1];
    tin[v] = Tp++;
    for (auto u : adj[v]) {
        if (u != p)
            dfs(u, v);
    }
    tout[v] = Tp++;
}
vector<int> tmp;
void _merge(int u, int v) {
    if (st[u].size() > st[v].size())
        st[u].swap(st[v]);
    for (auto x : st[u]) {
        if (st[v].count(x))
            tmp.pb(x);
        st[v].insert(x);
    }
}
void dfs2(int v, int p) {
    int s = -1, t = -1;
    if (!S[v].empty()) {
        s = S[v].back().se;
    }
    if (!T[v].empty())
        t = T[v].back().se;

    tmp.clear();
    for (auto u : adj[v]) {
        if (u == p)
            continue;
        dfs2(u, v);
        _merge(u, v);
    }
    if (s != -1) {
        for (auto u : st[v]) {
            if (u != s)
                G[s].pb(u);
        }
        if (st[v].count(s)) {
            st[v].erase(s);
        }
            
        else
            st[v].insert(s);
    }
    if (t != -1) {
        for (auto u : st[v])
            if (u != t)
                G[u].pb(t);
        if (st[v].count(t))
            st[v].erase(t);
        else
            st[v].insert(t);
    }
    for (auto x : tmp)
        st[v].erase(x);
}
bool anc(int v, int u) {
    return tin[v] <= tin[u] && tout[v] >= tout[u];
}
int lca(int v, int u) {
    if (tin[v] > tin[u])
        swap(v, u);
    if (anc(v, u))
        return v;
    for (int i = L - 1; i >= 0; i--) {
        if (!anc(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}
void solve2() {
    sort(P, P +m);
    for (int i = 0; i < m - 1; i++) {
        if (P[i].se > P[i + 1].se) {
            cout << "No" << '\n';
            return;
        }

    }
    cout << "Yes";
}


void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        S[i].clear(), T[i].clear(), adj[i].clear();
    for (int i = 0; i < m; i++)
        G[i].clear(), deg[i] = 0;
    for (int i = 0; i < n - 1; i++) {
        int v, u; cin >> v >> u;
        adj[v].pb(u), adj[u].pb(v);
    }
    cin >> m;
    vector<pair<pair<int, int>, int> > vec;
    for (int i = 0; i < m; i++) {
        int s, t; cin >> s >> t;
        P[i] = mp(s, t);
        vec.pb(mp(mp(s, t), i));
        S[s].pb(mp(t, i));
        T[t].pb(mp(s, i));
    }
    if (m > 500) {
        solve2();
        return;
    }
        
    for (int i = 0; i < vec.size(); i++) {
        int s = vec[i].fi.fi, t = vec[i].fi.se, v = vec[i].se;
    }
    dfs2(1, 0);
    for (int i = 0; i < m; i++) {
        for (auto u : G[i]) {
            deg[u]++;
        }
    }
    queue<int> Q;
    for (int i = 0; i < m; i++)
        if (deg[i] == 0)
            Q.push(i);
    while (!Q.empty()) {
        int v = Q.front();
        Q.pop();
        for (auto u : G[v]) {
            deg[u]--;
            if (!deg[u])
                Q.push(u);
        }
    }
    cout << (*max_element(deg, deg + m) == 0 ? "Yes" : "No") << '\n';
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int tc; cin >> tc;
    while (tc--) {
        solve();
    }

    return 0;
}

Compilation message (stderr)

jail.cpp: In function 'void solve()':
jail.cpp:128:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for (int i = 0; i < vec.size(); i++) {
      |                     ~~^~~~~~~~~~~~
jail.cpp:129:13: warning: unused variable 's' [-Wunused-variable]
  129 |         int s = vec[i].fi.fi, t = vec[i].fi.se, v = vec[i].se;
      |             ^
jail.cpp:129:31: warning: unused variable 't' [-Wunused-variable]
  129 |         int s = vec[i].fi.fi, t = vec[i].fi.se, v = vec[i].se;
      |                               ^
jail.cpp:129:49: warning: unused variable 'v' [-Wunused-variable]
  129 |         int s = vec[i].fi.fi, t = vec[i].fi.se, v = vec[i].se;
      |                                                 ^

• 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