Submission #702546

#	Time	Username	Problem	Language	Result	Execution time	Memory
702546		alvingogo	Meetings (JOI19_meetings)	C++14	29 / 100	2686 ms	7624 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;
    }
    if(n==2){
        Bridge(min(v[0],v[1]),max(v[0],v[1]));
        return;
    }
    int x=0;
    x=v[x];
    vector<int> zz;
    vector<int> vis(n);
    vis[0]=1;
    int cnt=1;
    while(cnt<n){
        int y=-1;
        for(int i=0;i<n;i++){
            if(vis[i]==0){
                y=v[i];
                break;
            }
        }
        int i=0;
        for(auto h:v){
            if(h==x || vis[i]){
                i++;
                continue;
            }
            int u=get(x,y,h);
            if(u!=x){
                y=u;
                zz.push_back(h);
                vis[i]=1;
                cnt++;
            }
            i++;
        }
        Bridge(min(x,y),max(x,y));
        dc(zz);
        zz.clear();
    }
}
void Solve(int n){
    vector<int> v(n);
    iota(v.begin(),v.end(),0);
    shuffle(v.begin(),v.end(),rnd);
    dc(v);
}

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