oj.uz

Submission #1057031

# Submission time Handle Problem Language Result Execution time Memory
1057031 2024-08-13T13:28:35 Z Boas Jail (JOI22_jail) C++17
61 / 100
 133 ms 335876 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

template <typename T1, typename T2>
using indexed_map = tree<T1, T2, less<T1>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using indexed_set = indexed_map<T, null_type>;

#define loop(x, i) for (int i = 0; i < (x); i++)
#define loop1(x, i) for (int i = 1; i <= (x); i++)
#define rev(x, i) for (int i = (int)(x) - 1; i >= 0; i--)
#define itloop(x) for (auto it = begin(x); x != end(x); it++)
#define itrev(x) for (auto it = rbegin(x); x != rend(x); it++)
#define int long long
#define INF ((int64_t)(4e18 + 1))
#define INF32 ((int32_t)(2e9 + 1))
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define existsIn(x, l) (count(ALL(l), x) > 0)
#define removeIn(x, l) l.erase(find(ALL(l), x))
#define pb push_back
#define sz(x) (int)(x).size()
#define F first
#define S second
#define var const auto &
#define foreach(l) for (var e : l)

typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vii> vvii;
typedef vector<viii> vviii;
typedef set<int> si;
typedef set<ii> sii;
typedef set<iii> siii;
typedef vector<si> vsi;
typedef vector<sii> vsii;
typedef vector<vsi> vvsi;
typedef vector<string> vstr;
typedef vector<vector<string>> vvstr;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vi::iterator viit;
typedef si::iterator siit;
typedef int8_t in8;
typedef int16_t in16;
typedef int32_t in32;
typedef int64_t in64;

typedef bitset<500> bs;
typedef vector<bs> vbs;
typedef vector<vbs> vvbs;

void solve()
{
    int n, m;
    cin >> n;
    vvi adj(n);
    loop(n - 1, i)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    cin >> m;
    if (m > 500)
        throw;
    // vi mIx(n);
    vvbs bedRooms(20, vbs(n));
    vvbs workRooms(20, vbs(n));
    vvi p(20, vi(n));
    vi s(m), t(m), d(n);
    loop(m, i)
    {
        cin >> s[i] >> t[i];
        s[i]--;
        t[i]--;
        // mIx[s[i]] = i;
        bedRooms[0][s[i]][i] = 1;
        workRooms[0][t[i]][i] = 1;
    }
    auto dfs = [&](auto &&self, int i, int prev) -> void
    {
        for (int j : adj[i])
        {
            if (j == prev)
                continue;
            d[j] = d[i] + 1;
            p[0][j] = i;
            self(self, j, i);
        }
    };
    dfs(dfs, 0, 0);
    loop1(19, x)
    {
        loop(n, i)
        {
            int half = p[x - 1][i];
            p[x][i] = p[x - 1][half];
            bedRooms[x][i] = bedRooms[x - 1][i] | bedRooms[x - 1][half];
            workRooms[x][i] = workRooms[x - 1][i] | workRooms[x - 1][half];
        }
    }
    typedef tuple<int, bs, bs> ibs;
    auto getParent = [&](int i, int k) -> ibs
    {
        bs bedrms;
        bs workrms;
        loop(20, x)
        {
            if ((1 << x) & k)
            {
                bedrms |= bedRooms[x][i];
                workrms |= workRooms[x][i];
                i = p[x][i];
            }
        }
        // bedrms |= bedRooms[0][i];
        return {i, bedrms, workrms};
    };
    auto LCA = [&](int A, int b) -> ibs
    {
        if (d[A] - d[b] < 0)
            swap(A, b);
        auto [a, bedrms, workrms] = getParent(A, d[A] - d[b]);
        if (a == b)
        {
            bedrms |= bedRooms[0][a];
            workrms |= workRooms[0][a];
            return {a, bedrms, workrms};
        }
        rev(20, x)
        {
            if (p[x][a] != p[x][b])
            {
                bedrms |= bedRooms[x][a];
                bedrms |= bedRooms[x][b];
                workrms |= workRooms[x][a];
                workrms |= workRooms[x][b];
                a = p[x][a];
                b = p[x][b];
            }
        }
        bedrms |= bedRooms[1][a];   // voor de laatste erbij
        workrms |= workRooms[1][a]; // voor de laatste erbij
        bedrms |= bedRooms[0][b];
        workrms |= workRooms[0][b];
        return {p[0][a], bedrms, workrms};
    };
    int done = 0;
    vvi inPad(m);
    vi ervoor(m);
    loop(m, i)
    {
        auto [lca, bedrms, workrms] = LCA(s[i], t[i]);
        for (int j = bedrms._Find_first(); j < 500; j = bedrms._Find_next(j))
        {
            if (j == i)
                continue;
            if (workrms[j])
            {
                cout << "No" << endl;
                return;
            }
            ervoor[i]++;
            inPad[j].pb(i);
        }
        for (int j = workrms._Find_first(); j < 500; j = workrms._Find_next(j))
        {
            if (j == i)
                continue;
            ervoor[j]++;
            inPad[i].pb(j);
        }
    }
    stack<int> q;
    loop(m, i)
    {
        if (ervoor[i] == 0)
            q.push(i);
    }
    while (!q.empty())
    {
        int i = q.top();
        q.pop();
        done++;
        for (int j : inPad[i])
        {
            ervoor[j]--;
            if (ervoor[j] == 0)
            {
                q.push(j);
            }
        }
    }
    if (done == m)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 36 ms 796 KB Output is correct
5 Correct 78 ms 804 KB Output is correct
6 Correct 4 ms 1140 KB Output is correct
7 Correct 4 ms 1132 KB Output is correct
8 Correct 4 ms 1116 KB Output is correct
9 Correct 101 ms 19760 KB Output is correct
10 Correct 109 ms 334340 KB Output is correct
11 Correct 16 ms 344 KB Output is correct
12 Correct 77 ms 832 KB Output is correct
13 Runtime error 21 ms 13916 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -

Subtask #2
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 5 ms 1160 KB Output is correct
4 Correct 4 ms 1144 KB Output is correct
5 Correct 4 ms 1168 KB Output is correct
6 Correct 4 ms 1184 KB Output is correct
7 Correct 4 ms 1172 KB Output is correct
8 Correct 4 ms 1168 KB Output is correct
9 Correct 5 ms 1184 KB Output is correct
10 Correct 4 ms 1188 KB Output is correct
11 Correct 4 ms 1164 KB Output is correct
12 Correct 3 ms 1168 KB Output is correct
13 Correct 3 ms 1156 KB Output is correct

Subtask #3
16.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 5 ms 1160 KB Output is correct
4 Correct 4 ms 1144 KB Output is correct
5 Correct 4 ms 1168 KB Output is correct
6 Correct 4 ms 1184 KB Output is correct
7 Correct 4 ms 1172 KB Output is correct
8 Correct 4 ms 1168 KB Output is correct
9 Correct 5 ms 1184 KB Output is correct
10 Correct 4 ms 1188 KB Output is correct
11 Correct 4 ms 1164 KB Output is correct
12 Correct 3 ms 1168 KB Output is correct
13 Correct 3 ms 1156 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 4 ms 1176 KB Output is correct
17 Correct 4 ms 1168 KB Output is correct
18 Correct 4 ms 1184 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 5 ms 1168 KB Output is correct
21 Correct 6 ms 1168 KB Output is correct
22 Correct 5 ms 1164 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 4 ms 1144 KB Output is correct
26 Correct 1 ms 1140 KB Output is correct
27 Correct 5 ms 1164 KB Output is correct
28 Correct 1 ms 348 KB Output is correct

Subtask #4
28.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 5 ms 1160 KB Output is correct
4 Correct 4 ms 1144 KB Output is correct
5 Correct 4 ms 1168 KB Output is correct
6 Correct 4 ms 1184 KB Output is correct
7 Correct 4 ms 1172 KB Output is correct
8 Correct 4 ms 1168 KB Output is correct
9 Correct 5 ms 1184 KB Output is correct
10 Correct 4 ms 1188 KB Output is correct
11 Correct 4 ms 1164 KB Output is correct
12 Correct 3 ms 1168 KB Output is correct
13 Correct 3 ms 1156 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 4 ms 1176 KB Output is correct
17 Correct 4 ms 1168 KB Output is correct
18 Correct 4 ms 1184 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 5 ms 1168 KB Output is correct
21 Correct 6 ms 1168 KB Output is correct
22 Correct 5 ms 1164 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 4 ms 1144 KB Output is correct
26 Correct 1 ms 1140 KB Output is correct
27 Correct 5 ms 1164 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 4 ms 1116 KB Output is correct
30 Correct 3 ms 1116 KB Output is correct
31 Correct 3 ms 1116 KB Output is correct
32 Correct 3 ms 1116 KB Output is correct
33 Correct 4 ms 1176 KB Output is correct
34 Correct 3 ms 860 KB Output is correct
35 Correct 3 ms 976 KB Output is correct
36 Correct 3 ms 1064 KB Output is correct
37 Correct 3 ms 1060 KB Output is correct

Subtask #5
12.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 5 ms 1160 KB Output is correct
4 Correct 4 ms 1144 KB Output is correct
5 Correct 4 ms 1168 KB Output is correct
6 Correct 4 ms 1184 KB Output is correct
7 Correct 4 ms 1172 KB Output is correct
8 Correct 4 ms 1168 KB Output is correct
9 Correct 5 ms 1184 KB Output is correct
10 Correct 4 ms 1188 KB Output is correct
11 Correct 4 ms 1164 KB Output is correct
12 Correct 3 ms 1168 KB Output is correct
13 Correct 3 ms 1156 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 4 ms 1176 KB Output is correct
17 Correct 4 ms 1168 KB Output is correct
18 Correct 4 ms 1184 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 5 ms 1168 KB Output is correct
21 Correct 6 ms 1168 KB Output is correct
22 Correct 5 ms 1164 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 4 ms 1144 KB Output is correct
26 Correct 1 ms 1140 KB Output is correct
27 Correct 5 ms 1164 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 4 ms 1116 KB Output is correct
30 Correct 3 ms 1116 KB Output is correct
31 Correct 3 ms 1116 KB Output is correct
32 Correct 3 ms 1116 KB Output is correct
33 Correct 4 ms 1176 KB Output is correct
34 Correct 3 ms 860 KB Output is correct
35 Correct 3 ms 976 KB Output is correct
36 Correct 3 ms 1064 KB Output is correct
37 Correct 3 ms 1060 KB Output is correct
38 Correct 104 ms 20940 KB Output is correct
39 Correct 109 ms 335876 KB Output is correct
40 Correct 128 ms 18244 KB Output is correct
41 Correct 132 ms 18152 KB Output is correct
42 Correct 125 ms 18448 KB Output is correct
43 Correct 128 ms 18088 KB Output is correct
44 Correct 17 ms 3540 KB Output is correct
45 Correct 123 ms 330244 KB Output is correct
46 Correct 117 ms 330244 KB Output is correct
47 Correct 109 ms 332440 KB Output is correct
48 Correct 108 ms 332292 KB Output is correct
49 Correct 113 ms 330308 KB Output is correct
50 Correct 115 ms 330368 KB Output is correct
51 Correct 105 ms 331012 KB Output is correct
52 Correct 104 ms 330812 KB Output is correct
53 Correct 25 ms 23132 KB Output is correct
54 Correct 133 ms 330956 KB Output is correct

Subtask #6
0 / 11.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 0 ms 348 KB Output is correct
5 Correct 14 ms 348 KB Output is correct
6 Correct 3 ms 1156 KB Output is correct
7 Correct 3 ms 1164 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 3 ms 1064 KB Output is correct
13 Correct 40 ms 1288 KB Output is correct
14 Correct 67 ms 1564 KB Output is correct
15 Correct 53 ms 1300 KB Output is correct
16 Runtime error 22 ms 16988 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 36 ms 796 KB Output is correct
5 Correct 78 ms 804 KB Output is correct
6 Correct 4 ms 1140 KB Output is correct
7 Correct 4 ms 1132 KB Output is correct
8 Correct 4 ms 1116 KB Output is correct
9 Correct 101 ms 19760 KB Output is correct
10 Correct 109 ms 334340 KB Output is correct
11 Correct 16 ms 344 KB Output is correct
12 Correct 77 ms 832 KB Output is correct
13 Runtime error 21 ms 13916 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -