Submission #1279282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279282		noyancanturk	Meetings (JOI19_meetings)	C++20	29 / 100	871 ms	1208 KiB

meetings

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

#define query Query
#define answer Bridge
#define pb push_back

const int lim=2100;

unordered_set<int>v[lim];

vector<int>ch;

int dfs(int node,int par,int targ){
  if(node==targ){
    ch.clear();
    ch.pb(node);
    return 1;
  }
  for(int j:v[node]){
    if(j==par)continue;
    if(dfs(j,node,targ)){
      ch.pb(node);
      return 1;
    }
  }
  return 0;
}

int gonna[lim];

void killall(int node,int par,int targ){
  if(node==targ)return;
  gonna[node]=0;
  for(int j:v[node]){
    if(j==par)continue;
    killall(j,node,targ);
  }
}

int tot;

int sz[lim],vis[lim];
int p[lim];

int sbs(int node,int par){
  sz[node]=1;
  for(int j:v[node]){
    if(!vis[j]||!gonna[j]||j==par)continue;
    sz[node]+=sbs(j,node);
  }
  return sz[node];
}

int findcen(int node,int par){
  for(int j:v[node]){
    if(!vis[j]||!gonna[j]||j==par)continue;
    if(tot<2*sz[j])return findcen(j,node);
  } 
  return node;
}

void Solve(int n){
  iota(p,p+n,0);
  random_shuffle(p,p+n);
  v[p[0]].insert(p[1]);
  v[p[1]].insert(p[0]);
  vis[p[0]]=vis[p[1]]=1;
  for(int i=2;i<n;i++){
    if(vis[p[i]])continue;
    for(int j=0;j<n;j++)gonna[j]=1;
    while(!vis[p[i]]){
      int cnt=0,dude=0;
      for(int j=0;j<n;j++){
        if(vis[j]&&gonna[j]){
          cnt++;
          dude=j;
        }
      }
      if(cnt==1){
        vis[p[i]]=1;
        v[p[i]].insert(dude);
        v[dude].insert(p[i]);
        break;
      }
      vector<int>leafs;
      if(cnt==2){
        leafs.pb(dude);
        for(int j:v[dude]){
          if(vis[j]&&gonna[j])leafs.pb(j);
        }
      }else{
        tot=sbs(dude,-1);
        dude=findcen(dude,-1);
        tot=-1;
        for(int j:v[dude]){
          if(vis[j]&&gonna[j]){
            leafs.pb(findcen(j,dude));
            if(leafs.size()==2)break;
          }
        }
      }
      assert(leafs.size()==2);
      int res=query(leafs[0],leafs[1],p[i]);
      if(!vis[res]){
        dfs(leafs[0],-1,leafs[1]);
        int l=1,r=ch.size()-2,ans=ch.size()-1;
        while(l<=r){
          int mid=l+r>>1;
          int cur=query(ch[mid],ch.back(),res);
          if(cur==res){
            l=mid+1;
          }else{
            ans=mid;
            r=mid-1;
          }
        }
        v[ch[ans]].erase(ch[ans-1]);
        v[ch[ans-1]].erase(ch[ans]);
        v[ch[ans]].insert(res);
        v[res].insert(ch[ans]);
        v[ch[ans-1]].insert(res);
        v[res].insert(ch[ans-1]);
        vis[res]=1;
        gonna[res]=1;
      }
      killall(leafs[0],-1,res);
      killall(leafs[1],-1,res);
    }
  }
  int leafcnt=0;
  for(int i=0;i<n;i++){
    leafcnt+=v[i].size()==1;
  }
  // cerr<<leafcnt<<'\n';
  for(int i=0;i<n;i++){
    for(int j:v[i]){
      if(i<j){
        answer(i,j);
      }
    }
  }
}

Compilation message (stderr)

meetings.cpp: In function 'void Solve(int)':
meetings.cpp:66:17: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = int*]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   66 |   random_shuffle(p,p+n);
      |   ~~~~~~~~~~~~~~^~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from meetings.cpp:2:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~

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