Submission #1278732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278732		noyancanturk	Meetings (JOI19_meetings)	C++20	29 / 100	1066 ms	1128 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);
  }
}

void Solve(int n){
  v[0].insert(1);
  v[1].insert(0);
  int vis[n]{};
  vis[0]=vis[1]=1;
  for(int i=2;i<n;i++){
    if(vis[i])continue;
    for(int j=0;j<n;j++)gonna[j]=1;
    while(!vis[i]){
      int cnt=0,dude=0;
      for(int j=0;j<n;j++){
        if(vis[j]&&gonna[j]){
          // cerr<<j<<" active\n";
          cnt++;
          dude=j;
        }
      }
      if(cnt==1){
        // cerr<<"ma dude "<<i<<' '<<dude<<'\n';
        vis[i]=1;
        v[i].insert(dude);
        v[dude].insert(i);
        break;
      }
      vector<int>leafs;
      for(int j=0;j<n;j++){
        if(vis[j]&&gonna[j]){
          int cc=0;
          for(int k:v[j]){
            cc+=vis[k]&&gonna[k];
            if(cc==2)break;
          }
          if(cc==1){
            leafs.pb(j);
            if(leafs.size()==2)break;
          }
        }
      }
      // cerr<<cnt<<' '<<leafs.size()<<'\n';
      assert(leafs.size()==2);
      // cerr<<leafs[0]<<' '<<leafs[1]<<' '<<i<<'\n';
      int res=query(leafs[0],leafs[1],i);
      // cerr<<"asked "<<leafs[0]<<' '<<leafs[1]<<' '<<i<<' '<<res<<'\n';
      if(!vis[res]){
        // cerr<<"missing "<<leafs[0]<<' '<<leafs[1]<<' '<<res<<'\n';
        dfs(leafs[0],-1,leafs[1]);
        // cerr<<"ch : ";
        // for(int jj:ch)cerr<<jj<<' ';
        // cerr<<'\n';
        // assert(ch.size()>=2);
        // assert(ch[0]==leafs[1]&&ch.back()==leafs[0]);
        int l=1,r=ch.size()-2,ans=ch.size()-1;
        while(l<=r){
          int mid=l+r>>1;
          // cerr<<ch[mid]<<' '<<ch.back()<<' '<<res<<'\n';
          int cur=query(ch[mid],ch.back(),res);
          if(cur==res){
            l=mid+1;
          }else{
            ans=mid;
            r=mid-1;
          }
        }
        // cerr<<"here\n";
        // cerr<<ch[ans]<<' '<<ch[ans-1]<<' '<<res<<" inserted\n";
        // assert(v[ch[ans]].count(ch[ans-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;
      }
      killall(leafs[0],-1,res);
      killall(leafs[1],-1,res);
      gonna[res]=1;
    }
    // for(int i=0;i<n;i++){
    //   for(int j:v[i]){
    //     cerr<<i<<' '<<j<<'\n';
    //   }
    // }cerr<<'\n';
  }
  for(int i=0;i<n;i++){
    for(int j:v[i]){
      // cerr<<i<<' '<<j<<'\n';
      if(i<j){
        answer(i,j);
      }
    }
  }
}

// void Solve(int N) {
//   int x = Query(0, 1, 2);
//   for (int u = 0; u < N - 1; ++u) {
//     Bridge(u, u + 1);
//   }
// }

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