제출 #1278721

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278721		noyancanturk	Meetings (JOI19_meetings)	C++20	0 / 100	1705 ms	740 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]){
          cnt++;
          dude=j;
        }
      }
      if(cnt==1){
        vis[i]=1;
        v[i].insert(dude);
        v[dude].insert(i);
        break;
      }
      vector<int>leafs;
      for(int j=0;j<n;j++){
        if(gonna[j]&&v[j].size()==1){
          leafs.pb(j);
          if(leafs.size()==2)break;
        }
      }
      int res=query(leafs[0],leafs[1],i);
      if(!vis[res]){
        dfs(leafs[0],-1,leafs[1]);
        int l=2,r=ch.size()-1,ans=1;
        while(l<=r){
          int mid=l+r>>1;
          int cur=query(ch[mid],ch.back(),res);
          if(cur==res){
            r=mid-1;
          }else{
            ans=mid;
            l=mid+1;
          }
        }
        v[ch[ans]].erase(ch[ans-1]);
        v[ch[ans-1]].erase(ch[ans]);
        v[ch[ans]].insert(res);
        v[ch[ans-1]].insert(res);
        vis[res]=1;
      }
      killall(leafs[0],-1,res);
      killall(leafs[1],-1,res);
    }
  }
  for(int i=0;i<n;i++){
    for(int j:v[i]){
      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: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 71