oj.uz

Submission #598102

# Submission time Handle Problem Language Result Execution time Memory
598102 2022-07-17T15:07:29 Z dxz05 Jail (JOI22_jail) C++14
0 / 100
 5000 ms 30700 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;
            if (x == -1) g[i].push_back(j);
            if (y == -1) g[j].push_back(i);

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

            if (!ok) return false;
        }
    }

    return true;
}

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

    cout << (jail(n, m, S, T) ? "Yes" : "No") << endl;

}

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 16 ms 10008 KB Output is correct
5 Correct 27 ms 10400 KB Output is correct
6 Correct 7 ms 9812 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 8 ms 9812 KB Output is correct
9 Correct 66 ms 12452 KB Output is correct
10 Correct 51 ms 29380 KB Output is correct
11 Correct 11 ms 9812 KB Output is correct
12 Correct 48 ms 10644 KB Output is correct
13 Execution timed out 5034 ms 30700 KB Time limit exceeded
14 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 9740 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Incorrect 7 ms 9716 KB Output isn't correct
5 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 9740 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Incorrect 7 ms 9716 KB Output isn't correct
5 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 9740 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Incorrect 7 ms 9716 KB Output isn't correct
5 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 9740 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Incorrect 7 ms 9716 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Incorrect 7 ms 9684 KB Output isn't correct
3 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 16 ms 10008 KB Output is correct
5 Correct 27 ms 10400 KB Output is correct
6 Correct 7 ms 9812 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 8 ms 9812 KB Output is correct
9 Correct 66 ms 12452 KB Output is correct
10 Correct 51 ms 29380 KB Output is correct
11 Correct 11 ms 9812 KB Output is correct
12 Correct 48 ms 10644 KB Output is correct
13 Execution timed out 5034 ms 30700 KB Time limit exceeded
14 Halted 0 ms 0 KB -