oj.uz

Submission #665216

# Submission time Handle Problem Language Result Execution time Memory
665216 2022-11-27T10:20:39 Z ParsaS Jail (JOI22_jail) C++17
0 / 100
 5000 ms 895252 KB 
// 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];
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 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;
        vec.pb(mp(mp(s, t), i));
        S[s].pb(mp(t, i));
        T[t].pb(mp(s, i));
    }
    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

jail.cpp: In function 'void solve()':
jail.cpp:110: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]
  110 |     for (int i = 0; i < vec.size(); i++) {
      |                     ~~^~~~~~~~~~~~
jail.cpp:111:13: warning: unused variable 's' [-Wunused-variable]
  111 |         int s = vec[i].fi.fi, t = vec[i].fi.se, v = vec[i].se;
      |             ^
jail.cpp:111:31: warning: unused variable 't' [-Wunused-variable]
  111 |         int s = vec[i].fi.fi, t = vec[i].fi.se, v = vec[i].se;
      |                               ^
jail.cpp:111:49: warning: unused variable 'v' [-Wunused-variable]
  111 |         int s = vec[i].fi.fi, t = vec[i].fi.se, v = vec[i].se;
      |                                                 ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28512 KB Output is correct
2 Correct 13 ms 28436 KB Output is correct
3 Correct 14 ms 28512 KB Output is correct
4 Correct 21 ms 28780 KB Output is correct
5 Correct 33 ms 29264 KB Output is correct
6 Correct 18 ms 28576 KB Output is correct
7 Correct 16 ms 28500 KB Output is correct
8 Correct 16 ms 28652 KB Output is correct
9 Correct 75 ms 32700 KB Output is correct
10 Correct 61 ms 48452 KB Output is correct
11 Correct 20 ms 28652 KB Output is correct
12 Correct 57 ms 29572 KB Output is correct
13 Correct 207 ms 81000 KB Output is correct
14 Correct 192 ms 94852 KB Output is correct
15 Execution timed out 5124 ms 895252 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28516 KB Output is correct
2 Correct 15 ms 28388 KB Output is correct
3 Correct 19 ms 28524 KB Output is correct
4 Incorrect 20 ms 28520 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28516 KB Output is correct
2 Correct 15 ms 28388 KB Output is correct
3 Correct 19 ms 28524 KB Output is correct
4 Incorrect 20 ms 28520 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28516 KB Output is correct
2 Correct 15 ms 28388 KB Output is correct
3 Correct 19 ms 28524 KB Output is correct
4 Incorrect 20 ms 28520 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28516 KB Output is correct
2 Correct 15 ms 28388 KB Output is correct
3 Correct 19 ms 28524 KB Output is correct
4 Incorrect 20 ms 28520 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28416 KB Output is correct
2 Correct 14 ms 28500 KB Output is correct
3 Correct 19 ms 28440 KB Output is correct
4 Correct 16 ms 28452 KB Output is correct
5 Correct 24 ms 28660 KB Output is correct
6 Incorrect 23 ms 28512 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28512 KB Output is correct
2 Correct 13 ms 28436 KB Output is correct
3 Correct 14 ms 28512 KB Output is correct
4 Correct 21 ms 28780 KB Output is correct
5 Correct 33 ms 29264 KB Output is correct
6 Correct 18 ms 28576 KB Output is correct
7 Correct 16 ms 28500 KB Output is correct
8 Correct 16 ms 28652 KB Output is correct
9 Correct 75 ms 32700 KB Output is correct
10 Correct 61 ms 48452 KB Output is correct
11 Correct 20 ms 28652 KB Output is correct
12 Correct 57 ms 29572 KB Output is correct
13 Correct 207 ms 81000 KB Output is correct
14 Correct 192 ms 94852 KB Output is correct
15 Execution timed out 5124 ms 895252 KB Time limit exceeded
16 Halted 0 ms 0 KB -