Submission #821785

#	Time	Username	Problem	Language	Result	Execution time	Memory
821785		farhan132	Meetings (JOI19_meetings)	C++17	29 / 100	1826 ms	2132 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;
 
typedef int ll;
typedef double dd;
typedef pair<ll , ll> ii;
typedef tuple < ll,  ll, ll > tp;
 
#define ff first
#define ss second
#define pb push_back
#define in insert

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const ll N = 2005;
vector < ll > v[N];
ll col[N];

void dfs(ll s){
  if(col[s]) return;
  col[s] = 1;
  for(auto u : v[s]) dfs(u);
}

void solve(vector < ll > a){
  if(a.size() == 1) return;
  if(a.size() == 2){
    v[a[0]].pb(a[1]);
    v[a[1]].pb(a[0]);
    //cout << a[0] << ' ' << a[1] << " <- double" << '\n';
    return;
  }
  ll n = a.size();
  ll x = rng() % n, y = rng() % n;
  while(x == y){
    x = rng() % n;
    y = rng() % n;
  }
  x = a[x];
  y = a[y];
  vector < ll > X, mid, Y;
  for(auto u : a){
    if(u - x && u - y){
      ll z = Query(x, y, u);
      if(z == x) X.pb(u);
      if(z == y) Y.pb(u);
      if(z != x && z != y) mid.pb(u);
    }
  }
  shuffle(X.begin(), X.end(), rng);
  shuffle(Y.begin(), Y.end(), rng);

  // for x nodes
  vector < vector < ll > > F;
  for(auto u : X){
    bool ok = 0;
    for(ll i = 0; i < F.size(); i++){
      if(Query(u, F[i][0], x) != x){
        F[i].pb(u);
        ok = 1;
        break;
      }
    }
    if(!ok){
      F.pb({u});
    }
  }
  F.pb(mid);
  for(auto vec : F){
    if(vec.size() == 0) continue;
    solve(vec);
    for(auto u : vec) col[u] = 0;
    //cout << vec.size() << '\n';
    vector < ll > potential_cands;
    for(auto u : vec){
      potential_cands.pb(u);
    }
    shuffle(potential_cands.begin(), potential_cands.end(), rng);
    ll node = potential_cands[0]; 
    col[node] = 1;
    for(ll i = 0; i < potential_cands.size(); i++){
      if(col[potential_cands[i]]) continue;
      ll z = Query(potential_cands[i], node, x);
      if(z == node){
        dfs(potential_cands[i]);
      }else{
        col[node] = 0;
        col[z] = 1;
        dfs(potential_cands[i]);
        dfs(node);
        node = z;
      }
    }
    v[x].pb(node);
    v[node].pb(x);
    //cout << node << ' ' << x << " <- x" << '\n';
  }

  if(mid.size() == 0){
    v[x].pb(y);
    v[y].pb(x);
    //cout << y << ' ' << x << " <- m" << '\n';
  }

  F.clear();

  // for y nodes
  for(auto u : Y){
    bool ok = 0;
    for(ll i = 0; i < F.size(); i++){
      if(Query(u, F[i][0], y) != y){
        F[i].pb(u);
        ok = 1;
        break;
      }
    }
    if(!ok){
      F.pb({u});
    }
  }
  F.pb(mid);

  for(auto vec : F){
    if(vec.size() == 0) continue;
    if(vec != mid) solve(vec);
    for(auto u : vec) col[u] = 0;
    vector < ll > potential_cands;
    for(auto u : vec){
      potential_cands.pb(u);
    }
    shuffle(potential_cands.begin(), potential_cands.end(), rng);
    ll node = potential_cands[0]; 
    col[node] = 1;
    for(ll i = 0; i < potential_cands.size(); i++){
      if(col[potential_cands[i]]) continue;
      ll z = Query(potential_cands[i], node, y);
      if(z == node){
        dfs(potential_cands[i]);
      }else{
        col[node] = 0;
        col[z] = 1;
        dfs(potential_cands[i]);
        dfs(node);
        node = z;
      }
    }
    v[y].pb(node);
    v[node].pb(y);
    //cout << node << ' ' << y << " <- y" << '\n';
  }
  return;
}

void Solve(int n) {
  vector < ll > a;
  for(ll i = 0; i < n; i++) a.pb(i);
  solve(a);
  for(ll i = 0; i < n; i++){
    for(auto u : v[i]){
      if(u > i) Bridge(i, u);
    }
  }
  return;
}

Compilation message (stderr)

meetings.cpp: In function 'void solve(std::vector<int>)':
meetings.cpp:60:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(ll i = 0; i < F.size(); i++){
      |                   ~~^~~~~~~~~~
meetings.cpp:84:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(ll i = 0; i < potential_cands.size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~
meetings.cpp:113:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for(ll i = 0; i < F.size(); i++){
      |                   ~~^~~~~~~~~~
meetings.cpp:137:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for(ll i = 0; i < potential_cands.size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~

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