제출 #101250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
101250		rocketninja7	ICC (CEOI16_icc)	C++14	0 / 100	294 ms	592 KiB

icc

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

set<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(set<int>::iterator it=children[temp[i]].begin();it!=children[temp[i]].end();it++){
            tempA.push_back(*it);
        }
    }
    for(int i=n/2;i<n;i++){
        tempB.push_back(temp[i]);
        for(set<int>::iterator it=children[temp[i]].begin();it!=children[temp[i]].end();it++){
            tempB.push_back(*it);
        }
    }
    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(set<int>::iterator it=children[temp[i]].begin();it!=children[temp[i]].end();it++){
                temp2.push_back(*it);
            }
        }
        ans.first=connection1(temp2, tempB.size(), b);
        vector<int> temp3;
        for(int i=n/2;i<n;i++){
            temp3.push_back(temp[i]);
            for(set<int>::iterator it=children[temp[i]].begin();it!=children[temp[i]].end();it++){
                temp3.push_back(*it);
            }
        }
        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);
        if(max(parent[ans.first], parent[ans.second])<=component.back()&&*lower_bound(component.begin(), component.end(), max(parent[ans.first], parent[ans.second]))==max(parent[ans.first], parent[ans.second])){
            component.erase(lower_bound(component.begin(), component.end(), max(parent[ans.first], parent[ans.second])));
        }
        children[min(parent[ans.first], parent[ans.second])].insert(max(parent[ans.first], parent[ans.second]));
        for(set<int>::iterator it=children[max(parent[ans.first], parent[ans.second])].begin();it!=children[max(parent[ans.first], parent[ans.second])].end();it++){
            children[min(parent[ans.first], parent[ans.second])].insert(*it);
        }
        parent[max(ans.first, ans.second)]=parent[min(ans.first, ans.second)];
    }
}

컴파일 시 표준 에러 (stderr) 메시지

icc.cpp: In function 'std::pair<int, int> connection2(std::vector<int>)':
icc.cpp:53:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tempA.size();i++){
                 ~^~~~~~~~~~~~~
icc.cpp:56:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<tempB.size();i++){
                 ~^~~~~~~~~~~~~

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