oj.uz

Submission #601336

# Submission time Handle Problem Language Result Execution time Memory
601336 2022-07-21T17:55:16 Z dxz05 Jail (JOI22_jail) C++14
0 / 100
 91 ms 31828 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);
}

vector<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);
    vector<int> ids(n, -1), idt(n, -1);

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

    if (depth[n - 1] == n){
        vector<int> left(n, 0), right(n, 0);
        for (int i = 0; i < m; i++){
            if (S[i] < T[i]){
                right[S[i]]++;
                right[T[i]]--;
            } else {
                left[T[i]]++;
                left[S[i]]--;
            }
        }

        for (int i = 1; i < n; i++) left[i] += left[i - 1], right[i] += right[i - 1];

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

        cout << "Yes\n";
        return;
    }

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

    for (int i = 0; i < m; i++){
        int s = S[i], t = T[i];
        int l = lca(s, t);
        while (upper(l, s)){
            int j = ids[s];
            if (j != -1 && j != i) gg[j].push_back(i);
            j = idt[s];
            if (j != -1 && j != i) gg[i].push_back(j);
            if (s == 0) break;
            s = up[s][0];
        }

        while (upper(l, t)){
            int j = ids[t];
            if (j != -1 && j != i) gg[j].push_back(i);
            j = idt[t];
            if (j != -1 && j != i) gg[i].push_back(j);
            if (t == 0) break;
            t = up[t][0];
        }
    }

    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 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 20 ms 9684 KB Output is correct
5 Correct 37 ms 9780 KB Output is correct
6 Correct 7 ms 9684 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 7 ms 9812 KB Output is correct
9 Correct 91 ms 12688 KB Output is correct
10 Correct 46 ms 29144 KB Output is correct
11 Correct 11 ms 9776 KB Output is correct
12 Correct 41 ms 9876 KB Output is correct
13 Correct 55 ms 29572 KB Output is correct
14 Correct 71 ms 29520 KB Output is correct
15 Correct 61 ms 29556 KB Output is correct
16 Correct 65 ms 30140 KB Output is correct
17 Correct 73 ms 29580 KB Output is correct
18 Correct 69 ms 30176 KB Output is correct
19 Correct 70 ms 29676 KB Output is correct
20 Correct 57 ms 29656 KB Output is correct
21 Correct 57 ms 31828 KB Output is correct
22 Incorrect 58 ms 31740 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9748 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9752 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 6 ms 9672 KB Output is correct
12 Incorrect 6 ms 9744 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9748 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9752 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 6 ms 9672 KB Output is correct
12 Incorrect 6 ms 9744 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9748 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9752 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 6 ms 9672 KB Output is correct
12 Incorrect 6 ms 9744 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9748 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9752 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 6 ms 9672 KB Output is correct
12 Incorrect 6 ms 9744 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 13 ms 9760 KB Output is correct
6 Incorrect 6 ms 9684 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 20 ms 9684 KB Output is correct
5 Correct 37 ms 9780 KB Output is correct
6 Correct 7 ms 9684 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 7 ms 9812 KB Output is correct
9 Correct 91 ms 12688 KB Output is correct
10 Correct 46 ms 29144 KB Output is correct
11 Correct 11 ms 9776 KB Output is correct
12 Correct 41 ms 9876 KB Output is correct
13 Correct 55 ms 29572 KB Output is correct
14 Correct 71 ms 29520 KB Output is correct
15 Correct 61 ms 29556 KB Output is correct
16 Correct 65 ms 30140 KB Output is correct
17 Correct 73 ms 29580 KB Output is correct
18 Correct 69 ms 30176 KB Output is correct
19 Correct 70 ms 29676 KB Output is correct
20 Correct 57 ms 29656 KB Output is correct
21 Correct 57 ms 31828 KB Output is correct
22 Incorrect 58 ms 31740 KB Output isn't correct
23 Halted 0 ms 0 KB -