oj.uz

답안 #607285

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
607285 2022-07-26T14:26:44 Z DanerZein CEOI16_icc (CEOI16_icc) C++14
7 / 100
 110 ms 848 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N=110;
int pa[MAX_N];
void init(int n){
  for(int i=0;i<=n;i++) pa[i]=i;
}
int findset(int x){
  if(pa[x]==x) return x;
  return pa[x]=findset(pa[x]);
}
bool issameset(int i,int j){
  return findset(i)==findset(j);
}
void unionset(int i,int j){
  if(!issameset(i,j)){
    int u=findset(i),v=findset(j);
    pa[u]=v;
  }
}
int c=0;
int myQuery(vector<int> y,vector<int> x){
  int t=y.size();
  int *qu1=new int[t];
  for(int i=0;i<t;i++)
    qu1[i]=y[i];
  
  t=x.size();
  int *qu2=new int[t];
  for(int i=0;i<t;i++)
    qu2[i]=x[i];
  c++;
  return query(y.size(),x.size(),qu1,qu2);
}
vector<int> firstHalf(vector<int> x){
  vector<int> f;
  for(int i=0;i<x.size()/2;i++) f.push_back(x[i]);
  return f;
}
vector<int> secondHalf(vector<int> x){
  vector<int> f;
  for(int i=x.size()/2;i<x.size();i++) f.push_back(x[i]);
  return f;
}
void divide(vector<int> y,vector<int> x){
  if(x.size()==1 && y.size()==1){
    //cout<<x[0]<<" "<<y[0]<<endl;
    setRoad(x[0],y[0]);
    unionset(x[0],y[0]);
    return;
  }
  vector<int> y1=firstHalf(y),y2=secondHalf(y);
  vector<int> x1=firstHalf(x),x2=secondHalf(x);
  if(myQuery(x1,y1)) divide(x1,y1);
  else if(myQuery(x1,y2)) divide(x1,y2);
  else if(myQuery(x2,y1)) divide(x2,y1);
  else divide(x2,y2);
}
int N;
vector<int> conjun(vector<int> x){
  vector<int> con;
  for(int i=0;i<x.size();i++){
    for(int j=1;j<=N;j++){
      if(issameset(x[i],j)) con.push_back(j);
    }
  }
  return con;
}
void divCon(vector<int> y,vector<int> x){
  vector<int> y1=firstHalf(y),y2=secondHalf(y);
  vector<int> x1=firstHalf(x),x2=secondHalf(x);
  if(x.size()==1 && y.size()==1){
    divide(conjun(x),conjun(y));
    return;
  }
  if(myQuery(conjun(x1),conjun(y1))) divCon(x1,y1);
  else if(myQuery(conjun(x2),conjun(y1))) divCon(x2,y1);
  else if(myQuery(conjun(x1),conjun(y2))) divCon(x1,y2);
  else divCon(x2,y2);
  
}
void findUnion(vector<int> con){
  int k=log2(con.size());
  for(int i=0;i<k;i++){
    vector<int> c1,c2;
    for(int j=0;j<con.size();j++){
      if(j&(1<<i)) c1.push_back(con[j]);
      else c2.push_back(con[j]);
    }
    if(myQuery(conjun(c1),conjun(c2))){
      divCon(c1,c2);
      return;
    }
  }
}
void run(int n){
  N=n;
  init(n);
  for(int k=0;k<n-1;k++){
    vector<int> con;
    for(int i=1;i<=n;i++) con.push_back(findset(i));
    sort(con.begin(),con.end());
    con.erase(unique(con.begin(),con.end()),con.end());
    findUnion(con);
  }
}

Compilation message

icc.cpp: In function 'std::vector<int> firstHalf(std::vector<int>)':
icc.cpp:38:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for(int i=0;i<x.size()/2;i++) f.push_back(x[i]);
      |               ~^~~~~~~~~~~
icc.cpp: In function 'std::vector<int> secondHalf(std::vector<int>)':
icc.cpp:43:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int i=x.size()/2;i<x.size();i++) f.push_back(x[i]);
      |                        ~^~~~~~~~~
icc.cpp: In function 'std::vector<int> conjun(std::vector<int>)':
icc.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int i=0;i<x.size();i++){
      |               ~^~~~~~~~~
icc.cpp: In function 'void findUnion(std::vector<int>)':
icc.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int j=0;j<con.size();j++){
      |                 ~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 468 KB Ok! 230 queries used.
2 Correct 6 ms 468 KB Ok! 223 queries used.

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 548 KB Ok! 1240 queries used.
2 Incorrect 16 ms 468 KB Not all edges were guessed!
3 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 110 ms 800 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 632 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 62 ms 720 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 848 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -