Submission #1320148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320148		wangzhiyi33	Meetings (JOI19_meetings)	C++20	0 / 100	1 ms	408 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fir first
#define sec second
#define pb push_back

const int maxn=2000;
int n;
vector<int>adj[maxn+2];
int sub[maxn+2];
bool vis[maxn+2],msk[maxn+2];

void dfs(int cur,int par){
  sub[cur]=1;
  for(auto x : adj[cur]){
    if(x==par || vis[x])continue;
    dfs(x,cur);
    sub[cur]+=sub[x];
  }
}

int centro(int cur,int par,int sz){
  for(auto x : adj[cur]){
    if(x==par || vis[x])continue;
    if(sub[x]>=sz/2){
      return centro(x,cur,sz);
    }
  }
  return cur;
}

void add(int cur,int targ){
  dfs(cur,-1);
  int root=centro(cur,-1,sub[cur]);
  dfs(root,-1);
  vis[root]=true;

  vector<ii>sblh;
  for(auto x : adj[root]){
    if(vis[x])continue;
    sblh.pb({sub[x],x});
  }
  if(sblh.size()%2==1)sblh.pb({0,root});

  sort(sblh.rbegin(),sblh.rend());

  for(int q=0;q<sblh.size();q+=2){
    int a=sblh[q].sec,b=sblh[q+1].sec;
    int nd=Query(a,b,targ);

    if(a==nd || b==nd){
      if(b==nd && b==root)continue;
      add(nd,targ);
      return;
    }
    else if(nd!=root){
      int piv;
      if(Query(a,root,nd)==nd){
        piv=a;
      }
      else{
        piv=b;
      }

      adj[piv].erase(find(adj[piv].begin(),adj[piv].end(),root));
      adj[root].erase(find(adj[root].begin(),adj[root].end(),piv));

      adj[root].pb(nd),adj[nd].pb(root);
      adj[piv].pb(nd),adj[nd].pb(piv);

      if(piv!=targ){
        adj[piv].pb(targ),adj[targ].pb(piv);
      }
      msk[piv]=true;
      return;
    }
  }
  adj[targ].pb(root),adj[root].pb(targ);
}

void Solve(int N) {
  n=N;
  adj[0].push_back(1);
  adj[1].push_back(0);
  msk[0]=msk[1]=true;

  for(int q=2;q<n;q++){
    if(msk[q])continue;
    memset(vis,false,sizeof vis);
    add(0,q);
    msk[q]=true;
  }
  for(int q=0;q<N;q++){
    for(auto x : adj[q]){
      if(x>q)Bridge(q,x);
    }
  }
}

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