oj.uz

답안 #983548

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
983548 2024-05-15T17:11:33 Z FZ_Melo CEOI16_icc (CEOI16_icc) C++14
0 / 100
 1 ms 856 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

int n;
int arr1[101], arr2[101];
set<int> componentes;
vector<vector<int>> nums;

int buscaComp1(int t1, int t2){
    int l=0, r=t1-1;
    int aux[101];
    while(l<r){
        int mid=(l+r)/2;
        int pos=0;
        for(int i=l; i<=mid; i++)
            aux[pos++]=arr1[i];
        if(query(pos, t2, aux, arr2))
            r=mid;
        else
            l=mid+1;
    }
    return arr1[l];
}

int buscaComp2(int a, int t2){
    int l=0, r=t2-1;
    int aux[101];
    int ya[]={a};
    while(l<r){
        int mid=(l+r)/2;
        int pos=0;
        for(int i=l; i<=mid; i++)
            aux[pos++]=arr2[i];
        if(query(1, t2, ya, aux))
            r=mid;
        else
            l=mid+1;
    }
    return arr2[l];
}

pair<int, int> buscaComp(){
    int p1=0, p2=0;
    int t=componentes.size(), cnt=0;
    int a, b;
    for(auto it: componentes){
        if(cnt<t/2){
            for(int x: nums[it])
                arr1[p1++]=x;
        }
        else{
            for(int x: nums[it])
                arr2[p2++]=x;
        }
        cnt++;
    }
    if(query(p1, p2, arr1, arr2)){
        a=buscaComp1(p1, p2);
        b=buscaComp2(a, p2);
    }
    else{
        p2=0;
        for(int i=p1/2; i<p1; i++){
            arr2[p2++]=arr1[i];
        }
        p1/=2;
        if(query(p1, p2, arr1, arr2)){
            a=buscaComp1(p1, p2);
            b=buscaComp2(a, p2);
        }
        else{
            p1=p2=0;
            cnt=0;
            for(auto it: componentes){
                if(cnt>=t/2){
                    for(int x: nums[it])
                        arr1[p1++]=x;
                }
                cnt++;
            }
            for(int i=p1/2; i<p1; i++){
                arr2[p2++]=arr1[i];
                p1/=2;
                a=buscaComp1(p1, p2);
                b=buscaComp2(a, p2);
            }
        }
    }
    return {a, b};
}

int buscaNode1(int c1, int c2){
    int l=0, r=nums[c1].size()-1;
    int aux[101];
    while(l<r){
        int mid=(l+r)/2;
        int pos=0;
        for(int i=l; i<=mid; i++){
            aux[pos++]=arr1[i];
        }
        if(query(pos, nums[c2].size(), aux, arr2))
            r=mid;
        else
            l=mid+1;
    }
    return arr1[l];
}

int buscaNode2(int a, int c2){
    int l=0, r=nums[c2].size()-1;
    int aux[101];
    int ya[]={a};
    while(l<r){
        int mid=(l+r)/2;
        int pos=0;
        for(int i=l; i<=mid; i++){
            aux[pos++]=arr2[i];
        }
        if(query(1, pos, ya, aux))
            r=mid;
        else
            l=mid+1;
    }
    return arr2[l];
}


pair<int, int> buscaNode(int c1, int c2){
    int p1=0, p2=0;
    for(int x: nums[c1]){
        arr1[p1++]=x;
    }
    for(int x: nums[c2]){
        arr2[p2++]=x;
    }
    int a, b;
    a=buscaNode1(c1, c2);
    b=buscaNode2(a, c2);
    if(nums[c1].size()>=nums[c2].size()){
        componentes.erase(c2);
        for(int x: nums[c2]){
            nums[c1].push_back(x);
        }
    }
    else{
        componentes.erase(c1);
        for(int x: nums[c1]){
            nums[c2].push_back(x);
        }
    }
    return {a, b};
}

void run(int N){
    n=N;
    nums.clear();
    componentes.clear();
    nums.resize(n+1);
    for(int i=1; i<=n; i++){
        componentes.insert(i);
        nums[i].push_back(i);
    }
    for(int k=0; k<n-1; k++){
        pair<int, int> comp=buscaComp();
        pair<int, int> node=buscaNode(comp.first, comp.second);
        setRoad(node.first, node.second);
    }
}

Compilation message

icc.cpp: In function 'std::pair<int, int> buscaComp()':
icc.cpp:90:17: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |     return {a, b};
      |                 ^
icc.cpp:90:17: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB Query cities not in range [1, n]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 760 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 856 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB Wrong road!
2 Halted 0 ms 0 KB -