제출 #187312

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
187312		nicolaalexandra	ICC (CEOI16_icc)	C++14	0 / 100	6 ms	504 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
#define DIM 200
using namespace std;
vector <int> L[DIM];
int n,i,x,y,ok,nr_intv,k,k2;
int v[DIM],w[DIM],t[DIM],aux[DIM],viz[DIM];
pair <int,int> intv[DIM];
/*int query (int n, int m, int a[], int b[]){
    int ans;
    cout<<n<<" ";
    for (int i=0;i<n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    cout<<m<<" ";
    for (int i=0;i<m;i++)
        cout<<b[i]<<" ";
    cout<<endl;
    cin>>ans;
    return ans;
}
void setRoad (int x, int y){
    L[x].push_back(y);
    L[y].push_back(x);
}*/
int get_rad (int x){
    int aux = x;
    while (t[x] > 0)
        x = t[x];
    /*while (t[nr] > 0){
        int aux = t[nr];
        t[nr] = x;
        nr = aux;
    }*/
    return x;
}
void _union (int x, int y){
    int radx = get_rad (x), rady = get_rad (y);
    if (radx != rady){
        if (t[radx] < t[rady]){
            t[radx] += t[rady];
            t[rady] = radx;
        } else {
            t[rady] += t[radx];
            t[radx] = rady;
        }
    }
}
inline int cmp (int a, int b){
    return get_rad (a) < get_rad (b);
}
void divide1 (int v[], int k, int st, int dr){
    if (st == dr || ok)
        return;
    int mid = (st+dr)>>1;
    if (query(mid-st+1,dr-mid,v+st,v+mid+1)){
        /// inseamna ca cele doua noduri sunt in intervale diferite
        /// acum dau split pe intervalul mid+1...dr
        int le = mid+1, ri = dr;
        while (le < ri){
            int m = (le+ri)>>1;
            /// le...m
            if (query(mid-st+1,m-le+1,v+st,v+le)){ /// sigur nodul e in stanga
                ri = m;
            } else le = m+1;
        }
        y = v[le];
        int poz = le;
        /// acum trb sa aflu x
        le = st, ri = mid;
        while (le < ri){
            int m = (le+ri)>>1;
            /// le...m
            if (query(1,m-le+1,v+poz,v+le))
                ri = m;
            else le = m+1;
        }
        x = v[le];
        ok = 1;
        return;
    }
    divide1 (v,k,st,mid);
    divide1 (v,k,mid+1,dr);
}
void divide2 (int v[], int k, int w[], int k2, int st, int dr){
    if (!k2 || k < 1)
        return;
    if (st == dr){
        y = v[st];
        ok = 1;
        return;
    }
    int mid = (st+dr)>>1;
    if (query(k2,mid-st+1,w,v+st))
        divide2 (v,k,w,k2,st,mid);
    else divide2 (v,k,w,k2,mid+1,dr);
}
void divide3 (int v[], int k, int l, int r, int st, int dr){
    if (l == r || st == dr || ok)
        return;
    int m = (l+r)>>1; /// l,r,m sunt indicii intervalului
    int dim1 = intv[m].second-st+1, dim2 = dr-intv[m].second;
    if (query(dim1,dim2,v+st,v+intv[m].second+1)){
        /// am gasit bucatile, pot sa apuc sa le caut pe fiecare in parte
        int p = intv[m+1].first, u = dr;
        while (p < u){
            int mij = (p+u)>>1;
            if (query(dim1,mij-p+1,v+st,v+p))
                u = mij;
            else p = mij+1;
        }
        y = v[p];
        int poz = p;
        /// l am gasit pe y, acum trb sa l caut pe x in celalalt interval
        p = st, u = intv[m].second;
        while (p < u){
            int mij = (p+u)>>1;
            if (query(1,mij-p+1,v+poz,v+p))
                u = mij;
            else p = mij+1;
        }
        x = v[p];
        ok = 1;
        return;
    }
    divide3 (v,k,l,m,st,intv[m].second);
    divide3 (v,k,m+1,r,intv[m+1].first,dr);
}

void solve (){
    /// vr sa determin muchia x,y
    /// cazul 1: x si y nu au mai fost vizitate
    k = 0, k2 = 0, ok = 0;
    for (int i=1;i<=n;i++){
        if (!viz[i])
            v[k++] = i;
        else w[k2++] = i;
    }
    if (k > 1){ /// sa am cel putin doua elemente
        divide1 (v,k,0,k-1);
        if (ok)
            return;
    }
    /// cazul 2: x face parte dintr-o multime si y e nevizitat
    divide2 (v,k,w,k2,0,k-1);
    if (ok){
        /// acum trb sa l caut pe x
        aux[0] = y;
        int st = 0, dr = k2-1;
        while (st < dr){
            int mid = (st+dr)>>1;
            if (query(1,mid-st+1,aux,w+st))
                dr = mid;
            else st = mid+1;
        }
        x = w[st];

        return;
    }
    /// cazul 3: x si y fac parte fiecare dintr o multime
    /// sortez nodurile din multimi dupa tata, ca sa am intervale compacte care repr multimile
    sort (w,w+k2,cmp);

    /// acum principiul e asemanator cu cel de la primul caz
    /// obtin intervalele
    int val = 0;
    nr_intv = 0;
    for (int i=0;i<k2-1;i++){
        if (get_rad(w[i]) != get_rad(w[i+1])){
            intv[++nr_intv] = make_pair(val,i);
            val = i+1;
        }
    }
    intv[++nr_intv] = make_pair(val,k2-1);

    divide3 (w,k2,1,nr_intv,0,k2-1);
    return;
}
void run (int n){
    for (i=1;i<n;i++){
        solve();
        setRoad(x,y);
        _union (x,y);
        viz[x] = viz[y] = 1;
        //cout<<x<<" "<<y<<endl;
    }
}

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

icc.cpp: In function 'int get_rad(int)':
icc.cpp:27:9: warning: unused variable 'aux' [-Wunused-variable]
     int aux = x;
         ^~~

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