제출 #1170913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170913		niepamietamhasla	Meetings (JOI19_meetings)	C++20	0 / 100	25 ms	652 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);
    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; }
    int los = curr[rand() % curr.size()];
    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);
    }
    vector<vector<int>> podd;
    vector<int> v1;
    vector<int> v2;
    vector<int> sor = posortuj(los, nasciezce, root);
    odpowiedz(los, sor[0]);
    for(int i = 0; i < sor.size()-1; ++i){
        odpowiedz(sor[i], sor[i+1]);
    }
    odpowiedz(sor.back(), root);
    vector<int> ind(sor.size());
    for(int i = 0; i < sor.size(); ++i){
        ind[sor[i]] = i;
    }
    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]);
    }
    rozw(v1, los);
    rozw(v2, root);
    for(int i = 0; i < sor.size(); ++i){
        rozw(podd[i], sor[i]);
    }
    return;
}

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: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 71