oj.uz

Submission #598103

# Submission time Handle Problem Language Result Execution time Memory
598103 2022-07-17T15:09:08 Z dxz05 Jail (JOI22_jail) C++14
5 / 100
 5000 ms 28824 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){
                g[i].push_back(j);
                ok = true;
            }
            if (y == -1){
                g[j].push_back(i);
                ok = true;
            }

            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 15 ms 9684 KB Output is correct
5 Correct 28 ms 9684 KB Output is correct
6 Correct 7 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 8 ms 9812 KB Output is correct
9 Correct 60 ms 11196 KB Output is correct
10 Correct 52 ms 27980 KB Output is correct
11 Correct 11 ms 9684 KB Output is correct
12 Correct 39 ms 9684 KB Output is correct
13 Execution timed out 5060 ms 28824 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 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 6 ms 9724 KB Output is correct
7 Correct 6 ms 9752 KB Output is correct
8 Correct 7 ms 9736 KB Output is correct
9 Correct 7 ms 9812 KB Output is correct
10 Correct 7 ms 9748 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 6 ms 9748 KB Output is correct
13 Correct 5 ms 9744 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 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 6 ms 9724 KB Output is correct
7 Correct 6 ms 9752 KB Output is correct
8 Correct 7 ms 9736 KB Output is correct
9 Correct 7 ms 9812 KB Output is correct
10 Correct 7 ms 9748 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 6 ms 9748 KB Output is correct
13 Correct 5 ms 9744 KB Output is correct
14 Incorrect 5 ms 9684 KB Output isn't correct
15 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 6 ms 9684 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 6 ms 9724 KB Output is correct
7 Correct 6 ms 9752 KB Output is correct
8 Correct 7 ms 9736 KB Output is correct
9 Correct 7 ms 9812 KB Output is correct
10 Correct 7 ms 9748 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 6 ms 9748 KB Output is correct
13 Correct 5 ms 9744 KB Output is correct
14 Incorrect 5 ms 9684 KB Output isn't correct
15 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 6 ms 9684 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 6 ms 9724 KB Output is correct
7 Correct 6 ms 9752 KB Output is correct
8 Correct 7 ms 9736 KB Output is correct
9 Correct 7 ms 9812 KB Output is correct
10 Correct 7 ms 9748 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 6 ms 9748 KB Output is correct
13 Correct 5 ms 9744 KB Output is correct
14 Incorrect 5 ms 9684 KB Output isn't correct
15 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 Incorrect 5 ms 9652 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 15 ms 9684 KB Output is correct
5 Correct 28 ms 9684 KB Output is correct
6 Correct 7 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 8 ms 9812 KB Output is correct
9 Correct 60 ms 11196 KB Output is correct
10 Correct 52 ms 27980 KB Output is correct
11 Correct 11 ms 9684 KB Output is correct
12 Correct 39 ms 9684 KB Output is correct
13 Execution timed out 5060 ms 28824 KB Time limit exceeded
14 Halted 0 ms 0 KB -