oj.uz

Submission #1053632

# Submission time Handle Problem Language Result Execution time Memory
1053632 2024-08-11T14:41:31 Z j_vdd16 Jail (JOI22_jail) C++17
0 / 100
 5000 ms 32020 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 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;


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

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

    inOut[node].first = counter++;

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

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

    inOut[node].second = counter++;
}

constexpr int POW = 20;
vi lift[POW];

bool isAncestor(int a, int b) {
    return inOut[a].first <= inOut[b].first && inOut[b].first <= inOut[a].second;
}
bool isBetween(int node, int a, int b) {
    return isAncestor(a, node) && isAncestor(node, b);
}
int getLCA(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);

    int todo = depth[a] - depth[b];
    loop(pow, POW) {
        if (todo & (1 << pow)) {
            a = lift[pow][a];
        }
    }

    if (a == b) return a;

    for (int pow = POW - 1; pow >= 0; pow--) {
        if (lift[pow][a] == lift[pow][a]) continue;

        a = lift[pow][a];
        b = lift[pow][b];
    }

    return lift[0][a];
}
bool isOnSimplePath(int node, int a, int b) {
    int lca = getLCA(a, b);

    bool result = isBetween(node, lca, a) || isBetween(node, lca, b);
    return result;
}

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
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
2
1 5
5 3

1
4
1 2
1 3
1 4
3
2 3
3 4
4 2

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

    int q;
    cin >> q;

    while (q--) {
        cin >> n;

        counter = 0;
        adj = vvi(n);
        depth = vi(n);
        parent = vi(n);
        inOut = vii(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);

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

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

        for (int pow = 1; pow < POW; pow++) {
            loop(j, n) {
                int next = lift[pow - 1][j];
                lift[pow][j] = lift[pow - 1][next];
            }
        }

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

            routes.push_back({s, t});
        }
        sort(all(routes));

        bool containSuccess = true;
        vi inDegree(m);
        vector<set<int>> out(m);
        loop(i, m) {
            auto [s1, t1] = routes[i];

            loop(j, m) {
                auto [s2, t2] = routes[j];
                if (i == j) continue;
                
                //if (s1 < s2 && t1 > t2) containSuccess = false;
                //if (min(s1, t1) <= min(s2, t2) && max(s2, t2) <= max(s1, t1)) containSuccess = false;
                //if (min(s1, t1) <= t2 && t2 <= max(s1, t1) && min(s2, t2) <= t1 && t1 <= max(s2, t2)) containSuccess = false;

                if (isOnSimplePath(t2, s1, t1)) {
                    if (!out[i].count(j)) {
                        out[i].insert(j);
                        inDegree[j]++;
                    }

                    if (isOnSimplePath(s2, s1, t1)) containSuccess = false;
                }
                if (isOnSimplePath(s2, s1, t1)) {
                    if (!out[j].count(i)) {
                        out[j].insert(i);
                        inDegree[i]++;
                    }
                }

                //if (isOnSimplePath(s1, s2, t2) && isOnSimplePath(t1, s2, t2)) containSuccess = false;
            }

        }

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

        int count = 0;
        vb vis(m);
        while (startingPoints.size()) {
            int node = startingPoints.top();
            startingPoints.pop();

            if (vis[node]) continue;
            vis[node] = true;

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


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

        if (testSuccess) {
            cerr << "Yes (first subtask only)" << endl;
        }
        else {
            cerr << "No (first subtask only)" << endl;
        }
        if (!containSuccess || count != m) {
            cout << "No" << endl;
        }
        else {
            cout << "Yes" << endl;
        }
    }

	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 8 ms 348 KB Output is correct
5 Correct 17 ms 500 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 11 ms 712 KB Output is correct
9 Correct 316 ms 8728 KB Output is correct
10 Correct 42 ms 31572 KB Output is correct
11 Correct 10 ms 348 KB Output is correct
12 Correct 187 ms 852 KB Output is correct
13 Execution timed out 5073 ms 32020 KB Time limit exceeded
14 Halted 0 ms 0 KB -

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 348 KB Output is correct
4 Incorrect 1 ms 348 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 348 KB Output is correct
4 Incorrect 1 ms 348 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 348 KB Output is correct
4 Incorrect 1 ms 348 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 348 KB Output is correct
4 Incorrect 1 ms 348 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 11 ms 508 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 8 ms 348 KB Output is correct
5 Correct 17 ms 500 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 11 ms 712 KB Output is correct
9 Correct 316 ms 8728 KB Output is correct
10 Correct 42 ms 31572 KB Output is correct
11 Correct 10 ms 348 KB Output is correct
12 Correct 187 ms 852 KB Output is correct
13 Execution timed out 5073 ms 32020 KB Time limit exceeded
14 Halted 0 ms 0 KB -