Submission #702603

#	Time	Username	Problem	Language	Result	Execution time	Memory
702603		victor_gao	Meetings (JOI19_meetings)	C++17	29 / 100	2799 ms	2496 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());
set<pii>ans;
void DC(deque<int>have,int par){
  int n=have.size();
  int root=have[rng()%n];
  vector<deque<int> >all(20);
  /*
  cout<<"solve : ";
  for (auto i:have)
    cout<<i<<" ";
  cout<<'\n';
  cout<<"root is "<<root<<'\n';
  */
  for (auto i:have){
    if (i==root) continue;
    for (int j=0;j<19;j++){
      if (all[j].empty()){
        all[j].push_back(i);
        break;
      }
      else {
        int w=Query(all[j][0],root,i);
        if (w==root) continue;
        if (w==i) all[j].push_front(i);
        else all[j].push_back(i);
        break;
      }
    }
  }
  /*
  for (int i=0;i<19;i++){
    if (!all[i].empty()){
      cout<<"son "<<i<<" : ";
      for (auto j:all[i])
        cout<<j<<" ";
      cout<<'\n';
    }
  }
  */
  for (int i=0;i<19;i++){
    if (!all[i].empty()){
      int a=all[i][0],b=root;
      ans.insert({min(a,b),max(a,b)});
      DC(all[i],root);
    }
  }
}

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

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