제출 #1279280

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279280		noyancanturk	Meetings (JOI19_meetings)	C++20	29 / 100	741 ms	1148 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 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){
  v[0].insert(1);
  v[1].insert(0);
  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;
      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],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;
      }
      killall(leafs[0],-1,res);
      killall(leafs[1],-1,res);
      gonna[res]=1;
    }
  }
  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);
      }
    }
  }
}

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