Submission #1006376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006376		AdamGS	Meetings (JOI19_meetings)	C++17	100 / 100	478 ms	980 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;
  odw[0]=1;
  rep(i, n) if(!odw[i]) licz(i);
  rep(i, n) for(auto j : V[i]) if(i<j) Bridge(i, j);
}

Compilation message (stderr)

meetings.cpp: In function 'void usun_kraw(int, int)':
meetings.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
meetings.cpp:18:3: note: in expansion of macro 'rep'
   18 |   rep(i, V[a].size()) if(V[a][i]==b) swap(V[a][i], V[a][V[a].size()-1]);
      |   ^~~
meetings.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
meetings.cpp:19:3: note: in expansion of macro 'rep'
   19 |   rep(i, V[b].size()) if(V[b][i]==a) swap(V[b][i], V[b][V[b].size()-1]);
      |   ^~~
meetings.cpp: In function 'int cent(int)':
meetings.cpp:37:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     if(2*ma<=spojna.size()) return i;
      |        ~~~~^~~~~~~~~~~~~~~

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