Submission #258218

#	Time	Username	Problem	Language	Result	Execution time	Memory
258218		m3r8	ICC (CEOI16_icc)	C++14	100 / 100	199 ms	1912 KiB

icc

#include <stdio.h>
#include "icc.h"
#include <vector>
#include <set>
#include <utility>
#include <stdlib.h>
#include <algorithm>

#define ii std::pair<int,int>
std::vector<int> nd[50000];

int par[300];
int qryA[300];
int qryB[300];

int q1(std::vector<int> &a1, std::vector<int> &a2){
  int sa = 0;
  int sb = 0;
  for(int i: a1){
    for(int j:nd[i]){
      qryA[sa] = j;
      sa++;
    };  
  };
  for(int i: a2){
    for(int j:nd[i]){
      qryB[sb] = j;
      sb++;
    };  
  };
  if(sa == 0 || sb == 0)return 0;
  return query(sa,sb,qryA,qryB);
};

ii findCC(std::vector<int> lf, std::vector<int> rg,int fg){
  if(lf.size() == 1 && rg.size() == 1)return {lf[0],rg[0]};
  if(fg == 0 && lf.size() == 1)return findCC(lf,rg,1);
  std::vector<int> l1,l2;
  std::vector<int> r1,r2;
  if(fg == 0){
    for(int i = 0;i<lf.size();i++){
      if(i%2)l2.push_back(lf[i]);  
      else l1.push_back(lf[i]);
    };
    if(q1(l1,rg))return findCC(l1,rg,0);
    else return findCC(l2,rg,0);
  }else{
    for(int i = 0;i<rg.size();i++){
      if(i%2)r2.push_back(rg[i]);  
      else r1.push_back(rg[i]);
    };
    if(q1(lf,r1))return findCC(lf,r1,1);
    else return findCC(lf,r2,1);
  };
};

ii findC(std::vector<int> akt){
  if(akt.size() == 0)return {-1,-1}; 
  if(akt.size() == 1)return {-1,-1};
  if(akt.size() == 2){
    std::vector<int> t1 = {akt[0]};
    std::vector<int> t2 = {akt[1]};
    if(q1(t1,t2)){
      std::vector<int> l1,r1;
      for(auto i: nd[akt[0]])l1.push_back(i);
      for(auto i: nd[akt[1]])r1.push_back(i);
      return findCC(l1,r1,0);
    }else{
      return {-1,-1};  
    };
  }else{
    std::vector<int> lf;
    std::vector<int> rg;
    std::vector<int> pos;
    for(int i = 0;i<10;i++)pos.push_back(i);
    int pp = rand()%pos.size();
    int pw = (1<<pos[pp]);
    pos.erase(pos.begin() + pp);
    while(true){
      lf.clear();  
      rg.clear();
      for(int i = 0;i<akt.size();i++){
        if(i&pw)lf.push_back(akt[i]);  
        else rg.push_back(akt[i]);
      };
      int tmp = q1(lf,rg);
      if(tmp)break;
      else{
        pp = rand()%pos.size();
        pw = (1<<pos[pp]);
        pos.erase(pos.begin() + pp);
      };
    };
    std::vector<int> l1,r1;
    for(auto i: lf)
      for(auto j: nd[i])l1.push_back(j);  
    for(auto i: rg)
      for(auto j: nd[i])r1.push_back(j);  
    return findCC(l1,r1,0);
  };
};



void run(int N){
  int cn = N+1;
  std::vector<int> nodes;
  for(int i = 1;i<=N;i++){
    nodes.push_back(i);
    nd[i].push_back(i);
    par[i] = i;
  };
  for(int g = 0;g<N-1;g++){
    ii tmp = findC(nodes);
    setRoad(tmp.first,tmp.second);
    std::vector<int> ttp;
    int p1 = par[tmp.first];
    int p2 = par[tmp.second];
    for(int i: nodes){
      if(i != p1 && i != p2)ttp.push_back(i);  
    };
    for(auto i: nd[p1]){
      par[i] = cn;  
      nd[cn].push_back(i);
    };
    for(auto i: nd[p2]){
      par[i] = cn;  
      nd[cn].push_back(i);
    };
    nodes = ttp;
    nodes.push_back(cn++);
  };
};
/*
int adj[120][120];
std::vector<ii> rd; 


int qcnt = 0;
int query(int size_a, int size_b ,int a[], int b[]){
  qcnt++;
  //printf("query: %d %d\n",size_a,size_b);
  //for(int i = 0;i<size_a;i++)printf("%d ",a[i]);
  //puts("");
  //for(int i = 0;i<size_b;i++)printf("%d ",b[i]);
  //puts("");
  for(int i = 0;i<size_a;i++){
    for(int j = 0;j<size_b;j++){
      if(adj[a[i]][b[j]]){
       // printf("return 1\n");
        return 1;
      };  
    };
  };
  //printf("return: 0\n");
  return 0;
};
int cnt = 0;
int pqcnt = 0;
void setRoad(int a, int b){
  printf("SetRoad %d %d %d\n",a,b,qcnt-pqcnt);
  pqcnt = qcnt;
  if(rd[cnt].first == a && rd[cnt].second == b){
    cnt++;  
    if(cnt == rd.size())return;
    adj[rd[cnt].first][rd[cnt].second] = 1;
    adj[rd[cnt].second][rd[cnt].first] = 1;
  }else if(rd[cnt].first == b && rd[cnt].second == a){
    cnt++;  
    if(cnt == rd.size())return;
    adj[rd[cnt].first][rd[cnt].second] = 1;
    adj[rd[cnt].second][rd[cnt].first] = 1;
  }else{
    printf("Error\n");  
    exit(0);
  };
};


int main(void){
  int n;  
  scanf("%d",&n);
  int a,b;
  for(int i = 0;i<n-1;i++){
    scanf("%d %d",&a,&b);
    rd.push_back({a,b});
  };
  adj[rd[cnt].first][rd[cnt].second] = 1;
  adj[rd[cnt].second][rd[cnt].first] = 1;
  run(n);
  printf("nice %d\n",qcnt);
  return 0;
};
*/

Compilation message (stderr)

icc.cpp: In function 'std::pair<int, int> findCC(std::vector<int>, std::vector<int>, int)':
icc.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<lf.size();i++){
                   ~^~~~~~~~~~
icc.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<rg.size();i++){
                   ~^~~~~~~~~~
icc.cpp: In function 'std::pair<int, int> findC(std::vector<int>)':
icc.cpp:82:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0;i<akt.size();i++){
                     ~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10