oj.uz

Submission #966769

# Submission time Handle Problem Language Result Execution time Memory
966769 2024-04-20T10:21:23 Z LOLOLO Jail (JOI22_jail) C++17
49 / 100
 5000 ms 320516 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define           f    first
#define           s    second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 1.25e5;
vector <int> ed[N], ed2[N * 40];
int in[N], ou[N], dfstimer = 1, p[N][20], vi[N][20], vo[N][20], dep[N], st[N], en[N], cnt = 0;
char used[N * 40];
 
bool check_cycle(int u) {
    if (used[u] == 1)
        return 0;
 
    used[u] = 1; 
    for (auto x : ed2[u]) {
        if (used[x] != 2 && !check_cycle(x))
            return 0;
    }
 
    used[u] = 2;
    return 1;
}
 
void dfs(int u, int v) {
    vi[u][0] = ++cnt;
    vo[u][0] = ++cnt;
    if (st[u]) {
        ed2[st[u]].pb(vo[u][0]);
    }
 
    if (en[u]) {
        ed2[vi[u][0]].pb(en[u]);
    }
 
    dep[u] = dep[v] + 1;
    p[u][0] = v;
 
    for (int i = 1; i < 20; i++) {
        p[u][i] = p[p[u][i - 1]][i - 1];
        vi[u][i] = ++cnt;
        vo[u][i] = ++cnt;
        ed2[vo[u][i - 1]].pb(vo[u][i]);
        ed2[vo[p[u][i - 1]][i - 1]].pb(vo[u][i]);
        ed2[vi[u][i]].pb(vi[u][i - 1]);
        ed2[vi[u][i]].pb(vi[p[u][i - 1]][i - 1]);
    }
 
    ++dfstimer;
    in[u] = dfstimer;
    for (auto x : ed[u]) {
        if (x == v)
            continue;
 
        dfs(x, u);
    }
 
    ou[u] = dfstimer;
}
 
bool is(int a, int b) {
    return in[a] <= in[b] && ou[a] >= in[b]; 
}
 
int lca(int a, int b) {
    if (is(a, b))
        return a;
 
    if (is(b, a))
        return b;
 
    for (int i = 19; i >= 0; i--)
        if (is(p[a][i], b) == 0)
            a = p[a][i];
 
    return p[a][0];
}
 
int dis(int a, int b) {
    int c = lca(a, b);
    return dep[a] + dep[b] - dep[c] * 2;
}
 
void addedge(int a, int b, int id) {
    int k = dep[a] - dep[b] + 1;
    for (int j = 0; j < 20; j++) {
        if (k & (1 << j)) {
            ed2[id].pb(vi[a][j]);
            ed2[vo[a][j]].pb(id);
            a = p[a][j];
        }
    }
}
 
int find(int a, int k) {
    for (int j = 0; j < 20; j++)
        if (k & (1 << j))
            a = p[a][j];
 
    return a;
}
 
string solve() {
    int n;
    cin >> n;
 
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        ed[a].pb(b);
        ed[b].pb(a);
    }
 
    int m;
    cin >> m;
 
    vector <pair <int, int>> save;
 
    for (int i = 1; i <= m; i++) {
        int s, t;
        cin >> s >> t;
        save.pb({s, t});
        st[s] = i, en[t] = i;
    }
 
    cnt = m;
    dfs(1, 1);
 
    int id = 0;
    for (auto x : save) {
        id++;
        int s = x.f, t = x.s;
 
        int a = s, b = t;
        if (dep[s] > dep[t])
            swap(s, t);
 
        //int c = lca(s, t);
        /*if (s == c) {
            addedge(p[t][0], find(t, dep[t] - dep[s] - 1), id);
        } else {
            addedge(p[s][0], c, id);
            addedge(p[t][0], c, id);
        }*/
 
        for (int i = 1; i <= n; i++) {
            if (i == a || i == b)
                continue;        
 
            if (dis(i, a) + dis(i, b) == dis(a, b)) {
                if (st[i]) {
                    ed2[st[i]].pb(id);
                    ed2[st[i]].pb(id);
                }
 
                if (en[i]) {
                    ed2[id].pb(en[i]);
                    ed2[id].pb(en[i]);
                }
            } 
        }
 
        if (en[a]) {
            ed2[id].pb(en[a]);
            ed2[id].pb(en[a]);
        }
 
        if (st[b]) {
            ed2[st[b]].pb(id);
            ed2[st[b]].pb(id);
        }
    }
 
    int is = 0;
    for (int i = 1; i <= m; i++) {
        if (used[i] == 0 && check_cycle(i) == 0) {
            is = 1;
            break;
        }
    }
 
    for (int i = 1; i <= n; i++) {
        ed[i].clear();
        st[i] = en[i] = dep[i] = 0;
    }
 
    for (int i = 1; i <= cnt; i++) {
        ed2[i].clear();
        used[i] = 0;
    }
 
    if (is == 0)
        return "Yes";
 
    return "No";
}
 
int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);
 
    int t = 1;
    cin >> t;
 
    while (t--) {
        //solve();
        cout << solve() << "\n";
    }
 
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 130640 KB Output is correct
2 Correct 31 ms 130648 KB Output is correct
3 Correct 29 ms 130632 KB Output is correct
4 Correct 51 ms 131160 KB Output is correct
5 Correct 77 ms 131300 KB Output is correct
6 Correct 33 ms 130900 KB Output is correct
7 Correct 32 ms 130908 KB Output is correct
8 Correct 43 ms 131156 KB Output is correct
9 Correct 698 ms 145816 KB Output is correct
10 Correct 1327 ms 320516 KB Output is correct
11 Correct 39 ms 130816 KB Output is correct
12 Correct 132 ms 131612 KB Output is correct
13 Execution timed out 5056 ms 320488 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 130644 KB Output is correct
2 Correct 28 ms 130648 KB Output is correct
3 Correct 32 ms 130900 KB Output is correct
4 Correct 34 ms 130904 KB Output is correct
5 Correct 35 ms 131152 KB Output is correct
6 Correct 34 ms 130896 KB Output is correct
7 Correct 39 ms 130836 KB Output is correct
8 Correct 35 ms 130856 KB Output is correct
9 Correct 33 ms 130908 KB Output is correct
10 Correct 33 ms 131048 KB Output is correct
11 Correct 32 ms 130908 KB Output is correct
12 Correct 31 ms 130908 KB Output is correct
13 Correct 31 ms 130908 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 130644 KB Output is correct
2 Correct 28 ms 130648 KB Output is correct
3 Correct 32 ms 130900 KB Output is correct
4 Correct 34 ms 130904 KB Output is correct
5 Correct 35 ms 131152 KB Output is correct
6 Correct 34 ms 130896 KB Output is correct
7 Correct 39 ms 130836 KB Output is correct
8 Correct 35 ms 130856 KB Output is correct
9 Correct 33 ms 130908 KB Output is correct
10 Correct 33 ms 131048 KB Output is correct
11 Correct 32 ms 130908 KB Output is correct
12 Correct 31 ms 130908 KB Output is correct
13 Correct 31 ms 130908 KB Output is correct
14 Correct 29 ms 130648 KB Output is correct
15 Correct 30 ms 130652 KB Output is correct
16 Correct 32 ms 130832 KB Output is correct
17 Correct 40 ms 130908 KB Output is correct
18 Correct 38 ms 130904 KB Output is correct
19 Correct 30 ms 130640 KB Output is correct
20 Correct 42 ms 131036 KB Output is correct
21 Correct 39 ms 130892 KB Output is correct
22 Correct 39 ms 131072 KB Output is correct
23 Correct 29 ms 130648 KB Output is correct
24 Correct 30 ms 130652 KB Output is correct
25 Correct 39 ms 130904 KB Output is correct
26 Correct 33 ms 130876 KB Output is correct
27 Correct 39 ms 131148 KB Output is correct
28 Correct 31 ms 130516 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 130644 KB Output is correct
2 Correct 28 ms 130648 KB Output is correct
3 Correct 32 ms 130900 KB Output is correct
4 Correct 34 ms 130904 KB Output is correct
5 Correct 35 ms 131152 KB Output is correct
6 Correct 34 ms 130896 KB Output is correct
7 Correct 39 ms 130836 KB Output is correct
8 Correct 35 ms 130856 KB Output is correct
9 Correct 33 ms 130908 KB Output is correct
10 Correct 33 ms 131048 KB Output is correct
11 Correct 32 ms 130908 KB Output is correct
12 Correct 31 ms 130908 KB Output is correct
13 Correct 31 ms 130908 KB Output is correct
14 Correct 29 ms 130648 KB Output is correct
15 Correct 30 ms 130652 KB Output is correct
16 Correct 32 ms 130832 KB Output is correct
17 Correct 40 ms 130908 KB Output is correct
18 Correct 38 ms 130904 KB Output is correct
19 Correct 30 ms 130640 KB Output is correct
20 Correct 42 ms 131036 KB Output is correct
21 Correct 39 ms 130892 KB Output is correct
22 Correct 39 ms 131072 KB Output is correct
23 Correct 29 ms 130648 KB Output is correct
24 Correct 30 ms 130652 KB Output is correct
25 Correct 39 ms 130904 KB Output is correct
26 Correct 33 ms 130876 KB Output is correct
27 Correct 39 ms 131148 KB Output is correct
28 Correct 31 ms 130516 KB Output is correct
29 Correct 39 ms 131224 KB Output is correct
30 Correct 117 ms 131156 KB Output is correct
31 Correct 83 ms 131060 KB Output is correct
32 Correct 92 ms 131248 KB Output is correct
33 Correct 50 ms 130908 KB Output is correct
34 Correct 142 ms 130904 KB Output is correct
35 Correct 126 ms 130836 KB Output is correct
36 Correct 122 ms 131268 KB Output is correct
37 Correct 84 ms 130968 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 130644 KB Output is correct
2 Correct 28 ms 130648 KB Output is correct
3 Correct 32 ms 130900 KB Output is correct
4 Correct 34 ms 130904 KB Output is correct
5 Correct 35 ms 131152 KB Output is correct
6 Correct 34 ms 130896 KB Output is correct
7 Correct 39 ms 130836 KB Output is correct
8 Correct 35 ms 130856 KB Output is correct
9 Correct 33 ms 130908 KB Output is correct
10 Correct 33 ms 131048 KB Output is correct
11 Correct 32 ms 130908 KB Output is correct
12 Correct 31 ms 130908 KB Output is correct
13 Correct 31 ms 130908 KB Output is correct
14 Correct 29 ms 130648 KB Output is correct
15 Correct 30 ms 130652 KB Output is correct
16 Correct 32 ms 130832 KB Output is correct
17 Correct 40 ms 130908 KB Output is correct
18 Correct 38 ms 130904 KB Output is correct
19 Correct 30 ms 130640 KB Output is correct
20 Correct 42 ms 131036 KB Output is correct
21 Correct 39 ms 130892 KB Output is correct
22 Correct 39 ms 131072 KB Output is correct
23 Correct 29 ms 130648 KB Output is correct
24 Correct 30 ms 130652 KB Output is correct
25 Correct 39 ms 130904 KB Output is correct
26 Correct 33 ms 130876 KB Output is correct
27 Correct 39 ms 131148 KB Output is correct
28 Correct 31 ms 130516 KB Output is correct
29 Correct 39 ms 131224 KB Output is correct
30 Correct 117 ms 131156 KB Output is correct
31 Correct 83 ms 131060 KB Output is correct
32 Correct 92 ms 131248 KB Output is correct
33 Correct 50 ms 130908 KB Output is correct
34 Correct 142 ms 130904 KB Output is correct
35 Correct 126 ms 130836 KB Output is correct
36 Correct 122 ms 131268 KB Output is correct
37 Correct 84 ms 130968 KB Output is correct
38 Correct 708 ms 145916 KB Output is correct
39 Correct 1285 ms 319640 KB Output is correct
40 Execution timed out 5020 ms 141288 KB Time limit exceeded
41 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 130652 KB Output is correct
2 Correct 29 ms 130652 KB Output is correct
3 Correct 30 ms 130648 KB Output is correct
4 Correct 29 ms 130652 KB Output is correct
5 Correct 39 ms 130652 KB Output is correct
6 Correct 32 ms 130908 KB Output is correct
7 Correct 31 ms 130904 KB Output is correct
8 Correct 30 ms 130652 KB Output is correct
9 Correct 29 ms 130644 KB Output is correct
10 Correct 29 ms 131044 KB Output is correct
11 Correct 33 ms 130676 KB Output is correct
12 Correct 122 ms 130956 KB Output is correct
13 Correct 812 ms 131432 KB Output is correct
14 Correct 1020 ms 131152 KB Output is correct
15 Correct 1002 ms 130896 KB Output is correct
16 Execution timed out 5068 ms 309480 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 130640 KB Output is correct
2 Correct 31 ms 130648 KB Output is correct
3 Correct 29 ms 130632 KB Output is correct
4 Correct 51 ms 131160 KB Output is correct
5 Correct 77 ms 131300 KB Output is correct
6 Correct 33 ms 130900 KB Output is correct
7 Correct 32 ms 130908 KB Output is correct
8 Correct 43 ms 131156 KB Output is correct
9 Correct 698 ms 145816 KB Output is correct
10 Correct 1327 ms 320516 KB Output is correct
11 Correct 39 ms 130816 KB Output is correct
12 Correct 132 ms 131612 KB Output is correct
13 Execution timed out 5056 ms 320488 KB Time limit exceeded
14 Halted 0 ms 0 KB -