54012023-05-12 15:55:28szilSzéfnyitáscpp14Hibás válasz 23/1008ms6336 KiB
#include <bits/stdc++.h>

using ll = long long;
using namespace std;
const ll INF = 1e18;

const int MAXN = 151;

int a[MAXN];
int s[MAXN][2], s2[50001][2], b[50001];
bool bits[MAXN];

int timer;
struct Node {
    Node *p[2] = {nullptr, nullptr};
    int u = -1, t;
};

Node *root;

void add(vector<int> &v, int u) {
    Node *ptr = root;
    for (int i : v) {
        if (ptr->p[i] == nullptr) {
            ptr->p[i] = new Node();
            ptr->p[i]->t = timer++;
        }
        ptr = ptr->p[i];
    }
    ptr->u = u;
}

void upd(Node *v, int d = 0) {
    b[v->t] = bits[d];
    if (v->u != -1) {
        s2[v->t][0] = s2[v->t][1] = v->u;
        return;
    }
    if (v->p[0] != nullptr) {
        s2[v->t][0] = v->p[0]->t;
        upd(v->p[0], d + 1);
    }
    if (v->p[1] != nullptr) {
        s2[v->t][1] = v->p[1]->t;
        upd(v->p[1], d + 1);
    }
}

int main()
{
    srand(time(0));
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k; cin >> n;
    timer = n + 1;
    root = new Node();
    root->t = timer++;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> a[i] >> s[i][0] >> s[i][1];
    }
    cin >> k;
    for (int i = 0; i < n; i++) {
        bits[i] = rand() % 2;
    }

    for (int i = 1; i <= n; i++) {
        vector<int> v;
        int u = i;
        for (int it = 0; it < n-1; it++) {
            v.push_back(a[u]);
            u = s[u][bits[it]];
        }
        add(v, s[u][bits[n-1]]);
    }
    upd(root);
    cout << timer-1 << " " << n+1 << "\n";
    for (int i = 1; i <= n; i++) {
        cout << a[i] << " " << s[i][0] << " " << s[i][1] << "\n";
    }
    for (int i = n+1; i < timer; i++) {
        if (s2[i][0] == 0) s2[i][0] = s2[i][1];
        if (s2[i][1] == 0) s2[i][1] = s2[i][0];
        if (s2[i][0] == 0) {
            s2[i][0] = s2[i][1] = 1;
        }
        cout << b[i] << " " << s2[i][0] << " " << s2[i][1] << "\n";
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1844 KiB
2Elfogadva3ms2056 KiB
subtask20/16
3Elfogadva3ms2056 KiB
4Elfogadva3ms2244 KiB
5Elfogadva3ms2456 KiB
6Hibás válasz3ms2800 KiB
7Hibás válasz3ms2876 KiB
8Elfogadva3ms3220 KiB
9Elfogadva2ms3176 KiB
10Hibás válasz3ms3260 KiB
11Hibás válasz3ms3472 KiB
12Elfogadva3ms3520 KiB
13Hibás válasz3ms3612 KiB
14Hibás válasz3ms3824 KiB
subtask30/24
15Hibás válasz3ms3824 KiB
16Elfogadva3ms3924 KiB
17Elfogadva3ms4276 KiB
18Elfogadva3ms4296 KiB
19Elfogadva3ms4232 KiB
20Elfogadva3ms4408 KiB
21Elfogadva3ms4396 KiB
22Elfogadva3ms4360 KiB
23Elfogadva3ms4368 KiB
subtask423/23
24Elfogadva3ms4368 KiB
25Elfogadva3ms4492 KiB
26Elfogadva3ms4348 KiB
27Elfogadva3ms4512 KiB
28Elfogadva3ms4436 KiB
29Elfogadva3ms4428 KiB
30Elfogadva3ms4440 KiB
31Elfogadva3ms4696 KiB
32Elfogadva3ms4792 KiB
subtask50/37
33Elfogadva3ms4792 KiB
34Elfogadva3ms2244 KiB
35Elfogadva3ms2456 KiB
36Hibás válasz3ms2800 KiB
37Hibás válasz3ms2876 KiB
38Elfogadva3ms3220 KiB
39Elfogadva2ms3176 KiB
40Hibás válasz3ms3260 KiB
41Hibás válasz3ms3472 KiB
42Elfogadva3ms3520 KiB
43Hibás válasz3ms3612 KiB
44Hibás válasz3ms3824 KiB
45Elfogadva3ms3924 KiB
46Elfogadva3ms4276 KiB
47Elfogadva3ms4296 KiB
48Elfogadva3ms4232 KiB
49Elfogadva3ms4408 KiB
50Elfogadva3ms4396 KiB
51Elfogadva3ms4360 KiB
52Elfogadva3ms4368 KiB
53Elfogadva3ms4492 KiB
54Elfogadva3ms4348 KiB
55Elfogadva3ms4512 KiB
56Elfogadva3ms4436 KiB
57Elfogadva3ms4428 KiB
58Elfogadva3ms4440 KiB
59Elfogadva3ms4696 KiB
60Elfogadva3ms4792 KiB
61Elfogadva4ms4880 KiB
62Elfogadva6ms5608 KiB
63Elfogadva6ms5560 KiB
64Elfogadva7ms5756 KiB
65Elfogadva7ms5812 KiB
66Elfogadva7ms5916 KiB
67Elfogadva7ms5836 KiB
68Elfogadva7ms5940 KiB
69Elfogadva7ms5792 KiB
70Elfogadva8ms6252 KiB
71Elfogadva7ms6336 KiB
72Elfogadva7ms6264 KiB