제출 #950769

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
950769		Vladth11	ICC (CEOI16_icc)	C++14	100 / 100	83 ms	632 KiB

icc

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

#include "icc.h"

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

const ll NMAX = 101;
const ll INF = (1LL << 58);
const ll nrbits = 20;
const ll MOD = 998244353;
const int VMAX = 10;

int a[NMAX];
int b[NMAX];

set <int> st[NMAX];

int pa[NMAX];
int n;
int dsu(int x){
    if(pa[x] == x)
        return x;
    return pa[x] = dsu(pa[x]);
}

void merge(int a, int b){
    a = dsu(a);
    b = dsu(b);
    pa[b] = a;
    for(auto x : st[b])
        st[a].insert(x);
    st[b].clear();
}

int sol1, sol2;
int auxiliar[NMAX];
int nrAux, nrA, nrB;

int divideA(int st, int dr){
    if(st == dr)
        return a[st];
    int mid = (st + dr) / 2;
    nrAux = 0;
    for(int i = st; i <= mid; i++){
        auxiliar[nrAux++] = a[i];
    }
    int rez = query(nrAux, nrB, auxiliar, b);
    if(rez)
        return divideA(st, mid);
    return divideA(mid + 1, dr);
}

int divideB(int st, int dr){
    if(st == dr)
        return b[st];
    int mid = (st + dr) / 2;
    nrAux = 0;
    for(int i = st; i <= mid; i++){
        auxiliar[nrAux++] = b[i];
    }
    int rez = query(nrA, nrAux, a, auxiliar);
    if(rez)
        return divideB(st, mid);
    return divideB(mid + 1, dr);
}


int comp[NMAX];

void newEdge(){
    vector <int> cn;
    for(int i = 1; i <= n; i++){
        int rt = dsu(i);
        if(rt != i) continue;
        cn.push_back(i);
    }
    int acum = 0;
    for(int j = 0; j < 7; j++){
        nrA = 0;
        nrB = 0;
        for(int i = 0; i < cn.size(); i++){
            int x = cn[i];
            if(i & (1 << j)){
                for(auto y : st[x]){
                    a[nrA++] = y;
                    comp[y] = i;
                }
            }else{
                for(auto y : st[x]){
                    b[nrB++] = y;
                    comp[y] = i;
                }
            }
        }
        int rez = query(nrA, nrB, a, b);
        if(rez){
            acum = j;
            break;
        }
    }
    int primul = divideA(0, nrA - 1);
    vector <int> ramas;
    for(int i = 0; i < nrB; i++)
        ramas.push_back(b[i]);
    nrB = 0;
    for(auto x : ramas){
        int ok = 1;
        for(int j = 0; j < acum; j++){
            if((comp[x] & (1 << j)) != (comp[primul] & (1 << j))){
                ok = 0;
            }
        }
        if(ok){
            b[nrB++] = x;
        }
    }
    int doilea = divideB(0, nrB - 1);
    setRoad(primul, doilea);
    merge(primul, doilea);
}

void run(int N){
    n = N;
    int i;
    for(i = 1; i <= n; i++){
        pa[i] = i;
        st[i].insert(i);
    }
    for(i = 1; i < n; i++){
        newEdge();
    }
}

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

icc.cpp: In function 'void newEdge()':
icc.cpp:87:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int i = 0; i < cn.size(); i++){
      |                        ~~^~~~~~~~~~~

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