oj.uz

Submission #101242

# Submission time Handle Problem Language Result Execution time Memory
101242 2019-03-18T04:15:32 Z rocketninja7 ICC (CEOI16_icc) C++14
0 / 100
 31 ms 952 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.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 #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 828 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -