Submission #1224295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224295		poat	Meetings (JOI19_meetings)	C++17	29 / 100	445 ms	1712 KiB

meetings

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

mt19937 rng(time(0));

void solve(vector<int> vec)
{
  if(vec.size() == 1)
    return;
  else if(vec.size() == 2)
  {
    if(vec[0] > vec[1])
      swap(vec[0], vec[1]);

    Bridge(vec[0], vec[1]);
    return;
  }

  shuffle(vec.begin(), vec.end(), rng);
  
  
  int x = vec[0], y = vec[1];

  map<int, bool> used;
  used[x] = used[y] = 1;

  vector<int> a = {x}, b = {y};  
  for(int i = 2; i < vec.size(); i++)
  {
    if(used[vec[i]])
      continue;

    used[vec[i]] = 1;

    int z = Query(x, y, vec[i]);
    if(z == x)
      a.push_back(vec[i]);
    else if(z == y)
      b.push_back(vec[i]);
    else if(z == vec[i])
    {
      if(a.size() > b.size())
      {
        y = vec[i];
        b.push_back(vec[i]);
      }
      else
      {
        x = vec[i];
        a.push_back(vec[i]);
      }
    }
    else 
    {
      used[z] = 1;
      if(a.size() > b.size())
      {
        y = z;
        b.push_back(z);
        b.push_back(vec[i]);
      }
      else
      {
        x = z;
        a.push_back(z);
        a.push_back(vec[i]);
      }
    }
  }

  Bridge(min(x, y), max(x, y));

  solve(a);
  solve(b);

}

void Solve(int N) 
{
  vector<int> vec;
  for(int i = 0; i < N; i++)
    vec.push_back(i);

  solve(vec);

}

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