oj.uz

답안 #605108

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
605108 2022-07-25T13:05:32 Z pliam CEOI16_icc (CEOI16_icc) C++14
100 / 100
 145 ms 596 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 105

int par[MAXN],height[MAXN];
vector<int> elems[MAXN];
vector<int> ccs;

int find_set(int v){
    if(par[v]==v) return v;
    else return par[v]=find_set(par[v]);
}


void union_sets(int a,int b){
    a=find_set(a);
    b=find_set(b);
    if(a==b) return;
    if(height[a]<height[b]) swap(a,b);
    par[b]=a;
    if(height[a]==height[b]) height[a]++;
    for(int v:elems[b]){
        elems[a].push_back(v);
    }
}

vector<pair<vector<int>,vector<int>>> curr,case1,case2;
bool same_set;
bool all_one;
vector<int> white;
vector<int> black;

int query_case(vector<pair<vector<int>,vector<int>>> cas){
    white.clear();
    black.clear();
    for(auto p:cas){
        for(int c:p.first){
            for(int i:elems[c]){
                white.push_back(i);
            }
        }for(int c:p.second){
            for(int i:elems[c]){
                black.push_back(i);
            }
        }
    }
    int arr_white[white.size()];
    for(int i=0;i<white.size();i++){
        arr_white[i]=white[i];
    }
    int arr_black[black.size()];
    for(int i=0;i<black.size();i++){
        arr_black[i]=black[i];
    }
    return query(white.size(),black.size(),arr_white,arr_black);
}

int query_sets(){
    int arr_white[white.size()];
    for(int i=0;i<white.size();i++){
        arr_white[i]=white[i];
    }
    int arr_black[black.size()];
    for(int i=0;i<black.size();i++){
        arr_black[i]=black[i];
    }
    return query(white.size(),black.size(),arr_white,arr_black);
}

void construct_cases_same_set(){
    case1.clear();
    case2.clear();
    for(auto p:curr){
        if(p.first.size()==1) continue;
        //else cut it in half
        vector<int> firsth,secondh;
        int n=p.first.size();
        int mid=n/2;
        for(int i=0;i<mid;i++){
            firsth.push_back(p.first[i]);
        }for(int i=mid;i<n;i++){
            secondh.push_back(p.first[i]);
        }
        case1.push_back({firsth,secondh});
        case2.push_back({firsth,firsth});
        case2.push_back({secondh,secondh});
    }
}

void construct_cases_diff_set(){
    all_one=true;
    case1.clear();
    case2.clear();
    for(auto p:curr){
        vector<int> seta=p.first;
        vector<int> setb=p.second;
        //else cut them in half
        vector<int> set1,set2,set3,set4;
        int n=seta.size();
        int m=setb.size();
        int mid1=n/2;
        int mid2=m/2;
        for(int i=0;i<mid1;i++){
            set1.push_back(seta[i]);
        }for(int i=mid1;i<n;i++){
            set2.push_back(seta[i]);
        }
        for(int i=0;i<mid2;i++){
            set3.push_back(setb[i]);
        }for(int i=mid2;i<m;i++){
            set4.push_back(setb[i]);
        }
        if(n==m&&n==1){
            case1.push_back({set2,set4});
            case2.push_back({set2,set4});
        }else if(n==1){
            case1.push_back({set2,set3});
            case2.push_back({set2,set4});
            all_one=false;
        }else if(m==1){
            case1.push_back({set1,set4});
            case2.push_back({set2,set4});
            all_one=false;
        }else{
            case1.push_back({set1,set3}); case1.push_back({set4,set2});
            case2.push_back({set1,set4}); case2.push_back({set3,set2});
            all_one=false;
        }
    }
}

void construct_cases_cc(){
    case1.clear();
    case2.clear();
    int n=curr.size();
    int mid=n/2;
    for(int i=0;i<mid;i++){
        case1.push_back({curr[i].first,curr[i].second});
    }for(int i=mid;i<n;i++){
        case2.push_back({curr[i].first,curr[i].second});
    }
}

bool check_a(int a,int k){
    white.clear();
    for(int i=0;i<=k;i++){
        white.push_back(elems[a][i]);
    }
    return query_sets();
}

bool check_b(int b,int k){
    black.clear();
    for(int i=0;i<=k;i++){
        black.push_back(elems[b][i]);
    }
    return query_sets();
}

pair<int,int> find_edge(int N){
    same_set=true;
    ccs.clear();
    for(int i=1;i<=N;i++){
        if(par[i]==i) ccs.push_back(i);
    }
    curr={{ccs,ccs}};
    while(same_set){
        construct_cases_same_set();
        int ansq=query_case(case1);
        if(ansq){
            same_set=false;
            curr=case1;
            all_one=false;
        }else{
            curr=case2;
        }
    }
    //now we go to the second part
    while(1){
        construct_cases_diff_set();
        if(all_one) break;
        int ansq=query_case(case1);
        if(ansq)curr=case1;
        else curr=case2;
    }
    //now to the third part where we have pairs of cc's
    while(curr.size()>=2){
        construct_cases_cc();
        int ansq=query_case(case1);
        if(ansq) curr=case1;
        else curr=case2;
    }
    //now we have pair of cc's
    int a=curr[0].first[0];
    int b=curr[0].second[0];
    black=elems[b];
    int k=elems[a].size()-1;
    for(int bh=elems[a].size();bh>0;bh/=2){
        while(k-bh>=0&&check_a(a,k-bh)) k-=bh;
    }
    int edgea=elems[a][k];
    white={edgea};
    k=elems[b].size()-1;
    for(int bh=elems[b].size();bh>0;bh/=2){
        while(k-bh>=0&&check_b(b,k-bh)) k-=bh;
    }
    int edgeb=elems[b][k];
    return {edgea,edgeb};
}

void run(int N){
    for(int i=1;i<=N;i++){
        par[i]=i;
        elems[i]={i};
    }
    for(int i=1;i<=N-1;i++){
        pair<int,int> edge=find_edge(N);
        union_sets(edge.first,edge.second);
        setRoad(edge.first,edge.second);
    }
}

Compilation message

icc.cpp: In function 'int query_case(std::vector<std::pair<std::vector<int>, std::vector<int> > >)':
icc.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i=0;i<white.size();i++){
      |                 ~^~~~~~~~~~~~~
icc.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=0;i<black.size();i++){
      |                 ~^~~~~~~~~~~~~
icc.cpp: In function 'int query_sets()':
icc.cpp:61:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i=0;i<white.size();i++){
      |                 ~^~~~~~~~~~~~~
icc.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i=0;i<black.size();i++){
      |                 ~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 520 KB Ok! 668 queries used.
2 Correct 31 ms 524 KB Ok! 586 queries used.
3 Correct 31 ms 528 KB Ok! 586 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 524 KB Ok! 1634 queries used.
2 Correct 104 ms 536 KB Ok! 1436 queries used.
3 Correct 118 ms 536 KB Ok! 1564 queries used.
4 Correct 136 ms 536 KB Ok! 1631 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 596 KB Ok! 1569 queries used.
2 Correct 109 ms 536 KB Ok! 1591 queries used.
3 Correct 113 ms 588 KB Ok! 1467 queries used.
4 Correct 109 ms 468 KB Ok! 1638 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 548 KB Ok! 1499 queries used.
2 Correct 108 ms 544 KB Ok! 1441 queries used.
3 Correct 107 ms 548 KB Ok! 1480 queries used.
4 Correct 105 ms 544 KB Ok! 1500 queries used.
5 Correct 137 ms 536 KB Ok! 1618 queries used.
6 Correct 137 ms 524 KB Ok! 1569 queries used.

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 536 KB Ok! 1472 queries used.
2 Correct 96 ms 548 KB Ok! 1436 queries used.