oj.uz

Submission #570107

# Submission time Handle Problem Language Result Execution time Memory
570107 2022-05-28T14:36:40 Z MatijaL ICC (CEOI16_icc) C++17
0 / 100
 19 ms 592 KB 
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
typedef long long ll;
#define pll pair<ll, ll>
#define loop(i, n) for(ll i = 0; i < n; i++)
#define FOR(i,n,m) for(ll i = n; i <= m; i++)
#define isIn(vec, item) find(vec.begin(), vec.end(), item) != vec.end()
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define inf 1500000005
#define mod 1500000007
#define print(v) for(auto e : v) cout << e << " "; cout << endl;

int cnt=0;
int cnt1=0;
int cnt2=0;

vector<int> mpr(200);

/*
int query(int s_a, int s_b, int a[], int b[]){
    printf("Query\n");
    FOR(i, 0, s_a-1) printf("%d ", a[i]);
    printf("\n");
    FOR(i, 0, s_b-1) printf("%d ", b[i]);
    printf("\n");
    cnt++;
    int ans;
    cin >> ans;
    return ans;
}

void setRoad(int a, int b){
    printf("Set road %d %d\n",a,b);
}*/

int par[200], sz[200];
int find(ll a){
    if(par[a]==a)return a;
    return par[a]=find(par[a]);
}
void un(int a, int b){
    a=find(a);b=find(b);
    if(a==b) return;
    if(sz[b]>sz[a]) swap(a, b);
    par[b]=a;
    sz[a]+=sz[b];
}
vector<int> cmp;
set<int> comps;

bool comp_query(vector<int> a, vector<int> b){
    vector<int> u, v;
    for(auto e : a){
        FOR(i, 1, 150){
            if(find(i)==e)u.pb(mpr[i]);
        }
    }
    for(auto e : b){
        FOR(i, 1, 150){
            if(find(i)==e)v.pb(mpr[i]);
        }
    }
    if(min(u.size(), v.size())==0) return false;
    return query(u.size(), v.size(), &u[0], &v[0]);
}

bool out=0;
pll f(int l, int r){
    if(l>=r || out) return mp(0, 0);
    vector<int> a, b;
    int m=(l+r)/2;
    FOR(i, l, m) a.pb(cmp[i]);
    FOR(i, m+1, r) b.pb(cmp[i]);
    bool ans = comp_query(a, b);
    if(ans) {out=1;return mp(l, r);}
    else if(l+1==r) return mp(0,0);
    else return max(f(l, m), f(m+1, r));
}

int g(int l, int r, int l_b, int r_b){
    vector<int> b;
    FOR(i, l_b, r_b)b.pb(cmp[i]);
    int m;
    while(l!=r){
        m=(l+r)/2;
        vector<int> a;
        FOR(i, l, m) a.pb(cmp[i]);
        cnt1++;
        bool ans=comp_query(a, b);
        if(ans)r=m;
        else l=m+1;
    }
    return l;
}

int h(int A, int B){
    vector<int> b;
    FOR(i, 1, 150) if(find(i)==B)b.pb(mpr[i]);
    vector<int> v;
    FOR(i, 1, 150) if(find(i)==A)v.pb(i);
    int l=0, r=v.size()-1;
    int m;
    while(l!=r){
        m=(l+r)/2;
        vector<int> a;
        FOR(i, l, m) a.pb(mpr[v[i]]);
        cnt2++;
        bool ans=query(a.size(), b.size(), &a[0], &b[0]);
        if(ans) r=m;
        else l=m+1;
    }
    return v[l];
}



void run(int N){
    //setup
    FOR(i, 1, 150) {par[i]=i;sz[i]=1;}
    FOR(i, 1, N) mpr[i]=i;
    
    std::random_device rd;
    std::mt19937 G(rd());
    
    //print(mpr);
    loop(_n, N-1){
        
        shuffle(mpr.begin()+1, mpr.begin()+N+1, G);

        //find components
        comps.clear(); cmp.clear();
        FOR(i, 1, N) comps.insert(find(i));
        for(auto e : comps) cmp.pb(e);
        int M = cmp.size();

        //query
        out=0;
        auto [l,r] = f(0, M-1);
        int m = (l+r)/2;

        int A = g(l, m, m+1, r);
        int B = g(m+1, r, A, A);

        //printf("Found comps %d %d\n", cmp[A], cmp[B]);

        int X = h(cmp[A], cmp[B]);
        int Y = h(cmp[B], cmp[A]);
        setRoad(mpr[X], mpr[Y]);
        un(X, Y);
    }
    //printf("cnt=%d | %d |%d\n", cnt, cnt1, cnt2);
}


/*
int main(){
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    
    int _N;
    cin >> _N;
    run(_N);
}*/

Subtask #1
0 / 7.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 29.0

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

Subtask #6
0 / 10.0

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