Submission #1171382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171382		M_W_13	Meetings (JOI19_meetings)	C++20	100 / 100	802 ms	2668 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
#define pb push_back
#define st first
#define nd second

void bridge(int a, int b) {
  Bridge(min(a, b), max(a, b));
}

void posortuj(vector<int> sciezka, int korzen, int last) {
  int sz = sciezka.size();
  // rep(i, sz) {
  //   cout << sciezka[i] << " ";
  // }
  // cout << '\n';
  // cout << "korzen ze sciezka = " << korzen << '\n';
  // cout << "last = " << last << '\n';
  vector<int> ans;
  rep(i, sz) {
    int v = sciezka[i];
    int poc = 0;
    int rozm = ans.size();
    int kon = rozm;
    int odp = rozm;
    while (poc < kon) {
      int sr = (poc + kon)/2;
      int w = ans[sr];
      if (Query(korzen, v, w) == v) {
        odp = sr;
        kon = sr;
      }
      else {
        poc = sr + 1;
      }
    }
    vector<int> ans2;
    rep(j, odp) {
      ans2.pb(ans[j]);
    }
    ans2.pb(v);
    for (int j = odp; j < rozm; j++) {
      ans2.pb(ans[j]);
    }
    ans = ans2;
  }
  // rep(i, sz) {
  //   cout << ans[i] << " ";
  // }
  // cout << '\n';
  if (sz > 0) {
    bridge(korzen, ans[0]);
    bridge(ans[sz - 1], last);
  }
  else {
    bridge(korzen, last);
  }
  // cout << "PLS" << '\n';
  rep(i, sz - 1) {
    bridge(ans[i], ans[i + 1]);
  }
  // cout << "SKULL" << '\n';
}

void rozw(vector<int> wierzcholki, int korzen) {
  int sz = wierzcholki.size();
  // rep(i, sz) {
  //   cout << wierzcholki[i] << " ";
  // }
  // cout << '\n';
  // cout << "korzen = " << korzen << '\n';
  if (sz == 0) {
    return ;
  }
  if (sz == 1) {
    bridge(wierzcholki[0], korzen);
    return;
  }
  int los = rand() % sz;
  int v = wierzcholki[los];
  vector<int> pom[2002];
  vector<int> sciezka;
  rep(i, sz) {
    if (i == los) continue;
    int w = wierzcholki[i];
    int lca = Query(korzen, v, w);
    if (lca == w) {
      sciezka.pb(w);
    }
    else {
      pom[lca].pb(w);
    }
  }
  posortuj(sciezka, korzen, v);
  rep(i, 2002) {
    int sz = pom[i].size();
    if (sz == 0) {
      continue;
    }
    rozw(pom[i], i);
  }
}

void Solve(int N) {
  vector<int> v;
  int los = rand() % N;
  rep(i, N) {
    if (i == los) continue;
    v.pb(i);
  }
  rozw(v, los);
}

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