oj.uz

답안 #598077

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
598077 2022-07-17T14:10:53 Z dxz05 Jail (JOI22_jail) C++14
5 / 100
 5000 ms 25400 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);
}

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 == y) continue;

            if (x == S[i] && y == T[j]) continue;
            if (x == T[i] && y == S[j]) continue;
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5044 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 13 ms 5332 KB Output is correct
5 Correct 26 ms 5700 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 4 ms 5076 KB Output is correct
8 Correct 5 ms 5036 KB Output is correct
9 Correct 61 ms 7064 KB Output is correct
10 Correct 65 ms 24016 KB Output is correct
11 Correct 10 ms 5204 KB Output is correct
12 Correct 37 ms 5952 KB Output is correct
13 Execution timed out 5062 ms 25400 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 5 ms 5052 KB Output is correct
4 Correct 4 ms 5056 KB Output is correct
5 Correct 5 ms 5048 KB Output is correct
6 Correct 4 ms 5056 KB Output is correct
7 Correct 4 ms 5076 KB Output is correct
8 Correct 5 ms 5076 KB Output is correct
9 Correct 5 ms 5060 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 4 ms 5052 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 3 ms 5060 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 5 ms 5052 KB Output is correct
4 Correct 4 ms 5056 KB Output is correct
5 Correct 5 ms 5048 KB Output is correct
6 Correct 4 ms 5056 KB Output is correct
7 Correct 4 ms 5076 KB Output is correct
8 Correct 5 ms 5076 KB Output is correct
9 Correct 5 ms 5060 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 4 ms 5052 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 3 ms 5060 KB Output is correct
14 Incorrect 3 ms 5040 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 5 ms 5052 KB Output is correct
4 Correct 4 ms 5056 KB Output is correct
5 Correct 5 ms 5048 KB Output is correct
6 Correct 4 ms 5056 KB Output is correct
7 Correct 4 ms 5076 KB Output is correct
8 Correct 5 ms 5076 KB Output is correct
9 Correct 5 ms 5060 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 4 ms 5052 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 3 ms 5060 KB Output is correct
14 Incorrect 3 ms 5040 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 5 ms 5052 KB Output is correct
4 Correct 4 ms 5056 KB Output is correct
5 Correct 5 ms 5048 KB Output is correct
6 Correct 4 ms 5056 KB Output is correct
7 Correct 4 ms 5076 KB Output is correct
8 Correct 5 ms 5076 KB Output is correct
9 Correct 5 ms 5060 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 4 ms 5052 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 3 ms 5060 KB Output is correct
14 Incorrect 3 ms 5040 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5044 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 13 ms 5332 KB Output is correct
5 Correct 26 ms 5700 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 4 ms 5076 KB Output is correct
8 Correct 5 ms 5036 KB Output is correct
9 Correct 61 ms 7064 KB Output is correct
10 Correct 65 ms 24016 KB Output is correct
11 Correct 10 ms 5204 KB Output is correct
12 Correct 37 ms 5952 KB Output is correct
13 Execution timed out 5062 ms 25400 KB Time limit exceeded
14 Halted 0 ms 0 KB -