Submission #702618

#	Time	Username	Problem	Language	Result	Execution time	Memory
702618		victor_gao	Meetings (JOI19_meetings)	C++17	100 / 100	571 ms	1004 KiB

meetings

#include<bits/stdc++.h>
#include "meetings.h"
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int>Merge_sort(vector<int>now,int mn){
  if (now.size()==1) return now;
  int n=now.size(),mid=(n-1)/2;
  vector<int>l,r,ans;
  for (int i=0;i<=mid;i++)
    l.push_back(now[i]);
  for (int i=mid+1;i<n;i++)
    r.push_back(now[i]);
  l=Merge_sort(l,mn);
  r=Merge_sort(r,mn);
  int p=0;
  for (auto i:l){
    if (p>=r.size()){
      ans.push_back(i);
      continue;
    }
    int small=Query(mn,i,r[p]);
    while(p<r.size()&&small==r[p]){
      ans.push_back(r[p++]);
      if (p<r.size())
        small=Query(mn,i,r[p]);
    }
    ans.push_back(i);
  }
  while (p<r.size())
    ans.push_back(r[p++]);
  return ans;
}
set<pii>ans;
void DC(vector<int>have,int dep){
 // cout<<dep<<" "<<have.size()<<'\n';
  int n=have.size();
  if (n==1) return;
  else if (n==2){
  //  cout<<"n=2 add : "<<min(have[0],have[1])<<" "<<max(have[0],have[1])<<'\n';
    assert(have[0]!=have[1]);
    ans.insert({min(have[0],have[1]),max(have[0],have[1])});
    return;
  }
  shuffle(have.begin(),have.end(),rng);
  int p1=have[0],p2=have[1];
  vector<vector<int> >all(n);
  vector<int>path;
  map<int,int>mp;
  /*
  cout<<"solve : ";
  for (auto i:have)
    cout<<i<<" ";
  cout<<'\n';
  cout<<"root is "<<p1<<" "<<p2<<'\n';
 */
  path.push_back(p2);
  all[0].push_back(p1);
  all[1].push_back(p2);
  for (int id=2;id<n;id++){
    int i=have[id];
    int nxt=Query(p1,i,p2);
    if (nxt==i)
      path.push_back(i);
    if (nxt!=p1&&nxt!=p2){
      if (!mp[nxt]) mp[nxt]=id;
      all[mp[nxt]].push_back(i);
    }
    else if (nxt==p1)
      all[0].push_back(i);
    else all[1].push_back(i);
  }
  /*
  for (int i=0;i<n;i++){
    if (!all[i].empty()){
      cout<<"son "<<i<<" : ";
      for (auto j:all[i])
        cout<<j<<" ";
      cout<<'\n';
    }
  }
  cout<<"path : "<<p1<<' ';
  for (auto i:path)
    cout<<i<<" ";
  cout<<'\n';
  */
  path=Merge_sort(path,p1);
//  cout<<"add "<<min(p1,path[0])<<' '<<max(p1,path[0])<<'\n';
  assert(p1!=path[0]);
  ans.insert({min(p1,path[0]),max(p1,path[0])});
  for (int i=1;i<path.size();i++){
  //  cout<<"add "<<min(path[i],path[i-1])<<" "<<max(path[i],path[i-1])<<'\n';
    assert(path[i]!=path[i-1]);
    ans.insert({min(path[i],path[i-1]),max(path[i],path[i-1])});
  }
  for (int i=0;i<n;i++){
    if (!all[i].empty()){
      DC(all[i],dep+1);
    }
  }
}

void Solve(int N){
  vector<int>dq;
  for (int i=0;i<N;i++)
    dq.push_back(i);
  DC(dq,0);
  for (auto i:ans){
   // assert(i.x!=i.y);
   // assert(i.x<i.y);
  //  cout<<i.x<<" "<<i.y<<'\n';
    Bridge(i.x,i.y);
  }
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<int> Merge_sort(std::vector<int>, int)':
meetings.cpp:21:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     if (p>=r.size()){
      |         ~^~~~~~~~~~
meetings.cpp:26:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     while(p<r.size()&&small==r[p]){
      |           ~^~~~~~~~~
meetings.cpp:28:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |       if (p<r.size())
      |           ~^~~~~~~~~
meetings.cpp:33:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   while (p<r.size())
      |          ~^~~~~~~~~
meetings.cpp: In function 'void DC(std::vector<int>, int)':
meetings.cpp:94:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for (int i=1;i<path.size();i++){
      |                ~^~~~~~~~~~~~

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