Submission #821758

#	Time	Username	Problem	Language	Result	Execution time	Memory
821758		farhan132	Meetings (JOI19_meetings)	C++17	0 / 100	78 ms	984 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];

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]);
    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) X.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){
    solve(vec);
    vector < ll > potential_cands;
    for(auto u : vec){
      potential_cands.pb(u);
    }
    shuffle(potential_cands.begin(), potential_cands.end(), rng);
    ll node = potential_cands.back();
    for(ll i = 0; i + 1 < potential_cands.size(); i+=2){
      ll z = Query(potential_cands[i], potential_cands[i + 1], x);
      if(z == potential_cands[i]){
        node = potential_cands[i];
        break;
      }
      if(z == potential_cands[i + 1]){
        node = potential_cands[i + 1];
        break;
      }
    }
    v[x].pb(node);
    v[node].pb(x);
  }

  F.clear();
  F.shrink_to_fit();

  // 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 != mid) solve(vec);
    vector < ll > potential_cands;
    for(auto u : vec){
      potential_cands.pb(u);
    }
    shuffle(potential_cands.begin(), potential_cands.end(), rng);
    ll node = potential_cands.back();
    for(ll i = 0; i + 1 < potential_cands.size(); i+=2){
      ll z = Query(potential_cands[i], potential_cands[i + 1], y);
      if(z == potential_cands[i]){
        node = potential_cands[i];
        break;
      }
      if(z == potential_cands[i + 1]){
        node = potential_cands[i + 1];
        break;
      }
    }
    v[y].pb(node);
    v[node].pb(y);
  }
  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:51: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]
   51 |     for(ll i = 0; i < F.size(); i++){
      |                   ~~^~~~~~~~~~
meetings.cpp:71:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(ll i = 0; i + 1 < potential_cands.size(); i+=2){
      |                   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
meetings.cpp:92: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]
   92 |     for(ll i = 0; i < F.size(); i++){
      |                   ~~^~~~~~~~~~
meetings.cpp:113:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for(ll i = 0; i + 1 < potential_cands.size(); i+=2){
      |                   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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