oj.uz

Submission #1053486

# Submission time Handle Problem Language Result Execution time Memory
1053486 2024-08-11T12:27:58 Z j_vdd16 Jail (JOI22_jail) C++17
5 / 100
 68 ms 86984 KB 
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

typedef uint64_t u64;
typedef int64_t i64;

int n, m;
vvi adj;
vi depth;
vi parent;

void dfs(int node, int p, int d) {
    depth[node] = d;

    for (int child : adj[node]) {
        if (child == p) continue;

        parent[child] = node;
        dfs(child, node, d + 1);
    }
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

    /*
1
7
1 2
2 3
3 4
4 5
5 6
6 7
3
1 3
4 2
2 5
    */

/*
1
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
3
1 4
2 5
3 6
*/

    int q;
    cin >> q;

    constexpr int POW = 20;
    while (q--) {
        cin >> n;

        adj = vvi(n);
        depth = vi(n);
        parent = vi(n);
        loop(i, n - 1) {
            int a, b;
            cin >> a >> b;
            a--; b--;

            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        dfs(0, -1, 0);

        vi lift[POW] = {};
        vvi endPointLift[POW] = {};
        loop(i, POW) {
            lift[i] = vi(n);
            endPointLift[i] = vvi(n);
        }

        loop(i, n) lift[0][i] = parent[i];

        vii routes;
        cin >> m;
        loop(i, m) {
            int s, t;
            cin >> s >> t;
            s--; t--;

            routes.push_back({s, t});
            endPointLift[0][t].push_back(i);
        }

        // for (int i = 1; i < POW; i++) {
        //     loop(j, n) {
        //         endPointLift[i][j] = endPointLift[i - 1][j];

        //         int next = lift[i - 1][j];
        //         lift[i][j] = lift[i - 1][next];

        //         //if (next == 0) continue;

        //         for (int x : endPointLift[i - 1][next]) {
        //             endPointLift[i][j].push_back(x);
        //         }
        //     }
        // }

        // vi inDegree(n);
        // vector<set<int>> out(n);
        // loop(i, m) {
        //     auto [s, t] = routes[i];

        //     vi endPointsOnRoute;
        //     if (depth[s] < depth[t]) swap(s, t);

        //     int todo = depth[s] - depth[t];
        //     loop(j, POW) {
        //         if (todo & (1 << j)) {
        //             for (int x : endPointLift[j][s]) endPointsOnRoute.push_back(x);

        //             s = lift[j][s];
        //         }
        //     }

        //     for (int j = POW - 1; j >= 0; j--) {
        //         if (lift[j][s] == lift[j][t]) continue;

        //         for (int x : endPointLift[j][s]) endPointsOnRoute.push_back(x);
        //         for (int x : endPointLift[j][t]) endPointsOnRoute.push_back(x);

        //         s = lift[j][s];
        //         t = lift[j][t];
        //     }

        //     if (s == t) {
        //         for (int x : endPointLift[0][s]) endPointsOnRoute.push_back(x);
        //     }
        //     else {
        //         for (int x : endPointLift[1][s]) endPointsOnRoute.push_back(x);
        //         for (int x : endPointLift[0][t]) endPointsOnRoute.push_back(x);
        //     }

        //     cerr << "I = " << i << ": ";
        //     for (int x : endPointsOnRoute) {
        //         if (x == i) continue;
        //         cerr << x << ' ';

        //         inDegree[x]++;
        //         out[i].insert(x);
        //     }
        //     cerr << endl;
        // }

        // stack<int> startingPoints;
        // loop(i, m) {
        //     if (inDegree[i] == 0) startingPoints.push(i);
        // }

        // int count = 0;
        // while (startingPoints.size()) {
        //     int node = startingPoints.top();
        //     startingPoints.pop();

        //     count++;
        //     for (int child : out[node]) {
        //         inDegree[child]--;
        //         if (inDegree[child] == 0) startingPoints.push(child);
        //     }
        // }

        

        bool success = true;
        sort(all(routes));
        int prev = 0;
        for (auto [s, t] : routes) {
            if (t < prev) {
                success = false;
            }
            
            prev = t;
        }

        if (/*count == m*/success) {
            cout << "Yes" << endl;
        }
        else {
            cout << "No" << endl;
        }
    }

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 9 ms 860 KB Output is correct
5 Correct 18 ms 1160 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 22 ms 5708 KB Output is correct
10 Correct 44 ms 80724 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 23 ms 1372 KB Output is correct
13 Correct 46 ms 83368 KB Output is correct
14 Correct 48 ms 83404 KB Output is correct
15 Correct 57 ms 83404 KB Output is correct
16 Correct 68 ms 86884 KB Output is correct
17 Correct 49 ms 83916 KB Output is correct
18 Correct 59 ms 86984 KB Output is correct
19 Correct 50 ms 83916 KB Output is correct
20 Correct 48 ms 83916 KB Output is correct
21 Correct 55 ms 83916 KB Output is correct
22 Correct 49 ms 83916 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Incorrect 1 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Incorrect 1 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Incorrect 1 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Incorrect 1 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 5 ms 604 KB Output is correct
6 Incorrect 1 ms 604 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 9 ms 860 KB Output is correct
5 Correct 18 ms 1160 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 22 ms 5708 KB Output is correct
10 Correct 44 ms 80724 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 23 ms 1372 KB Output is correct
13 Correct 46 ms 83368 KB Output is correct
14 Correct 48 ms 83404 KB Output is correct
15 Correct 57 ms 83404 KB Output is correct
16 Correct 68 ms 86884 KB Output is correct
17 Correct 49 ms 83916 KB Output is correct
18 Correct 59 ms 86984 KB Output is correct
19 Correct 50 ms 83916 KB Output is correct
20 Correct 48 ms 83916 KB Output is correct
21 Correct 55 ms 83916 KB Output is correct
22 Correct 49 ms 83916 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Incorrect 1 ms 604 KB Output isn't correct
27 Halted 0 ms 0 KB -