Submission #344252

#	Time	Username	Problem	Language	Result	Execution time	Memory
344252		milleniumEeee	Meetings (JOI19_meetings)	C++17	17 / 100	3051 ms	620 KiB

meetings

#include "meetings.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fr first
#define sc second
using namespace std;

const int MAXN = 2003; // дерево индексация с 0...n-1
vector <pair<int, int>> ans; // u < v
int n;

struct DSU {
  vector <int> pr;
  vector <int> sz;
  DSU (int n) {
    pr.resize(n);
    sz.resize(n);
    for (int i = 0; i < n; i++) {
      pr[i] = i;
      sz[i] = 1;
    }
  }
  int findp(int v) {
    if (v == pr[v]) {
      return v;
    }
    return pr[v] = findp(pr[v]);
  }
  void unite(int a, int b) {
    a = findp(a);
    b = findp(b);
    if (a == b) {
      return;
    }
    if (sz[a] > sz[b]) {
      swap(a, b);
    }
    pr[a] = b;
    sz[b] += sz[a];
  }
};

void build(int v, vector <bool> used) {
  vector <int> sub(n, 0);
  vector <pair<int, int>> sub_root(n, make_pair(-1e9, -1));
  DSU dsu(n);
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (used[i] && used[j]) {
        if (i != v && j != v) {
          int x = Query(i, j, v);
          if (x == i || x == j) {
            if (x == i) {
              sub[i]++;
            }
            else if (x == j) {
              sub[j]++;
            }
            dsu.unite(i, j);
          }
        }
      }
    }
  }
  set <int> subtrees;
  for (int i = 0; i < n; i++) {
    if (used[i] && i != v) {
      int boss = dsu.findp(i);
      subtrees.insert(boss);
      if (sub_root[boss].first < sub[i]) {
        sub_root[boss].first = sub[i];
        sub_root[boss].second = i;
      }      
    }
  }
  for (int el : subtrees) {
    ans.push_back(make_pair(v, sub_root[el].second));
    vector <int> vec;
    for (int i = 0; i < n; i++) {
      if (dsu.findp(i) == el) {
        used[i] = 1;
        vec.push_back(i);
      } else {
        used[i] = 0;
      }
    }
    int x = rand() % vec.size();
    build(vec[x], used);
  }
}

void Solve(int nn) {
  n = nn;
  vector <bool> used(n, true);
  build(0, used);
  for (auto &el : ans) {
    if (el.first > el.second) {
      swap(el.first, el.second);
    }
    Bridge(el.first, el.second);
  }
}

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