Submission #844112

#	Time	Username	Problem	Language	Result	Execution time	Memory
844112		sjimed	Meetings (JOI19_meetings)	C++14	100 / 100	841 ms	1224 KiB

meetings

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

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pb push_back
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()
#define pre(x) cout<<fixed; cout.precision(x);

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;

int n;
vector<int> g[2010];
int sz[2010];
bool chk[2010];
bool in[2010];

int cnt;
const int MX = 100000;

int q(int u, int v, int w) {
  cnt++;
  assert(0 <= u && u < n);
  assert(0 <= v && v < n);
  assert(0 <= w && w < n);

  assert(u != v && v != w && w != u);
  assert(cnt <= 100000);
  return Query(u, v, w);
}

void dfs(int x, int p = 0) {
  sz[x] = 1;
  for(auto i : g[x]) {
    if(i == p || chk[i]) continue;
    dfs(i, x);
    sz[x] += sz[i];
  }
}

int Cen(int x) {
  int s = 1, mx = 0, mxi;
  for(auto i : g[x]) {
    if(chk[i]) continue;
    s += sz[i];
    if(sz[i] > mx) mx = sz[i], mxi = i;
  }
  if(mx > s/2) {
    sz[x] = s - mx;
    return Cen(mxi);
  }
  return x;
}

pii Find(int x) {
  memset(chk, 0, sizeof(chk));
  int r = 0;
  while(1) {
    dfs(r);
    r = Cen(r);
    //cout << r << "!!!" << endl;
    sort(all(g[r]), [](int i, int j) {
      return sz[i] > sz[j];
    });
    for(int i=0; i<g[r].size(); i+=2) {
      if(i+1 == g[r].size()) {
        if(q(g[r][i], r, x) != r) {
          if(chk[g[r][i]]) return mp(r, g[r][i]);
          chk[r] = true;
          r = g[r][i];
          break;
        }
      }
      else if(q(g[r][i], g[r][i+1], x) != r) {
        chk[r] = true;
        int nr;
        if(q(g[r][i], r, x) != r) nr = g[r][i];
        else nr = g[r][i+1];
        if(chk[nr]) return mp(r, nr);
        r = nr;
        break;
      }
      if(i+2 >= g[r].size()) return mp(r, r);
    }
  }
}

void Solve(int N) {
  n = N;

  cnt = 0;
  for(int i=0; i<n; i++) g[i].clear(), chk[i] = in[i] = false;

  g[0].eb(1);
  g[1].eb(0);

  for(int i=2; i<n; i++) {
    if(in[i]) continue;
    int u, v;
    tie(u, v) = Find(i);
    //cout << i << ": " << u << " " << v << "\n";
    if(u == v) {
      g[u].eb(i);
      g[i].eb(u);
      continue;
    }
    int tmp = q(u, v, i);
    //cout << tmp << "!\n";
    if(tmp == u) {
      g[u].eb(i);
      g[i].eb(u);
    }
    else if(tmp == v) {
      g[v].eb(i);
      g[i].eb(v);
    }
    else {
      if(tmp != i) {
        g[tmp].eb(i);
        g[i].eb(tmp);
      }
      g[tmp].eb(u);
      g[tmp].eb(v);
      for(auto &j : g[u]) if(j == v) j = tmp;
      for(auto &j : g[v]) if(j == u) j = tmp;
      in[tmp] = true;
    }
  }

  int e = 0;
  for(int i=0; i<n; i++) {
    for(auto j : g[i]) {
      if(i < j) {
        e++;
        Bridge(i, j);
      }
    }
  }
  assert(e == n-1);
}

Compilation message (stderr)

meetings.cpp: In function 'pii Find(int)':
meetings.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i=0; i<g[r].size(); i+=2) {
      |                  ~^~~~~~~~~~~~
meetings.cpp:75:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |       if(i+1 == g[r].size()) {
      |          ~~~~^~~~~~~~~~~~~~
meetings.cpp:92:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |       if(i+2 >= g[r].size()) return mp(r, r);
      |          ~~~~^~~~~~~~~~~~~~
meetings.cpp: In function 'int Cen(int)':
meetings.cpp:51:22: warning: 'mxi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |   int s = 1, mx = 0, mxi;
      |                      ^~~

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