oj.uz

Submission #231054

# Submission time Handle Problem Language Result Execution time Memory
231054 2020-05-12T12:52:57 Z nicolaalexandra ICC (CEOI16_icc) C++14
0 / 100
 5 ms 384 KB 
#include <bits/stdc++.h>
#include "icc.h"
#define DIM 200
using namespace std;
vector <int> L[DIM],comp[DIM],w;
int n,i,x,y,k,k2;
int v[DIM],t[DIM],aux[DIM],a[DIM],b[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){
    while (t[x] > 0)
        x = t[x];
    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;
        }
    }
}


void solve2 (int n, int m, int a[], int b[]){
    int st = 0, dr = n-1;
    while (st <= dr){
        int mid = (st+dr)>>1;

        int el = 0;
        aux[el++] = a[mid];

        if (query(el,m,aux,b)){
            x = a[mid];
            break;
        }

        el = 0;
        for (int i=st;i<=mid;i++)
            aux[el++] = a[i];

        if (query(el,m,aux,b)) /// clar se afla in stanga
            dr = mid-1;
        else st = mid+1;
    }

    n = 1;
    a[0] = x;

    st = 0, dr = m-1;
    while (st <= dr){
        int mid = (st+dr)>>1;

        int el = 0;
        aux[el++] = b[mid];
        if (query(n,el,a,aux)){
            y = b[mid];
            break;
        }

        el = 0;
        for (int i=st;i<=mid;i++)
            aux[el++] = b[i];
        if (query(n,el,a,aux))
            dr = mid-1;
        else st = mid+1;
    }

}

void solve (){
    /// impart componentele conexe in doua multimi

    for (int i=1;i<=n;i++)
        comp[i].clear();

    w.clear();
    for (int i=1;i<=n;i++){
        comp[get_rad(i)].push_back(i);
        if (t[i] < 0)
            w.push_back(i);
    }

    for (int bit=0;(1<<bit)<=w.size();bit++){
        k = 0, k2 = 0;
        for (auto it : w){
            if (it&(1<<bit)){
                for (auto val : comp[it])
                    a[k++] = val;
            } else {
                for (auto val : comp[it])
                    b[k2++] = val;
            }
        }

        if (!k || !k2)
            continue;

        if (query(k,k2,a,b)){ /// am gasit cele doua multimi

            solve2 (k,k2,a,b);

            break;
        }
    }

}
void run (int n){
    memset (t,-1,sizeof t);
    for (int i=1;i<n;i++){
        solve();
        setRoad(x,y);
        _union (x,y);
        //cout<<x<<" "<<y<<endl;
    }
}

Compilation message

icc.cpp: In function 'void solve()':
icc.cpp:106:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int bit=0;(1<<bit)<=w.size();bit++){
                    ~~~~~~~~^~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 29.0

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

Subtask #6
0 / 10.0

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