oj.uz

답안 #1053603

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1053603 2024-08-11T14:14:13 Z j_vdd16 Jail (JOI22_jail) C++17
0 / 100
 5000 ms 28448 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
*/

    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);
        vvi 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)) {
                    out[j].push_back(i);
                    inDegree[i]++;

                    if (isOnSimplePath(s2, s1, t1)) containSuccess = false;
                }
                if (isOnSimplePath(s2, s1, t1)) {
                    out[i].push_back(j);
                    inDegree[j]++;
                }
                // if (isOnSimplePath(t1, s2, t2)) {
                //     out[i].push_back(j);
                //     inDegree[j]++;

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

        }

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

# 결과 실행 시간 메모리 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 8 ms 348 KB Output is correct
5 Correct 18 ms 504 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 8 ms 536 KB Output is correct
9 Correct 178 ms 2984 KB Output is correct
10 Correct 32 ms 27224 KB Output is correct
11 Correct 10 ms 348 KB Output is correct
12 Correct 110 ms 576 KB Output is correct
13 Execution timed out 5005 ms 28448 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 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 9 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 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

# 결과 실행 시간 메모리 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 8 ms 348 KB Output is correct
5 Correct 18 ms 504 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 8 ms 536 KB Output is correct
9 Correct 178 ms 2984 KB Output is correct
10 Correct 32 ms 27224 KB Output is correct
11 Correct 10 ms 348 KB Output is correct
12 Correct 110 ms 576 KB Output is correct
13 Execution timed out 5005 ms 28448 KB Time limit exceeded
14 Halted 0 ms 0 KB -