Submission #605858

#	Time	Username	Problem	Language	Result	Execution time	Memory
605858		Je_O	ICC (CEOI16_icc)	C++17	100 / 100	145 ms	628 KiB

icc

#include "icc.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int N = 105;
int par[N];
vector<int> cc[N];

int find(int x){
    if(par[x] == x)return x;
    return par[x] = find(par[x]);
}

void merge(int x, int y){
    x = find(x); y = find(y);
    if(x == y)return;
    if(cc[x].size() > cc[y].size())swap(x, y);
    par[x] = y;
    for(int i = 0; i < cc[x].size(); ++i){
        cc[y].pb(cc[x][i]);
    }
    return;
}

vector<int> lst[N][2];

void build(int idx, int l, int r, int p){
    if(l == r){
        lst[idx][p].pb(l);
        return;
    }
    if(idx > 1)for(int i = l; i <= r; ++i)lst[idx][p].pb(i);
    int m = (l + r)/2;
    build(idx + 1, l, m, 0);
    build(idx + 1, m + 1, r, 1);
    return;
}

vector<int> va, vb;

void add(int idx, int p){
    if(p == 0){
        for(int i = 0; i < cc[idx].size(); ++i){
            va.pb(cc[idx][i]);
        }
    }else{
        for(int i = 0; i < cc[idx].size(); ++i){
            vb.pb(cc[idx][i]);
        }
    }
    return;
}

int ask(int sz_a, int sz_b, vector<int> v_a, vector<int> v_b){
    int ar_a[sz_a];
    int ar_b[sz_b];
    for(int i = 0; i < sz_a; ++i)ar_a[i] = v_a[i];
    for(int i = 0; i < sz_b; ++i)ar_b[i] = v_b[i];
    return query(sz_a, sz_b, ar_a, ar_b);
}

// bool path[N][N];
// int curid = 0;
// int uu[N], vv[N];

// int query(int sz_a, int sz_b, vector<int> v_a, vector<int> v_b){

//     cout << v_a[0] << ' ' << v_b[0] << endl;
//     for(int i = 0; i < sz_a; ++i){
//         for(int j = 0; j < sz_b; ++j){
//             if(path[v_a[i]][v_b[j]])return 1;
//         }
//     }
//     return 0;
// }

// void setRoad(int a, int b){
//     if((uu[curid] == a && vv[curid] == b) || (uu[curid] == b && vv[curid] == a)){
//         cout << curid << ' ' << "true" << endl;
//     }else{
//         cout << a << ' ' << b << '\n';
//     }
//     return;
// }

void run(int n){
    for(int i = 1; i <= n; ++i)par[i] = i;
    for(int i = 1; i <= n; ++i)cc[i].pb(i);
    for(int q = 1; q < n; ++q){
        // path[uu[q]][vv[q]] = true;
        // path[vv[q]][uu[q]] = true;
        // ++curid;
        vector<int> v;
        for(int i = 1; i <= n; ++i){
            if(find(i) == i)v.pb(i);
        }
        for(int i = 1; i <= n; ++i){
            lst[i][0].clear(); lst[i][1].clear();
        }
        va.clear(); vb.clear();
        build(1, 0, v.size() - 1, 0);
        for(int i = 1; i <= n; ++i){
            va.clear(); vb.clear();
            for(int j = 0; j < lst[i][0].size(); ++j){
                add(v[lst[i][0][j]], 0);
            }
            for(int j = 0; j < lst[i][1].size(); ++j){
                add(v[lst[i][1][j]], 1);
            }
            int get = 0;
            if(va.size() > 0 && vb.size() > 0)get = ask(va.size(), vb.size(), va, vb);
            if(get == 1)break;
        }
        // cout << q << " -> ";
        // for(int i = 0; i < va.size(); ++i)cout << va[i] << ' ';
        // cout << endl;
        // for(int i = 0; i < vb.size(); ++i)cout << vb[i] << ' ';
        // cout << endl;
        int l = 0, r = va.size() - 1;
        while(l < r){
            int m = (l + r)/2;
            vector<int> cur_va;
            for(int i = 0; i <= m; ++i){
                cur_va.pb(va[i]);
            }
            int get = 0;
            if(cur_va.size() > 0 && vb.size() > 0)get = ask(cur_va.size(), vb.size(), cur_va, vb);
            if(get == 1){
                r = m;
            }else{
                l = m + 1;
            }
        }
        int ans_1 = va[l];
        l = 0; r = vb.size() - 1;
        while(l < r){
            int m = (l + r)/2;
            vector<int> cur_vb;
            for(int i = 0; i <= m; ++i){
                cur_vb.pb(vb[i]);
            }
            int get = 0;
            if(va.size() > 0 && cur_vb.size() > 0)get = ask(va.size(), cur_vb.size(), va, cur_vb);
            if(get == 1){
                r = m;
            }else{
                l = m + 1;
            }
        }
        int ans_2 = vb[l];
        setRoad(ans_1, ans_2);
        merge(ans_1, ans_2);
    }
    return;
}

// int main(){
//     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//     int n; cin >> n;
//     for(int i = 1; i < n; ++i){
//         cin >> uu[i] >> vv[i];
//     }
//     run(n);
//     return 0;
// }

Compilation message (stderr)

icc.cpp: In function 'void merge(int, int)':
icc.cpp:25:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i = 0; i < cc[x].size(); ++i){
      |                    ~~^~~~~~~~~~~~~~
icc.cpp: In function 'void add(int, int)':
icc.cpp:49:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int i = 0; i < cc[idx].size(); ++i){
      |                        ~~^~~~~~~~~~~~~~~~
icc.cpp:53:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int i = 0; i < cc[idx].size(); ++i){
      |                        ~~^~~~~~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:110:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |             for(int j = 0; j < lst[i][0].size(); ++j){
      |                            ~~^~~~~~~~~~~~~~~~~~
icc.cpp:113:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             for(int j = 0; j < lst[i][1].size(); ++j){
      |                            ~~^~~~~~~~~~~~~~~~~~

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