답안 #601321

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
601321	2022-07-21T17:00:47 Z	dxz05	Jail (JOI22_jail)	C++14	5 / 100	1882 ms	172952 KB

jail

//#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #601321

Compilation message

Subtask #1 0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 0 / 16.0

Subtask #4 0 / 28.0

Subtask #5 0 / 12.0

Subtask #6 0 / 11.0

Subtask #7 0 / 23.0

Subtask #1
0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
0 / 16.0

Subtask #4
0 / 28.0

Subtask #5
0 / 12.0

Subtask #6
0 / 11.0

Subtask #7
0 / 23.0