Submission #900634

#	Time	Username	Problem	Language	Result	Execution time	Memory
900634		nguyentunglam	Meetings (JOI19_meetings)	C++17	0 / 100	227 ms	262144 KiB

meetings

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

const int N = 2e3 + 10;

int st[N], ed[N], sz[N], timer, n;

bool dd[N];

vector<int> adj[N], arr;

void dfs(int u, int p) {
  sz[u] = 1;
  arr.push_back(u);
  st[u] = ++timer;
  for(int &v : adj[u]) if (v != p && !dd[v]) {
    dfs(v, u);
    sz[v] += sz[u];
  }
  ed[u] = timer;
}

bool scout (int u, int p, int x, int y) {
  if (u == x || u == y) return true;
  bool ret = 0;
  for(int &v : adj[u]) if (v != p && !dd[v]) ret |= scout(v, u, x, y);
  return ret;
}

void calc (int node, int x, bool on) {
//  cout << node << " " << x << endl;
  arr.clear();
  timer = 0;
  dfs(node, node);
  if (arr.size() == 2 && on) {
    int a = arr[0], b = arr[1];
    for(int i = 0; i < adj[a].size(); i++) if (adj[a][i] == b) {
      adj[a].erase(adj[a].begin() + i);
    }
    for(int i = 0; i < adj[b].size(); i++) if (adj[b][i] == a) {
      adj[b].erase(adj[b].begin() + i);
    }
    adj[a].push_back(x); adj[x].push_back(a);
    adj[b].push_back(x); adj[x].push_back(b);
    return;
  }
  if (arr.size() == 1) {
    bool add = 1;
    for(int &v : adj[node]) {
      assert(x != node && node != v && v != x);
      if (Query(x, node, v) != x) continue;
      for(int i = 0; i < adj[node].size(); i++) if (adj[node][i] == v) {
        adj[node].erase(adj[node].begin() + i);
      }
      for(int i = 0; i < adj[v].size(); i++) if (adj[v][i] == node) {
        adj[v].erase(adj[v].begin() + i);
      }
      adj[node].push_back(x); adj[x].push_back(node);
      adj[v].push_back(x); adj[x].push_back(v);
      return;
    }
    adj[node].push_back(x);
    adj[x].push_back(node);
    return;
  }
  int worst = n, a = 0, b = 0;
  for(int &j : arr) for(int &k : arr) if (st[j] < st[k]) {
    int cost;
    if (ed[j] >= st[k]) cost = max({sz[k], sz[j] - sz[k], n - sz[j]});
    else cost = max({sz[k], sz[j], n - sz[j] - sz[k]});
    if (cost < worst) {
      worst = cost;
      a = j; b = k;
    }
  }
//  cout << worst << " " << a << " " << b << endl;
//  assert(a != b && b != x && x != a);
  int c = Query(a, b, x);
  if (c == x) {
    for(int &v : adj[a]) if (!dd[v]) dd[v] = scout(v, a, a, b) ^ 1;
    for(int &v : adj[b]) if (!dd[v]) dd[v] = scout(v, b, a, b) ^ 1;
    calc(a, x, 1);
    return;
  }
  for(int &v : adj[c]) if (!dd[v]) dd[v] = scout(v, c, a, b);
  calc(c, x, on);
}


void Solve(int N) {
  n = N;
  for(int i = 0; i < n; i++) adj[i].clear(), dd[i] = 0;
  adj[0].push_back(1);
  adj[1].push_back(0);

  for(int cur = 2; cur < n; cur++) {
    calc(0, cur, 0);
    for(int i = 0; i < cur; i++) dd[i] = 0;
  }

//  cout << endl;
//
//  for(int i = 0; i < n; i++) for(int &j : adj[i]) if (i < j) {
//    cout << i << " " << j << endl;
//  }

//  return;

  for(int i = 0; i < n; i++) for(int &j : adj[i]) if (i < j) Bridge(i, j);
}

Compilation message (stderr)

meetings.cpp: In function 'void calc(int, int, bool)':
meetings.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i = 0; i < adj[a].size(); i++) if (adj[a][i] == b) {
      |                    ~~^~~~~~~~~~~~~~~
meetings.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i = 0; i < adj[b].size(); i++) if (adj[b][i] == a) {
      |                    ~~^~~~~~~~~~~~~~~
meetings.cpp:53:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |       for(int i = 0; i < adj[node].size(); i++) if (adj[node][i] == v) {
      |                      ~~^~~~~~~~~~~~~~~~~~
meetings.cpp:56:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |       for(int i = 0; i < adj[v].size(); i++) if (adj[v][i] == node) {
      |                      ~~^~~~~~~~~~~~~~~
meetings.cpp:49:10: warning: unused variable 'add' [-Wunused-variable]
   49 |     bool add = 1;
      |          ^~~

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