Submission #781118

#	Time	Username	Problem	Language	Result	Execution time	Memory
781118		PoonYaPat	Meetings (JOI19_meetings)	C++14	100 / 100	696 ms	804 KiB

meetings

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

int rt;
vector<int> temp[2005];

bool comp(int a, int b) {
  if (Query(rt,a,b)==a) return true;
  else return false;
}

void find(int root) {
  if (temp[root].size()==0) return;
  vector<int> v,path;
  swap(v,temp[root]);
  int sz=v.size(), ed=v[rand()%sz];

  for (auto s : v) {
    if (s==ed) continue;
    int h=Query(root,ed,s);
    if (h==s) path.push_back(s);
    else temp[h].push_back(s);
  }

  rt=root;
  sort(path.begin(),path.end(),comp); //root path ed
  path.push_back(ed);

  Bridge(min(root,path[0]),max(root,path[0]));
  for (int i=1; i<path.size(); ++i) Bridge(min(path[i],path[i-1]),max(path[i],path[i-1]));

  find(root);
  for (auto s : path) find(s);
}

void Solve(int N) {
  srand(time(0));
  for (int i=1; i<N; ++i) temp[0].push_back(i);
  find(0);
}

Compilation message (stderr)

meetings.cpp: In function 'void find(int)':
meetings.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for (int i=1; i<path.size(); ++i) Bridge(min(path[i],path[i-1]),max(path[i],path[i-1]));
      |                 ~^~~~~~~~~~~~

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