Submission #101242

#	Time	Username	Problem	Language	Result	Execution time	Memory
101242		rocketninja7	ICC (CEOI16_icc)	C++14	0 / 100	31 ms	952 KiB

icc

#include "icc.h"
#include <vector>
using namespace std;

vector<int> children[101];
int parent[101];

int connection1(vector<int> temp, int an, int a[]){
    if(temp.size()==1){
        return temp[0];
    }
    int n=temp.size();
    int b1[n/2];
    for(int i=0;i<n/2;i++){
        b1[i]=temp[i];
    }
    if(query(an, n/2, a, b1)){
        vector<int> temp2;
        for(int i=0;i<n/2;i++){
            temp2.push_back(temp[i]);
        }
        return connection1(temp2, an, a);
    }
    else{
        vector<int> temp2;
        for(int i=n/2;i<n;i++){
            temp2.push_back(temp[i]);
        }
        return connection1(temp2, an, a);
    }
}

pair<int, int> connection2(vector<int> temp){
    int n=temp.size();
    if(n<2){
        return make_pair(0, 0);
    }
    vector<int> tempA, tempB;
    for(int i=0;i<n/2;i++){
        tempA.push_back(temp[i]);
        for(int j=0;j<children[temp[i]].size();j++){
            tempA.push_back(children[temp[i]][j]);
        }
    }
    for(int i=n/2;i<n;i++){
        tempB.push_back(temp[i]);
        for(int j=0;j<children[temp[i]].size();j++){
            tempB.push_back(children[temp[i]][j]);
        }
    }
    int a[tempA.size()], b[tempB.size()];
    for(int i=0;i<tempA.size();i++){
        a[i]=tempA[i];
    }
    for(int i=0;i<tempB.size();i++){
        b[i]=tempB[i];
    }
    if(query(tempA.size(), tempB.size(), a, b)){
        pair<int, int> ans;
        vector<int> temp2;
        for(int i=0;i<n/2;i++){
            temp2.push_back(temp[i]);
            for(int j=0;j<children[temp[i]].size();j++){
                temp2.push_back(children[temp[i]][j]);
            }
        }
        ans.first=connection1(temp2, tempB.size(), b);
        vector<int> temp3;
        for(int i=n/2;i<n;i++){
            temp3.push_back(temp[i]);
            for(int j=0;j<children[temp[i]].size();j++){
                temp3.push_back(children[temp[i]][j]);
            }
        }
        ans.second=connection1(temp3, tempA.size(), a);
        return ans;
    }
    else{
        vector<int> temp2;
        for(int i=0;i<n/2;i++){
            temp2.push_back(temp[i]);
        }
        pair<int, int> ans=connection2(temp2);
        if(ans==make_pair(0, 0)){
            vector<int> temp3;
            for(int i=n/2;i<n;i++){
                temp3.push_back(temp[i]);
            }
            return connection2(temp3);
        }
        return ans;
    }
}

void run(int n) {
    vector<int> component;
    for(int i=1;i<=n;i++){
        component.push_back(i);
        parent[i]=i;
    }
    for(int i=0;i<n-1;i++){
        pair<int, int> ans=connection2(component);
        setRoad(ans.first, ans.second);
        component.erase(lower_bound(component.begin(), component.end(), max(ans.first, ans.second)));
        children[parent[min(ans.first, ans.second)]].push_back(max(ans.first, ans.second));
        for(int j=0;j<children[max(ans.first, ans.second)].size();j++){
            children[parent[min(ans.first, ans.second)]].push_back(children[max(ans.first, ans.second)][j]);
        }
        parent[max(ans.first, ans.second)]=parent[min(ans.first, ans.second)];
    }
}

Compilation message (stderr)

icc.cpp: In function 'std::pair<int, int> connection2(std::vector<int>)':
icc.cpp:41:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<children[temp[i]].size();j++){
                     ~^~~~~~~~~~~~~~~~~~~~~~~~~
icc.cpp:47:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<children[temp[i]].size();j++){
                     ~^~~~~~~~~~~~~~~~~~~~~~~~~
icc.cpp:52:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tempA.size();i++){
                 ~^~~~~~~~~~~~~
icc.cpp:55:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tempB.size();i++){
                 ~^~~~~~~~~~~~~
icc.cpp:63:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<children[temp[i]].size();j++){
                         ~^~~~~~~~~~~~~~~~~~~~~~~~~
icc.cpp:71:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<children[temp[i]].size();j++){
                         ~^~~~~~~~~~~~~~~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:106:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<children[max(ans.first, ans.second)].size();j++){
                     ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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