Submission #780709

#	Time	Username	Problem	Language	Result	Execution time	Memory
780709		vjudge1	Simurgh (IOI17_simurgh)	C++17	70 / 100	79 ms	8452 KiB

simurgh

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

#define all(x) (x).begin(),(x).end()
using namespace std;

//#define ask count_common_roads 

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 500;

vector<pii> g[nmax];
vector<int> occ;
vector<int> candr;
int flag;

int cnt = 0;
int ask(vector<int> r) {
  return count_common_roads(r);
}

void dfs(int x) {
  occ[x] = flag;
  for(auto [y, ptr] : g[x]) {
    if(occ[y] != 0) continue;
    //cerr << x << ' ' << y << '\t' << ptr << '\n';
    occ[y] = flag;
    candr.emplace_back(ptr);
    dfs(y);
  }
  return;
}

int mat[nmax][nmax];
  vector<int> isgood;
  vector<int> checked;

void solvefori(int i) {
  fill(all(occ), 0);
  candr.clear();
  occ[i] = -1;
  vector<vector<int>> atrs;
  atrs.emplace_back();
  vector<int> nv;
  flag = 0;
  for(auto [x, ptr] : g[i]) {
    if(occ[x] == 0) {
      flag++;
      dfs(x);
      nv.emplace_back(ptr);
      atrs.emplace_back();
      atrs.back().emplace_back(ptr);
    }
    else
      atrs[occ[x]].emplace_back(ptr);
  }
  
  int startmn = sz(candr) - 1;
  copy(all(nv), back_inserter(candr));
  
  for(int i = 1; i <= flag; i++) {
    //cerr << "--\n";
    vector<int> rez;
    int mx = -1; 
    for(int j = 0; j < sz(atrs[i]); j++) {
      int u = atrs[i][j];
      candr[startmn + i] = u;
      if(checked[u] && isgood[u]) { mx = ask(candr); break; }
    }
    for(int j = 0; j < sz(atrs[i]); j++) {
      int u = atrs[i][j];
      candr[startmn + i] = u;
      if(!checked[u])
        rez.emplace_back(ask(candr));
      else
        rez.emplace_back(-1);
    }
    if(mx == -1)
      mx = *max_element(all(rez));
    for(int j = 0; j < sz(atrs[i]); j++) {
      checked[atrs[i][j]] = 1;
      if(rez[j] == mx)
        isgood[atrs[i][j]] = 1;
    }
  }
}

vector<int> S4(int n, vector<int> u, vector<int> v) {
  for(int i = 0; i < sz(u); i++) {
    mat[u[i]][v[i]] = i;
    mat[v[i]][u[i]] = i;
    
    g[u[i]].emplace_back(v[i], i);
    g[v[i]].emplace_back(u[i], i);
  }
  
  //cerr << "yura\n";
  solvefori(0);
  for(int j = 1; j < n; j++) checked[mat[j][0]] = 1;
  for(int i = 1; i < n; i++) {
    vector<int> crr;
    for(int j = 0; j < n; j++) {
      if(j == i) continue;
      crr.emplace_back(mat[i][j]);
    }
    int totaltf = ask(crr);
    for(int j = 0; j < i; j++)
      totaltf -= isgood[mat[i][j]];
    for(int smth = 0; smth < totaltf; smth++) {
      auto trywith = [&](int lim) {
        vector<int> ntwr;
        ntwr.emplace_back(mat[0][i]);
        int expected = isgood[mat[0][i]];
        for(int j = 1; j <= lim; j++) {
          if(j == i) continue;
          ntwr.emplace_back(mat[i][j]);
          if(checked[mat[i][j]]) expected += isgood[mat[i][j]];
        }
        for(int j = lim + 1; j < n; j++) {
          if(j == i) continue;
          ntwr.emplace_back(mat[0][j]);
          if(checked[mat[0][j]]) expected += isgood[mat[0][j]];
        }
        return ask(ntwr) - expected;
      };
      int lim = i - 1;
      
      for(int i = 9; i >= 0; i--) {
        if(lim + (1 << i) >= n) continue;
        if(trywith(lim + (1 << i)) <= 0) lim += (1 << i);
      }
      lim++;
      checked[mat[i][lim]] = 1;
      isgood[mat[i][lim]] = 1;
    }
    
    for(int j = 0; j < n; j++) {
      if(j == i) continue;
      checked[mat[i][j]] = 1;
    }
      
  }
  vector<int> lst;
  for(int i = 0; i < sz(isgood); i++)
    if(isgood[i])
      lst.emplace_back(i);
  return lst;
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
  isgood.resize(sz(u));
  checked.resize(sz(u));
  occ.resize(n);
  if(n > 240)
   return S4(n, u, v);
  for(int i = 0; i < sz(u); i++) {
    g[u[i]].emplace_back(v[i], i);
    g[v[i]].emplace_back(u[i], i);
  }
  
  for(int i = 0; i < n; i++) {
    solvefori(i);
  }
  
  vector<int> lst;
  for(int i = 0; i < sz(isgood); i++)
    if(isgood[i])
      lst.emplace_back(i);
  
  //for(auto x : lst)
    //cerr << x << ' ';
  //cerr << '\n';
  
  return lst;
}



/**
      Anul asta se da centroid.
-- Surse oficiale
*/

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 0 / 30