Submission #1171307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171307		anteknne	Meetings (JOI19_meetings)	C++20	100 / 100	607 ms	10160 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>

using namespace std;

#define st first
#define nd second
#define pb push_back
#define debug false

const int MAXN = 2000;
map<tuple<int, int, int>, pair<bool, int>> wyniki;
//mt19937 gen(69283573294);
random_device gen;

int zap (int a, int b, int c) {
    if (!wyniki[{a, b, c}].st) {
        wyniki[{a, b, c}] = {true, Query(a, b, c)};
        wyniki[{a, c, b}] = wyniki[{a, b, c}];
        wyniki[{b, a, c}] = wyniki[{a, b, c}];
        wyniki[{b, c, a}] = wyniki[{a, b, c}];
        wyniki[{c, a, b}] = wyniki[{a, b, c}];
        wyniki[{c, b, a}] = wyniki[{a, b, c}];
    }
    return wyniki[{a, b, c}].nd;
}

void wyn (int a, int b) {
    Bridge(min(a, b), max(a, b));
}

void dziel2(int a, int b, vector<int> v, int n) {
    shuffle(v.begin(), v.end(), gen);

    if (debug) {
        cout << "=====DZIEL2======" << "\n";
        cout << "wierzcholki: ";
        for (auto x : v) {
            cout << x << " ";
        }
        cout << "\n";
    }

    int m = int(v.size());

    if (m == 2) {
        wyn(a, b);
        return;
    }

    vector<int> v1, v2;
    set<int> s1, s2;
    v1.clear();
    v2.clear();
    s1.clear();
    s2.clear();
    int ind = 0;
    while (v[ind] == a || v[ind] == b) {
        ind ++;
    }
    int w = v[ind];

    s1.insert(a);
    s2.insert(b);
    s1.insert(w);
    s2.insert(w);
    for (int i = 0; i < m; i ++) {
        if (a == v[i] || v[i] == w) {
            continue;
        }
        int x = zap(a, v[i], w);
        if (x == w) {
            s2.insert(v[i]);
        } else {
            s1.insert(v[i]);
        }
    }

    for (auto x : s1) {
        v1.pb(x);
    }

    for (auto x : s2) {
        v2.pb(x);
    }

    if (debug) {
        cout << "a i b: " << a << " " << b << "\n";
        cout << "srodkowy: " << w << "\n";
        cout << "v1: ";
        for (auto x : v1) {
            cout << x << " ";
        }
        cout << "\n";
        cout << "v2: ";
        for (auto x : v2) {
            cout << x << " ";
        }
        cout << "\n";
    }

    if (int(v1.size()) > 1) {
        dziel2(a, w, v1, n);
    } else {
        if (int(v1.size()) == 0) {
            wyn(a, w);
        } else {
            wyn(a, v1.back());
            wyn(v1.back(), w);
        }
    }
    if (int(v2.size()) > 1) {
        dziel2(w, b, v2, n);
    } else {
        if (int(v2.size()) == 0) {
            wyn(w, b);
        } else {
            wyn(b, v2.back());
            wyn(v2.back(), w);
        }
    }


}

void dziel (vector<int> v, int n) {
    shuffle(v.begin(), v.end(), gen);

    if (debug) {
        cout << "=====DZIEL======" << "\n";
        cout << "wierzcholki: ";
        for (auto x : v) {
            cout << x << " ";
        }
        cout << "\n";
    }

    int m = int(v.size());
    if (m < 2) {
        return;
    }

    int u1 = v[0], u2 = v[1];

    if (debug) {
        cout << "boki sciezki: " << u1 << " " << u2 << "\n";
    }

    set<int> sciezka;
    map<int, vector<int>> jakie;
    sciezka.clear();
    jakie.clear();
    sciezka.insert(u1);
    sciezka.insert(u2);
    for (auto x : v) {
        jakie[x].clear();
    }

    for (int i = 2; i < m; i ++) {
        int x = zap(u1, u2, v[i]);
        sciezka.insert(x);
        jakie[x].pb(v[i]);
    }

    sciezka.insert(u1);
    sciezka.insert(u2);

    jakie[u1].pb(u1);
    jakie[u2].pb(u2);

    if (debug) {
        cout << "sciezka: ";
        for (auto x : sciezka) {
            cout << x << " ";
        }
        cout << "\n";
        cout << "poddzrewa: " << "\n";
        for (int i = 0; i < n; i ++) {
            cout << i << ": ";
            for (auto x : jakie[i]) {
                cout << x << " ";
            }
            cout << "\n";
        }
    }


    vector<int> vsciezka;
    vsciezka.clear();
    for (auto x : sciezka) {
        vsciezka.pb(x);
    }
    dziel2(u1, u2, vsciezka, n);

    for (auto x : jakie) {
        dziel(x.nd, n);
    }
}


void Solve (int n) {
    vector<int> v;
    v.clear();
    for (int i = 0; i < n; i ++) {
        v.pb(i);
    }
    dziel(v, n);
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 71 / 71