제출 #1170825

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170825		AdamGS	Meetings (JOI19_meetings)	C++17	29 / 100	393 ms	824 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e3+7;
vector<int>V[LIM], spojna;
int ile[LIM], usun[LIM], odw[LIM], n;
void dodaj_kraw(int a, int b) {
  V[a].pb(b);
  V[b].pb(a);
}
void usun_kraw(int a, int b) {
  rep(i, V[a].size()) if(V[a][i]==b) swap(V[a][i], V[a][V[a].size()-1]);
  rep(i, V[b].size()) if(V[b][i]==a) swap(V[b][i], V[b][V[b].size()-1]);
  V[a].pop_back();
  V[b].pop_back();
}
void DFS(int x, int o) {
  spojna.pb(x);
  ile[x]=1;
  for(auto i : V[x]) if(i!=o && !usun[i]) {
    DFS(i, x);
    ile[x]+=ile[i];
  }
}
int cent(int x) {
  spojna.clear();
  DFS(x, x);
  for(auto i : spojna) {
    int ma=spojna.size()-ile[i];
    for(auto j : V[i]) if(!usun[j] && ile[j]<ile[i]) ma=max(ma, ile[j]);
    if(2*ma<=spojna.size()) return i;
  }
  return -1;
}
void cd(int x, int p) {
  x=cent(x);
  spojna.clear();
  DFS(x, x);
  usun[x]=1;
  vector<pair<int,int>>P;
  for(auto i : V[x]) if(!usun[i]) 
    P.pb({ile[i], i});
  sort(all(P));
  reverse(all(P));
  for(auto xd : P) {
    int i=xd.nd;
    int a=Query(x, p, i);
    if(a==x) continue;
    if(a==i) {
      cd(i, p);
      return;
    }
    if(a==p) {
      usun_kraw(i, x);
      dodaj_kraw(i, p);
      dodaj_kraw(p, x);
      return;
    }
    usun_kraw(i, x);
    dodaj_kraw(i, a);
    dodaj_kraw(a, x);
    dodaj_kraw(a, p);
    odw[a]=1;
    return;
  }
  dodaj_kraw(x, p);
}
void licz(int x) {
  rep(i, n) usun[i]=ile[i]=0;
  cd(0, x);
  odw[x]=1;
}
void Solve(int _n) {
  n=_n;
  rep(i, n) if(!odw[i]) licz(i);
  rep(i, n) for(auto j : V[i]) if(i<j) Bridge(i, j);
}

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