Submission #1265958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265958		StefanSebez	Meetings (JOI19_meetings)	C++20	100 / 100	706 ms	2144 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=2050;
mt19937 rng(time(0));
void Resi(vector<int>vtx){
    //for(auto i:vtx) printf("%i ",i);printf("\n");
    if(vtx.size()<=1) return;
    shuffle(vtx.begin(),vtx.end(),rng);
    int u=vtx[0],v=vtx[1];
    vector<int>lanac={u};
    vector<int>podstablo[N];
    podstablo[u].pb(u);
    podstablo[v].pb(v);
    for(auto i:vtx){
        if(i==u||i==v) continue;
        int x=Query(u,v,i);
        if(x==i) lanac.pb(i);
        podstablo[x].pb(i);
    }
    lanac.pb(v);
    sort(lanac.begin()+1,lanac.end()-1,[&](int i,int j){return Query(u,i,j)==i;});
    for(int i=0;i+1<lanac.size();i++){
        int x=lanac[i],y=lanac[i+1];if(x>y)swap(x,y);
        Bridge(x,y);
    }
    /*for(auto i:lanac){
        printf("%i: ",i);printf("\n");
        for(auto j:podstablo[i]) printf("%i ",j);printf("\n");
    }*/
    for(auto i:lanac) Resi(podstablo[i]);
}
void Solve(int n) {
    vector<int>vtx;
    for(int i=0;i<n;i++) vtx.pb(i);
    Resi(vtx);
}

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