oj.uz

답안 #598119

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
598119 2022-07-17T16:25:01 Z dxz05 Jail (JOI22_jail) C++14
5 / 100
 5000 ms 29104 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];
inline 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 == y){
                if (x == S[i]) gg[i].push_back(j); else
                    gg[j].push_back(i);
                ok = true;
            }

            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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9860 KB Output is correct
2 Correct 6 ms 9664 KB Output is correct
3 Correct 6 ms 9648 KB Output is correct
4 Correct 22 ms 9684 KB Output is correct
5 Correct 30 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9768 KB Output is correct
8 Correct 8 ms 9772 KB Output is correct
9 Correct 65 ms 11212 KB Output is correct
10 Correct 72 ms 27960 KB Output is correct
11 Correct 11 ms 9772 KB Output is correct
12 Correct 48 ms 9784 KB Output is correct
13 Execution timed out 5006 ms 29104 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9760 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 7 ms 9720 KB Output is correct
6 Correct 6 ms 9788 KB Output is correct
7 Correct 7 ms 9796 KB Output is correct
8 Correct 9 ms 9684 KB Output is correct
9 Correct 7 ms 9684 KB Output is correct
10 Correct 8 ms 9684 KB Output is correct
11 Correct 8 ms 9684 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9760 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 7 ms 9720 KB Output is correct
6 Correct 6 ms 9788 KB Output is correct
7 Correct 7 ms 9796 KB Output is correct
8 Correct 9 ms 9684 KB Output is correct
9 Correct 7 ms 9684 KB Output is correct
10 Correct 8 ms 9684 KB Output is correct
11 Correct 8 ms 9684 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 5 ms 9684 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 9684 KB Output is correct
17 Correct 7 ms 9684 KB Output is correct
18 Correct 7 ms 9684 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 7 ms 9684 KB Output is correct
21 Correct 6 ms 9684 KB Output is correct
22 Correct 8 ms 9684 KB Output is correct
23 Incorrect 7 ms 9656 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9760 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 7 ms 9720 KB Output is correct
6 Correct 6 ms 9788 KB Output is correct
7 Correct 7 ms 9796 KB Output is correct
8 Correct 9 ms 9684 KB Output is correct
9 Correct 7 ms 9684 KB Output is correct
10 Correct 8 ms 9684 KB Output is correct
11 Correct 8 ms 9684 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 5 ms 9684 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 9684 KB Output is correct
17 Correct 7 ms 9684 KB Output is correct
18 Correct 7 ms 9684 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 7 ms 9684 KB Output is correct
21 Correct 6 ms 9684 KB Output is correct
22 Correct 8 ms 9684 KB Output is correct
23 Incorrect 7 ms 9656 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9760 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 7 ms 9720 KB Output is correct
6 Correct 6 ms 9788 KB Output is correct
7 Correct 7 ms 9796 KB Output is correct
8 Correct 9 ms 9684 KB Output is correct
9 Correct 7 ms 9684 KB Output is correct
10 Correct 8 ms 9684 KB Output is correct
11 Correct 8 ms 9684 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 5 ms 9684 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 9684 KB Output is correct
17 Correct 7 ms 9684 KB Output is correct
18 Correct 7 ms 9684 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 7 ms 9684 KB Output is correct
21 Correct 6 ms 9684 KB Output is correct
22 Correct 8 ms 9684 KB Output is correct
23 Incorrect 7 ms 9656 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9732 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 10 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9756 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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9860 KB Output is correct
2 Correct 6 ms 9664 KB Output is correct
3 Correct 6 ms 9648 KB Output is correct
4 Correct 22 ms 9684 KB Output is correct
5 Correct 30 ms 9684 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9768 KB Output is correct
8 Correct 8 ms 9772 KB Output is correct
9 Correct 65 ms 11212 KB Output is correct
10 Correct 72 ms 27960 KB Output is correct
11 Correct 11 ms 9772 KB Output is correct
12 Correct 48 ms 9784 KB Output is correct
13 Execution timed out 5006 ms 29104 KB Time limit exceeded
14 Halted 0 ms 0 KB -