Submission #1170942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170942		niepamietamhasla	Meetings (JOI19_meetings)	C++20	100 / 100	910 ms	1036 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
typedef long long ll;

int p, k;

bool comp(const int &i1, const int &i2){
    if(Query(p, i1, i2) == i1) return true;
    return false;
}

void odpowiedz(int a, int b){
    if(a > b) swap(a, b);
    //cerr << a << " " << b << " ans\n";
    Bridge(a, b);
    return;
}

vector<int> posortuj(int a, vector<int> sciezka, int b){
    p = a;
    k = b;
    sort(sciezka.begin(),sciezka.end(),comp);
    return sciezka;
}

void rozw(vector<int> curr, int root){
    if(curr.size() == 1) { odpowiedz(curr[0], root); return; }
    if(curr.size() == 0) { return; }
    // cerr << root << " r\n";
    // for(auto u : curr){
    //     cerr << u << " ";
    // }
    // cerr << " wierzch\n";
    int los = curr[rand() % curr.size()];
    //cerr << los << " los\n";
    vector<int> nasciezce;
    vector<int> odpowiedzi;
    for(auto u : curr){
        if(u == los){
            odpowiedzi.push_back(-1);
            continue;
        }
        odpowiedzi.push_back(Query(los, u, root));
        if(odpowiedzi.back() == u) nasciezce.push_back(u);
    }
    // for(auto u : nasciezce){
    //     cerr << u << " ";
    // }
    // cerr << " niepos\n";
    if(nasciezce.size() > 0){
        vector<vector<int>> podd;
        vector<int> sor = posortuj(los, nasciezce, root);
        // for(auto u : sor){
        //     cerr << u << " ";
        // }
        // cerr << " pos\n";
        vector<int> v1;
        vector<int> v2;
        odpowiedz(los, sor[0]);
        for(int i = 0; i < sor.size()-1; ++i){
            odpowiedz(sor[i], sor[i+1]);
        }
        odpowiedz(sor.back(), root);
        //cerr << "wej\n";
        map<int,int> ind;
        for(int i = 0; i < sor.size(); ++i){
            ind[sor[i]] = i;
        }
        //cerr << "pon\n";
        podd.resize(nasciezce.size());
        for(int i = 0; i < curr.size(); ++i){
            if(curr[i] == los or odpowiedzi[i] == curr[i]) continue;
            if(odpowiedzi[i] == los) v1.push_back(curr[i]);
            else if(odpowiedzi[i] == root) v2.push_back(curr[i]);
            else podd[ind[odpowiedzi[i]]].push_back(curr[i]);
            //cerr << i << " " << odpowiedzi[i] << " w\n";
        }
        if(v1.size() > 0) rozw(v1, los);
        if(v2.size() > 0)  rozw(v2, root);
        for(int i = 0; i < sor.size(); ++i){
            if(podd[i].size() == 0) continue;
            rozw(podd[i], sor[i]);
        }
        return;
    }
    else{
        odpowiedz(los, root);
        vector<int> v1;
        vector<int> v2;
        for(int i = 0; i < curr.size(); ++i){
            if(curr[i] == los or odpowiedzi[i] == curr[i]) continue;
            if(odpowiedzi[i] == los) v1.push_back(curr[i]);
            else if(odpowiedzi[i] == root) v2.push_back(curr[i]);
        }
        
        if(v1.size() > 0) rozw(v1, los);
        if(v2.size() > 0)  rozw(v2, root);
    }
}

void Solve(int N){
    int n = N;
    vector<int> curr;
    int root = 0;
    for(int i = 1; i < n;  ++i){
        curr.push_back(i);
    }
    rozw(curr, root);
    return;
}

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