oj.uz

Submission #601321

# Submission time Handle Problem Language Result Execution time Memory
601321 2022-07-21T17:00:47 Z dxz05 Jail (JOI22_jail) C++14
5 / 100
 1882 ms 172952 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);
    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;
    }

    int kk = min(5 * m, 20000000 / m);

    for (int i = 0; i < m; i++){
        for (int it = 0; it < kk; it++){
            int j = rng() % m;
            while (i == j) j = rng() % m;
            if (in(S[i], S[j], T[i])) gg[j].push_back(i);
            if (in(S[i], T[j], T[i])) gg[i].push_back(j);
        }
    }

    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 6 ms 9684 KB Output is correct
4 Correct 21 ms 9692 KB Output is correct
5 Correct 29 ms 9768 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 7 ms 9684 KB Output is correct
8 Correct 37 ms 10088 KB Output is correct
9 Correct 936 ms 20288 KB Output is correct
10 Correct 100 ms 35276 KB Output is correct
11 Correct 23 ms 9684 KB Output is correct
12 Correct 431 ms 10288 KB Output is correct
13 Correct 893 ms 28592 KB Output is correct
14 Correct 849 ms 28792 KB Output is correct
15 Correct 1607 ms 113172 KB Output is correct
16 Correct 1882 ms 116392 KB Output is correct
17 Correct 1528 ms 172952 KB Output is correct
18 Correct 836 ms 28756 KB Output is correct
19 Correct 1203 ms 69916 KB Output is correct
20 Incorrect 1224 ms 70040 KB Output isn't correct
21 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 6 ms 9688 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 7 ms 9784 KB Output is correct
5 Correct 6 ms 9688 KB Output is correct
6 Correct 8 ms 9672 KB Output is correct
7 Correct 7 ms 9684 KB Output is correct
8 Correct 8 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9788 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 6 ms 9684 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 6 ms 9688 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 7 ms 9784 KB Output is correct
5 Correct 6 ms 9688 KB Output is correct
6 Correct 8 ms 9672 KB Output is correct
7 Correct 7 ms 9684 KB Output is correct
8 Correct 8 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9788 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 6 ms 9684 KB Output is correct
14 Correct 6 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 6 ms 9684 KB Output is correct
17 Correct 8 ms 9684 KB Output is correct
18 Correct 9 ms 9684 KB Output is correct
19 Correct 6 ms 9684 KB Output is correct
20 Correct 10 ms 9684 KB Output is correct
21 Correct 7 ms 9684 KB Output is correct
22 Incorrect 8 ms 9684 KB Output isn't correct
23 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 6 ms 9688 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 7 ms 9784 KB Output is correct
5 Correct 6 ms 9688 KB Output is correct
6 Correct 8 ms 9672 KB Output is correct
7 Correct 7 ms 9684 KB Output is correct
8 Correct 8 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9788 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 6 ms 9684 KB Output is correct
14 Correct 6 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 6 ms 9684 KB Output is correct
17 Correct 8 ms 9684 KB Output is correct
18 Correct 9 ms 9684 KB Output is correct
19 Correct 6 ms 9684 KB Output is correct
20 Correct 10 ms 9684 KB Output is correct
21 Correct 7 ms 9684 KB Output is correct
22 Incorrect 8 ms 9684 KB Output isn't correct
23 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 6 ms 9688 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 7 ms 9784 KB Output is correct
5 Correct 6 ms 9688 KB Output is correct
6 Correct 8 ms 9672 KB Output is correct
7 Correct 7 ms 9684 KB Output is correct
8 Correct 8 ms 9684 KB Output is correct
9 Correct 6 ms 9684 KB Output is correct
10 Correct 6 ms 9788 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 6 ms 9684 KB Output is correct
14 Correct 6 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 6 ms 9684 KB Output is correct
17 Correct 8 ms 9684 KB Output is correct
18 Correct 9 ms 9684 KB Output is correct
19 Correct 6 ms 9684 KB Output is correct
20 Correct 10 ms 9684 KB Output is correct
21 Correct 7 ms 9684 KB Output is correct
22 Incorrect 8 ms 9684 KB Output isn't correct
23 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 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 23 ms 9780 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 8 ms 9684 KB Output is correct
8 Correct 7 ms 9768 KB Output is correct
9 Correct 7 ms 9684 KB Output is correct
10 Correct 7 ms 9684 KB Output is correct
11 Correct 8 ms 9684 KB Output is correct
12 Incorrect 542 ms 9908 KB Output isn't correct
13 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 6 ms 9684 KB Output is correct
4 Correct 21 ms 9692 KB Output is correct
5 Correct 29 ms 9768 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 7 ms 9684 KB Output is correct
8 Correct 37 ms 10088 KB Output is correct
9 Correct 936 ms 20288 KB Output is correct
10 Correct 100 ms 35276 KB Output is correct
11 Correct 23 ms 9684 KB Output is correct
12 Correct 431 ms 10288 KB Output is correct
13 Correct 893 ms 28592 KB Output is correct
14 Correct 849 ms 28792 KB Output is correct
15 Correct 1607 ms 113172 KB Output is correct
16 Correct 1882 ms 116392 KB Output is correct
17 Correct 1528 ms 172952 KB Output is correct
18 Correct 836 ms 28756 KB Output is correct
19 Correct 1203 ms 69916 KB Output is correct
20 Incorrect 1224 ms 70040 KB Output isn't correct
21 Halted 0 ms 0 KB -