oj.uz

Submission #598104

# Submission time Handle Problem Language Result Execution time Memory
598104 2022-07-17T15:15:19 Z dxz05 Jail (JOI22_jail) C++14
5 / 100
 5000 ms 28992 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)];
}

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

vector<int> gg[N];
bool jail(int n, int m, vector<int> S, vector<int> T){
    for (int i = 0; i < m; i++){
        for (int j = i + 1; j < m; j++){
            if (in(S[i], S[j], T[i]) && in(S[i], T[j], T[i])) return false;
            if (in(S[j], S[i], T[j]) && in(S[j], T[i], T[j])) return false;

            int x = -1, y = -1;
            if (in(S[j], S[i], T[j])) x = S[i];
            if (in(S[j], T[i], T[j])) x = T[i];
            if (in(S[i], S[j], T[i])) y = S[j];
            if (in(S[i], T[j], T[i])) y = T[j];

            if (x == -1 && y == -1) continue;
            bool ok = false;

            if (x == -1){
                gg[i].push_back(j);
                ok = true;
            }
            if (y == -1){
                gg[j].push_back(i);
                ok = true;
            }

            if (x != -1 && y != -1){
                if (x == y){
                    if (x == S[i]) gg[i].push_back(j); else
                        gg[j].push_back(i);
                    ok = true;
                } else {
                    if (x == S[i] && y == T[j]){
                        gg[i].push_back(j);
                        ok = true;
                    }
                    if (x == T[i] && y == S[j]){
                        gg[j].push_back(i);
                        ok = true;
                    }
                }
            }

            if (!ok) return false;
        }
    }

    return true;
}

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;
    }

    if (!jail(n, m, S, T)){
        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 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 15 ms 9768 KB Output is correct
5 Correct 26 ms 9776 KB Output is correct
6 Correct 6 ms 9724 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 7 ms 9812 KB Output is correct
9 Correct 62 ms 11212 KB Output is correct
10 Correct 50 ms 27980 KB Output is correct
11 Correct 10 ms 9684 KB Output is correct
12 Correct 43 ms 9784 KB Output is correct
13 Execution timed out 5058 ms 28992 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9692 KB Output is correct
8 Correct 7 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9768 KB Output is correct
11 Correct 5 ms 9708 KB Output is correct
12 Correct 5 ms 9740 KB Output is correct
13 Correct 6 ms 9792 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9692 KB Output is correct
8 Correct 7 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9768 KB Output is correct
11 Correct 5 ms 9708 KB Output is correct
12 Correct 5 ms 9740 KB Output is correct
13 Correct 6 ms 9792 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 7 ms 9812 KB Output is correct
17 Correct 7 ms 9812 KB Output is correct
18 Correct 6 ms 9768 KB Output is correct
19 Correct 5 ms 9748 KB Output is correct
20 Correct 6 ms 9812 KB Output is correct
21 Correct 6 ms 9812 KB Output is correct
22 Correct 7 ms 9768 KB Output is correct
23 Incorrect 5 ms 9752 KB Output isn't correct
24 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 4 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9692 KB Output is correct
8 Correct 7 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9768 KB Output is correct
11 Correct 5 ms 9708 KB Output is correct
12 Correct 5 ms 9740 KB Output is correct
13 Correct 6 ms 9792 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 7 ms 9812 KB Output is correct
17 Correct 7 ms 9812 KB Output is correct
18 Correct 6 ms 9768 KB Output is correct
19 Correct 5 ms 9748 KB Output is correct
20 Correct 6 ms 9812 KB Output is correct
21 Correct 6 ms 9812 KB Output is correct
22 Correct 7 ms 9768 KB Output is correct
23 Incorrect 5 ms 9752 KB Output isn't correct
24 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 4 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9692 KB Output is correct
8 Correct 7 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9768 KB Output is correct
11 Correct 5 ms 9708 KB Output is correct
12 Correct 5 ms 9740 KB Output is correct
13 Correct 6 ms 9792 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 7 ms 9812 KB Output is correct
17 Correct 7 ms 9812 KB Output is correct
18 Correct 6 ms 9768 KB Output is correct
19 Correct 5 ms 9748 KB Output is correct
20 Correct 6 ms 9812 KB Output is correct
21 Correct 6 ms 9812 KB Output is correct
22 Correct 7 ms 9768 KB Output is correct
23 Incorrect 5 ms 9752 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9760 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9748 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 10 ms 9852 KB Output is correct
6 Correct 7 ms 9812 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Incorrect 6 ms 9684 KB Output isn't correct
10 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 15 ms 9768 KB Output is correct
5 Correct 26 ms 9776 KB Output is correct
6 Correct 6 ms 9724 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 7 ms 9812 KB Output is correct
9 Correct 62 ms 11212 KB Output is correct
10 Correct 50 ms 27980 KB Output is correct
11 Correct 10 ms 9684 KB Output is correct
12 Correct 43 ms 9784 KB Output is correct
13 Execution timed out 5058 ms 28992 KB Time limit exceeded
14 Halted 0 ms 0 KB -