oj.uz

Submission #101250

# Submission time Handle Problem Language Result Execution time Memory
101250 2019-03-18T04:48:00 Z rocketninja7 ICC (CEOI16_icc) C++14
0 / 100
 294 ms 592 KB 
#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)];
    }
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 512 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 512 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 560 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 564 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 512 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 294 ms 592 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -