oj.uz

Submission #231066

# Submission time Handle Problem Language Result Execution time Memory
231066 2020-05-12T14:31:50 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,el;
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){
    cout<<x<<" "<<y<<endl;
}
*/

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 (t[radx] < t[rady]){
        t[radx] += t[rady];
        t[rady] = radx;
    } else {
        t[rady] += t[radx];
        t[radx] = rady;
    }

}

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

    for (int bit=0;bit<8;bit++){
        k = 0, k2 = 0;

        for (int i=1;i<=n;i++){
            int val = get_rad(i);
            if (val&(1<<bit))
                a[k++] = i;
            else b[k2++] = i;
        }

        if (!k || !k2)
            continue;

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

            int val = k;
            while (val > 1){
                int mid = val/2;

                if (query(mid,k2,a,b))
                    val = mid;
                else {
                    for (int i=mid;i<val;i++)
                        a[i-mid] = a[i];
                    val -= mid;
                }
            }
            x = a[0], k = 1;

            val = k2;
            while (val > 1){
                int mid = val/2;

                if (query(k,mid,a,b))
                    val = mid;
                else {
                    for (int i=mid;i<val;i++)
                        b[i-mid] = b[i];
                    val -= mid;
                }
            }
            y = b[0], k2 = 1;

            _union (x,y);

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

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 4 ms 384 KB Wrong road!
2 Halted 0 ms 0 KB -