Submission #1171271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171271		Piokemon	Meetings (JOI19_meetings)	C++20	29 / 100	424 ms	848 KiB

meetings

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

constexpr int N = 2000;
set<pair<int,int>> kraw;
vector<int> graf[N+9];
bool block[N+9];
int dp[N+9];
int sajz;

void calcdp(int v, int par){
  sajz++;
  dp[v]=1;
  for (int x:graf[v]){
    if (!block[x] && x!=par){
      calcdp(x,v);
      dp[v]+=dp[x];
    }
  }
}

int fintcentr(int v, int par){
  int maks=-1,ktor=-1;
  for (int x:graf[v]){
    if (x==par || block[x])continue;
    if (dp[x]>maks){
      maks=dp[x]; ktor=x;
    }
  }
  if (maks <= sajz/2)return v;
  return fintcentr(ktor,v);
}

bool comp(int a, int b){return dp[a]>dp[b];}

void insert(int v, int popc, int par){
  // popc - poprzedni centroid, wsm dowonly wierzcholek w tej spojnej
  // par - uzywam by odgrodzic od poprzedniego centroida, czy wyznaczyc spojna w ktorej jestem
  block[par]=1;
  sajz=0;
  calcdp(popc,-1);
  int nowy = fintcentr(popc,par);
  calcdp(nowy,-1);
  sort(graf[nowy].begin(),graf[nowy].end(),comp);
  for (int x:graf[nowy]){
    if (block[x])continue;
    int temp = Query(nowy,x,v);
    if (temp==x){
      insert(v,x,nowy);
      return;
    }
    else if (temp==nowy)continue;
    else{
      kraw.erase({min(nowy,x),max(nowy,x)});
      kraw.insert({min(nowy,temp),max(nowy,temp)});
      kraw.insert({min(x,temp),max(x,temp)});
      return;
    }
  }
  kraw.insert({min(nowy,v),max(nowy,v)});
}

void constr(int n){
  for (int x=0;x<=n;x++){
    graf[x].clear();
    block[x]=0;
  }
  for (pair<int,int> x:kraw){
    graf[x.first].push_back(x.second);
    graf[x.second].push_back(x.first);
  }
}

void Solve(int N) {
  for (int t=1;t<N;t++){
    constr(N);
    int cel=-1;
    for (int x=1;x<N;x++){
      if (graf[x].size()==0)cel=x;
    }
    insert(cel,0,N+1);
  }
  for (pair<int,int> x:kraw){
    Bridge(min(x.first,x.second),max(x.first,x.second));
  }
  return;
}

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