oj.uz

Submission #601007

# Submission time Handle Problem Language Result Execution time Memory
601007 2022-07-21T10:04:16 Z dxz05 Jail (JOI22_jail) C++14
61 / 100
 5000 ms 41096 KB 
//#pragma GCC optimize("Ofast,O2,O3,unroll-loops")
//#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << "[" << H << "]";
    debug_out(T...);
}

#ifdef dddxxz
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SZ(s) ((int)s.size())
#define all(x) (x).begin(), (x).end()
#define lla(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair

clock_t startTime;

double getCurrentTime() {
    return (double) (clock() - startTime) / CLOCKS_PER_SEC;
}

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 1000000101;
const long long LLINF = 1223372000000000555;
const int N = 2e5 + 3e2;
const int M = 5555;

vector<int> g[N];

int tin[N], tout[N], timer = 0;
int up[N][18], depth[N];

inline void dfs(int v, int p){
    tin[v] = ++timer;
    depth[v] = depth[p] + 1;

    up[v][0] = p;
    for (int i = 1; i < 18; i++){
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for (int u : g[v]){
        if (u != p) dfs(u, v);
    }
    tout[v] = ++timer;
}

inline bool upper(int u, int v){
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

inline int lca(int u, int v){
    if (upper(u, v)) return u;
    if (upper(v, u)) return v;
    for (int i = 17; i >= 0; i--){
        if (!upper(up[u][i], v)) u = up[u][i];
    }
    return up[u][0];
}

inline int dist(int u, int v){
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}

inline bool in(int a, int b, int c){
    return dist(a, c) == dist(a, b) + dist(b, c);
}

set<int> gg[N];

int color[N];
bool dfs(int v){
    color[v] = 1;
    for (int u : gg[v]){
        if (color[u] == 1) return true;
        if (color[u] == 0 && dfs(u)) return true;
    }
    color[v] = 2;
    return false;
}

void solve(int TC) {
    int n;
    cin >> n;

    timer = 0;
    for (int i = 0; i < n; i++) g[i].clear();

    for (int i = 0; i < n - 1; i++){
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(0, 0);

    int m;
    cin >> m;

    vector<int> S(m), T(m);
    for (int i = 0; i < m; i++){
        cin >> S[i] >> T[i];
        S[i]--, T[i]--;
    }

    for (int i = 0; i < m; i++){
        gg[i].clear();
        color[i] = 0;
    }

    bool ok = true;
    for (int i = 0; i < m; i++){
        for (int j = 0; j < m; j++){
            if (i == j) continue;
            if (in(S[i], S[j], T[i]) && in(S[i], T[j], T[i])) ok = false;
            if (in(S[j], S[i], T[j]) && in(S[j], T[i], T[j])) ok = false;
            if (in(S[i], S[j], T[i])) gg[j].insert(i);
            if (in(S[i], T[j], T[i])) gg[i].insert(j);
        }
    }

    if (!ok){
        cout << "No\n";
        return;
    }

    for (int i = 0; i < m; i++){
        if (color[i] == 0 && dfs(i)){
            cout << "No\n";
            return;
        }
    }

    cout << "Yes\n";

}

int main() {
    startTime = clock();
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

#ifdef dddxxz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int TC = 1;
    cin >> TC;

    for (int test = 1; test <= TC; test++) {
        //debug(test);
        //cout << "Case #" << test << ": ";
        solve(test);
    }

#ifdef dddxxz
    cerr << endl << "Time: " << int(getCurrentTime() * 1000) << " ms" << endl;
#endif

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 9 ms 14420 KB Output is correct
3 Correct 9 ms 14456 KB Output is correct
4 Correct 18 ms 14728 KB Output is correct
5 Correct 30 ms 15112 KB Output is correct
6 Correct 10 ms 14472 KB Output is correct
7 Correct 9 ms 14476 KB Output is correct
8 Correct 19 ms 14768 KB Output is correct
9 Correct 482 ms 23648 KB Output is correct
10 Correct 79 ms 39284 KB Output is correct
11 Correct 17 ms 14632 KB Output is correct
12 Correct 199 ms 15740 KB Output is correct
13 Execution timed out 5033 ms 41096 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 10 ms 14460 KB Output is correct
3 Correct 9 ms 14548 KB Output is correct
4 Correct 10 ms 14492 KB Output is correct
5 Correct 9 ms 14472 KB Output is correct
6 Correct 9 ms 14536 KB Output is correct
7 Correct 11 ms 14452 KB Output is correct
8 Correct 9 ms 14548 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Correct 10 ms 14476 KB Output is correct
11 Correct 9 ms 14488 KB Output is correct
12 Correct 10 ms 14488 KB Output is correct
13 Correct 9 ms 14420 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 10 ms 14460 KB Output is correct
3 Correct 9 ms 14548 KB Output is correct
4 Correct 10 ms 14492 KB Output is correct
5 Correct 9 ms 14472 KB Output is correct
6 Correct 9 ms 14536 KB Output is correct
7 Correct 11 ms 14452 KB Output is correct
8 Correct 9 ms 14548 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Correct 10 ms 14476 KB Output is correct
11 Correct 9 ms 14488 KB Output is correct
12 Correct 10 ms 14488 KB Output is correct
13 Correct 9 ms 14420 KB Output is correct
14 Correct 7 ms 14420 KB Output is correct
15 Correct 7 ms 14456 KB Output is correct
16 Correct 8 ms 14420 KB Output is correct
17 Correct 10 ms 14432 KB Output is correct
18 Correct 9 ms 14420 KB Output is correct
19 Correct 7 ms 14420 KB Output is correct
20 Correct 11 ms 14420 KB Output is correct
21 Correct 9 ms 14420 KB Output is correct
22 Correct 9 ms 14472 KB Output is correct
23 Correct 9 ms 14456 KB Output is correct
24 Correct 9 ms 14464 KB Output is correct
25 Correct 9 ms 14420 KB Output is correct
26 Correct 9 ms 14420 KB Output is correct
27 Correct 9 ms 14548 KB Output is correct
28 Correct 8 ms 14456 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 10 ms 14460 KB Output is correct
3 Correct 9 ms 14548 KB Output is correct
4 Correct 10 ms 14492 KB Output is correct
5 Correct 9 ms 14472 KB Output is correct
6 Correct 9 ms 14536 KB Output is correct
7 Correct 11 ms 14452 KB Output is correct
8 Correct 9 ms 14548 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Correct 10 ms 14476 KB Output is correct
11 Correct 9 ms 14488 KB Output is correct
12 Correct 10 ms 14488 KB Output is correct
13 Correct 9 ms 14420 KB Output is correct
14 Correct 7 ms 14420 KB Output is correct
15 Correct 7 ms 14456 KB Output is correct
16 Correct 8 ms 14420 KB Output is correct
17 Correct 10 ms 14432 KB Output is correct
18 Correct 9 ms 14420 KB Output is correct
19 Correct 7 ms 14420 KB Output is correct
20 Correct 11 ms 14420 KB Output is correct
21 Correct 9 ms 14420 KB Output is correct
22 Correct 9 ms 14472 KB Output is correct
23 Correct 9 ms 14456 KB Output is correct
24 Correct 9 ms 14464 KB Output is correct
25 Correct 9 ms 14420 KB Output is correct
26 Correct 9 ms 14420 KB Output is correct
27 Correct 9 ms 14548 KB Output is correct
28 Correct 8 ms 14456 KB Output is correct
29 Correct 19 ms 14720 KB Output is correct
30 Correct 91 ms 14548 KB Output is correct
31 Correct 63 ms 14660 KB Output is correct
32 Correct 49 ms 14504 KB Output is correct
33 Correct 14 ms 14512 KB Output is correct
34 Correct 179 ms 14568 KB Output is correct
35 Correct 180 ms 14764 KB Output is correct
36 Correct 167 ms 14528 KB Output is correct
37 Correct 104 ms 14660 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 10 ms 14460 KB Output is correct
3 Correct 9 ms 14548 KB Output is correct
4 Correct 10 ms 14492 KB Output is correct
5 Correct 9 ms 14472 KB Output is correct
6 Correct 9 ms 14536 KB Output is correct
7 Correct 11 ms 14452 KB Output is correct
8 Correct 9 ms 14548 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Correct 10 ms 14476 KB Output is correct
11 Correct 9 ms 14488 KB Output is correct
12 Correct 10 ms 14488 KB Output is correct
13 Correct 9 ms 14420 KB Output is correct
14 Correct 7 ms 14420 KB Output is correct
15 Correct 7 ms 14456 KB Output is correct
16 Correct 8 ms 14420 KB Output is correct
17 Correct 10 ms 14432 KB Output is correct
18 Correct 9 ms 14420 KB Output is correct
19 Correct 7 ms 14420 KB Output is correct
20 Correct 11 ms 14420 KB Output is correct
21 Correct 9 ms 14420 KB Output is correct
22 Correct 9 ms 14472 KB Output is correct
23 Correct 9 ms 14456 KB Output is correct
24 Correct 9 ms 14464 KB Output is correct
25 Correct 9 ms 14420 KB Output is correct
26 Correct 9 ms 14420 KB Output is correct
27 Correct 9 ms 14548 KB Output is correct
28 Correct 8 ms 14456 KB Output is correct
29 Correct 19 ms 14720 KB Output is correct
30 Correct 91 ms 14548 KB Output is correct
31 Correct 63 ms 14660 KB Output is correct
32 Correct 49 ms 14504 KB Output is correct
33 Correct 14 ms 14512 KB Output is correct
34 Correct 179 ms 14568 KB Output is correct
35 Correct 180 ms 14764 KB Output is correct
36 Correct 167 ms 14528 KB Output is correct
37 Correct 104 ms 14660 KB Output is correct
38 Correct 468 ms 23504 KB Output is correct
39 Correct 77 ms 39324 KB Output is correct
40 Correct 4207 ms 19792 KB Output is correct
41 Correct 4497 ms 16364 KB Output is correct
42 Correct 4322 ms 20240 KB Output is correct
43 Correct 57 ms 16492 KB Output is correct
44 Correct 4198 ms 15096 KB Output is correct
45 Correct 334 ms 29644 KB Output is correct
46 Correct 338 ms 29448 KB Output is correct
47 Correct 460 ms 31568 KB Output is correct
48 Correct 450 ms 31616 KB Output is correct
49 Correct 372 ms 29652 KB Output is correct
50 Correct 381 ms 29604 KB Output is correct
51 Correct 96 ms 29924 KB Output is correct
52 Correct 97 ms 30208 KB Output is correct
53 Correct 3837 ms 15596 KB Output is correct
54 Correct 318 ms 29424 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14416 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 9 ms 14456 KB Output is correct
4 Correct 9 ms 14420 KB Output is correct
5 Correct 21 ms 14728 KB Output is correct
6 Correct 9 ms 14420 KB Output is correct
7 Correct 9 ms 14468 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 9 ms 14420 KB Output is correct
10 Correct 8 ms 14464 KB Output is correct
11 Correct 9 ms 14420 KB Output is correct
12 Correct 162 ms 14508 KB Output is correct
13 Correct 1678 ms 15120 KB Output is correct
14 Correct 753 ms 15344 KB Output is correct
15 Correct 1300 ms 15252 KB Output is correct
16 Execution timed out 5007 ms 30032 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 9 ms 14420 KB Output is correct
3 Correct 9 ms 14456 KB Output is correct
4 Correct 18 ms 14728 KB Output is correct
5 Correct 30 ms 15112 KB Output is correct
6 Correct 10 ms 14472 KB Output is correct
7 Correct 9 ms 14476 KB Output is correct
8 Correct 19 ms 14768 KB Output is correct
9 Correct 482 ms 23648 KB Output is correct
10 Correct 79 ms 39284 KB Output is correct
11 Correct 17 ms 14632 KB Output is correct
12 Correct 199 ms 15740 KB Output is correct
13 Execution timed out 5033 ms 41096 KB Time limit exceeded
14 Halted 0 ms 0 KB -