Submission #702545

#	Time	Username	Problem	Language	Result	Execution time	Memory
702545		alvingogo	Meetings (JOI19_meetings)	C++14	29 / 100	2325 ms	7464 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

mt19937 rnd(time(NULL));
map<pair<int,pair<int,int> >,int> mp;
int get(int a,int b,int c){
    if(a>b){
        swap(a,b);
    }
    if(b>c){
        swap(b,c);
    }
    if(a>b){
        swap(a,b);
    }
    if(a==b || b==c){
        return b;
    }
    if(mp.find({a,{b,c}})!=mp.end()){
        return mp[{a,{b,c}}];
    }
    return mp[{a,{b,c}}]=Query(a,b,c);
}
void dc(vector<int>& v){
    int n=v.size();
    if(n<=1){
        return;
    }
    /*
    cout << "v: ";
    for(auto h:v){
        cout << h << " ";
    }
    cout << "\n";
    */
    if(n==2){
        Bridge(min(v[0],v[1]),max(v[0],v[1]));
        return;
    }
    int x=rnd()%n;
    int y=rnd()%n;
    while(y==x){
        y=rnd()%n;
    }
    x=v[x];
    y=v[y];
    vector<int> zz;
    vector<int> gg;
    for(auto h:v){
        if(h==x){
            continue;
        }
        int u=get(x,y,h);
        if(u!=x){
            y=u;
            zz.push_back(h);
        }
        else{
            gg.push_back(h);
        }
    }
    Bridge(min(x,y),max(x,y));
    gg.push_back(x);
    dc(zz);
    dc(gg);

}
void Solve(int n){
    vector<int> v(n);
    iota(v.begin(),v.end(),0);
    dc(v);
}

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