Submission #1170982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170982		owieczka	Meetings (JOI19_meetings)	C++20	100 / 100	854 ms	3588 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int zli = 1;
vector<int> group[100'000];
vector<int> path[2'002];
vector<int> under[2'002];
// int parent[2'000];
// int centr[2'000];
int done[2'002];
vector <int> graph[2'002];

mt19937 gen(1);
int draw_new(vector<int> &vec, int dn)
{
  int lim = vec.size();
  int v = vec[gen()%lim];
  while (done[v] == dn)
  {
    v = vec[gen()%lim];
  }
  return v;
}


pair<int, int> rec_path(int up, int down, int id) // zwraca najnizszy i najwyzszy
{
  if (group[id].size() == 1)
  {
    return {group[id][0], group[id][0]};
  }
  int led = draw_new(group[id], -2);
  int ld = zli+1;
  int hd = zli+2;
  zli+=2;
  for (auto i : group[id])
  {
    if (i == led)continue;
    int a = Query(i, led, down);
    if (a == i)
    {
      group[ld].push_back(i); // niższa
    }
    else if (a == led)
    {
      group[hd].push_back(i); // wyzsza
    }
    else assert(false);
  }
  int u, d;
  if (group[hd].empty())
  {
    graph[up].push_back(led);
    graph[led].push_back(up);
    u = led;
  }
  else
  {
    auto h = rec_path(up, led, hd);
    graph[h.first].push_back(led);
    graph[led].push_back(h.first);
    u = h.second;
  }
  if (group[ld].empty())
  {
    graph[led].push_back(down);
    graph[down].push_back(led);
    d = led;
  }
  else{
    auto l = rec_path(led, down, ld);
    graph[led].push_back(l.second);
    graph[l.second].push_back(led);
    d = l.first;
  }
  return {d, u};
}

void solve_path(int v, int p)
{
  if (path[v].empty())
  {
    graph[p].push_back(v);
    graph[v].push_back(p);
    return;
  }
  shuffle(path[v].begin(), path[v].end(), gen);
  for (auto i : path[v])
  {
    group[zli+1].push_back(i);
  }
  zli++;
  auto a = rec_path(p, v, zli);
  graph[a.first].push_back(v);
  graph[v].push_back(a.first);
  graph[p].push_back(a.second);
  graph[a.second].push_back(p);
}

void divide_under(int p)
{
  if (under[p].empty())
  {
    return;
  }
  if (under[p].size() == 1)
  {
    graph[p].push_back(under[p][0]);
    graph[under[p][0]].push_back(p);
    return;
  }

  shuffle(under[p].begin(), under[p].end(), gen);

  // int v = draw_new(under[p], p);
  // done[v] = p;
  vector<int> fract = {};
  for (auto i : under[p])
  {
    if (done[i] == p)continue;
    bool found = 0;
    for (auto f : fract)
    {
      // int f = fract[j];
      int a = Query(i, f, p);
      if (a == p)//w innej spojnej
      {
        continue;
      }
      if (a == f)
      {
        under[f].push_back(i);
        found = 1;
        break;
      }
      else 
      {
        if (done[a] != p)
        {
          done[a] = p;
          path[f].push_back(a);
        }
        if(i != a)under[a].push_back(i);
        found = 1;
        break;
      }
    }
    done[i] = p;
    if (!found)fract.push_back(i);
  }
  for (auto f : fract)
  {
    solve_path(f, p);
    divide_under(f);
    for (auto i : path[f])
    {
      divide_under(i);
    }

  }
}
set<pair<int,int>> o;
void Solve(int N) {
  // int x = Query(0, 1, 2);
  // for (int u = 0; u < N - 1; ++u) {
  //   Bridge(u, u + 1);
  // }
  int r = gen()%N;
  for (int i = 0; i < N; i++)
  {
    done[i] = -1;
    if (r == i)continue;
    under[r].push_back(i);
  }
  divide_under(r);
  for (int i = 0; i < N; i++)
  {
    for (auto v : graph[i])
    {
      if (i < v && !o.contains({i, v}))
      {
        Bridge(i, v);
        o.insert({i, v});
      }
    }
  }
}

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