Submission #1171525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171525		TlenekWodoru	Meetings (JOI19_meetings)	C++20	0 / 100	57 ms	680 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(2137);
int Start,Meta;
bool cmp(int a, int b)
{
    if(a==b){return 0;}
    if(a==Start){return 1;}
    if(b==Meta){return 1;}
    if(a==Meta){return 0;}
    if(b==Start){return 0;}
    return Query(Start,a,b)==a;
}
void F(int v, vector<int>U)
{
    if(U.size()==1){return;}
    if(U.size()==2)
    {
        Bridge(U[0],U[1]);
        return;
    }
    shuffle(U.begin(),U.end(),rng);
    int v2=v;
    while(v==v2)
    {
        v2=U[rng()%(int)U.size()];
    }
    map<int,vector<int>>M;
    M[v].push_back(v);
    M[v2].push_back(v2);
    for(int u : U)
    {
        if(u==v||u==v2){continue;}
        int u2=Query(v,v2,u);
        M[u2].push_back(u);
    }
    vector<int>T;
    for(auto XD : M)
    {
        T.push_back(XD.first);
        F(XD.first,XD.second);
    }
    Start=v;
    Meta=v2;
    stable_sort(T.begin(),T.end(),cmp);
    for(int i=1;i<T.size();i++)
    {
        int a=T[i-1],b=T[i];
        if(a>b){swap(a,b);}
        Bridge(a,b);
    }
}
void Solve(int n)
{
    vector<int>U;
    for(int i=0;i<n;i++){U.push_back(i);}
    shuffle(U.begin(),U.end(),rng);
    F(U[0],U);
}

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