Submission #1307260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307260		vako_p	Meetings (JOI19_meetings)	C++20	100 / 100	1250 ms	1044 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second

static ll n;
random_device rd;
mt19937_64 gen(rd());

void br(ll a, ll b){
  if(a > b) swap(a, b);
  Bridge(a, b);
}

void f(vector<ll> v){
  if(v.size() <= 1) return;
  // for(auto it : v) cout << it << ' ';
  // cout << '\n';
  if(v.size() == 2){
    br(v[0], v[1]);
    return;
  }
  uniform_int_distribution<ll> dis(0, v.size() - 1);
  for(int i = 0; i < v.size(); i++) swap(v[i], v[dis(gen)]);
  // add
  ll x = v[0],y = v[1];
  vector<vector<ll>> vv;
  vv.pb({x});
  vv.pb({y});
  vector<ll> a;
  a.pb(x);
  a.pb(y);
  for(int i = 2; i < v.size(); i++){
    ll ans = Query(x, y, v[i]);
    bool ok = true;
    for(auto &it : vv){
      if(it[0] == ans){
        ok = false;
        if(v[i] != ans) it.pb(v[i]);
        break;
      }
    }
    if(ok){
      a.pb(ans);
      vv.pb({ans});
      if(ans != v[i]) vv[vv.size() - 1].pb(v[i]);
    }
  }
  auto op = [&](const ll num1, const ll num2) -> bool{
    if(num2 == x or num1 == num2) return false;
    if(num1 == x) return true;
    return (Query(num1, x, num2) == num1);
  };
  sort(a.begin(), a.end(), op);
  // for(auto it : a) cout << it << ' ';
  // cout << '\n';
  for(int i = 1; i < a.size(); i++) br(a[i], a[i - 1]);
  // cout << vv.size() << " -- " << '\n';
  // for(auto it : vv){
  //   for(auto it1 : it) cout << it1 << ' ';
  //   cout << '\n';
  // }
  for(auto it : vv) f(it);
}

void Solve(int N) {
  n = N;
  vector<ll> v(n);
  iota(v.begin(), v.end(), 0);
  f(v);
}

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