Submission #131188

#	Time	Username	Problem	Language	Result	Execution time	Memory
131188		zubec	ICC (CEOI16_icc)	C++14	11 / 100	175 ms	888 KiB

icc

#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

#ifdef __WIN32

int gg[110][110], ptr;
pair < int, int > edg[110];

void setRoad(int a, int b){
    ++ptr;
    cout << a << ' ' << b << endl;
    int x = edg[ptr].first, y = edg[ptr].second;
    gg[x][y] = gg[y][x] = 1;
}

int query(int a, int b, int *A, int *B){
    for (int i = 0; i < a; ++i){
        for (int j = 0; j < b; ++j){
            if (gg[A[i]][B[j]])return 1;
        }
    }
    return 0;
}

#endif // __WIN32


int n;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int sz1, sz2, A[110], B[110];

int my_query(vector<int> &vec1, vector <int> &vec2){
    sz1 = sz2 = 0;
    for (int i = 0; i < vec1.size(); i++)
        A[sz1++] = vec1[i];
    for (int i = 0; i < vec2.size(); i++)
        B[sz2++] = vec2[i];
    return query(sz1, sz2, A, B);
}

int dsu[110];

int dsu_get(int v){
    if (v == dsu[v])
        return v;
    return dsu[v] = dsu_get(dsu[v]);
}

void dsu_unite(int a, int b){
    a = dsu_get(a);
    b = dsu_get(b);
    dsu[b] = a;
}

vector <int> g[110];

void run(int N){
    n = N;
    for (int i = 1; i <= n; i++){
        dsu[i] = i;
    }
    for (int tt = 1; tt < n; tt++){
        vector <int> vec;
        for (int i = 1; i <= n; i++)
            g[i].clear();
        for (int i = 1; i <= n; i++){
            vec.push_back(dsu_get(i));
            g[dsu_get(i)].push_back(i);
        }
        sort(vec.begin(), vec.end());
        vec.erase(unique(vec.begin(), vec.end()), vec.end());
        while(1){
            int mask = 0;
            int lst = 0;
            int sz = 0;
            for (int bt = 0; ; bt++){
                vector <int> vec1, vec2;
                for (int j = 0; j < vec.size(); j++){
                    if (vec[j] & (1<<bt)){
                        for (int l = 0; l < g[vec[j]].size(); l++)
                            vec1.push_back(g[vec[j]][l]);
                    } else {
                        for (int l = 0; l < g[vec[j]].size(); l++)
                            vec2.push_back(g[vec[j]][l]);
                    }
                }
                if (vec1.empty() || vec2.empty())
                    break;
                sz = bt;
                /*cout << "kek " << bt << endl;
                for (int j = 0; j < vec1.size(); j++)
                    cout << vec1[j] << ' ';
                cout << endl;
                for (int j = 0; j < vec2.size(); j++)
                    cout << vec2[j] << ' ';
                cout << endl;*/
                if (my_query(vec1, vec2)){
                    mask |= (1<<bt);
                    lst = bt;
                }
            }
            int mask1 = 0, mask2 = (1<<lst);
            for (int bt = sz; bt >= 0; bt--){
                if (bt == lst)
                    continue;
                if (mask & (1<<bt)){
                    vector <int> vec1, vec2;
                    for (int j = 0; j < vec.size(); j++){
                        if ((vec[j] & (1<<bt)) && (vec[j] & (1<<lst))){
                            for (int l = 0; l < g[vec[j]].size(); l++)
                                vec1.push_back(g[vec[j]][l]);
                        } else
                        if (!(vec[j] & (1<<bt)) && !(vec[j] & (1<<lst))){
                            for (int l = 0; l < g[vec[j]].size(); l++)
                                vec2.push_back(g[vec[j]][l]);
                        }
                    }
                    if (vec1.empty() || vec2.empty() || !my_query(vec1, vec2))
                        mask1 |= (1<<bt); else
                        mask2 |= (1<<bt);
                } else {
                    vector <int> vec1, vec2;
                    for (int j = 0; j < vec.size(); j++){
                        if (!(vec[j] & (1<<bt)) && (vec[j] & (1<<lst))){
                            for (int l = 0; l < g[vec[j]].size(); l++)
                                vec1.push_back(g[vec[j]][l]);
                        } else
                        if (!(vec[j] & (1<<bt)) && !(vec[j] & (1<<lst))){
                            for (int l = 0; l < g[vec[j]].size(); l++)
                                vec2.push_back(g[vec[j]][l]);
                        }
                    }
                    if (vec1.empty() || vec2.empty() || !my_query(vec1, vec2)){
                        mask1 |= (1<<bt);
                        mask2 |= (1<<bt);
                    }
                }
            }
            vector <int> vec1 = g[mask1], vec2 = g[mask2];
            /*cout << mask1 << ' ' << mask2 << ' ' << mask << endl;
            cout << "kek " << vec1.size() << ' ' << vec2.size() << endl;
            for (int j = 0; j < vec1.size(); j++)
                cout << vec1[j] << ' ';
            cout << endl;
            for (int j = 0; j < vec2.size(); j++)
                cout << vec2[j] << ' ';
            cout << endl;*/

            int l = 0, r = vec1.size()-1;
            while(l < r){
                int mid = (l+r)>>1;
                vector <int> cur;
                for (int j = l; j <= mid; j++)
                    cur.push_back(vec1[j]);
                if (my_query(cur, vec2))
                    r = mid; else
                    l = mid+1;
            }
            int a = vec1[l];
            l = 0, r = vec2.size();
            while(l < r){
                int mid = (l+r)>>1;
                vector <int> cur;
                for (int j = l; j <= mid; j++)
                    cur.push_back(vec2[j]);
                if (my_query(vec1, cur))
                    r = mid; else
                    l = mid+1;
            }
            int b = vec2[l];
            setRoad(a, b);
            dsu_unite(a, b);
            break;
        }
    }
}

#ifdef __WIN32

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++){
        cin >> edg[i].first >> edg[i].second;
    }
    gg[edg[1].first][edg[1].second] = gg[edg[1].second][edg[1].first] = 1;
    ptr = 1;
    run(n);
}

#endif // __WIN32

/**

4
2 4
1 3
1 4

*/

Compilation message (stderr)

icc.cpp: In function 'int my_query(std::vector<int>&, std::vector<int>&)':
icc.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec1.size(); i++)
                     ~~^~~~~~~~~~~~~
icc.cpp:39:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec2.size(); i++)
                     ~~^~~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:81:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int j = 0; j < vec.size(); j++){
                                 ~~^~~~~~~~~~~~
icc.cpp:83:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for (int l = 0; l < g[vec[j]].size(); l++)
                                         ~~^~~~~~~~~~~~~~~~~~
icc.cpp:86:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for (int l = 0; l < g[vec[j]].size(); l++)
                                         ~~^~~~~~~~~~~~~~~~~~
icc.cpp:111:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int j = 0; j < vec.size(); j++){
                                     ~~^~~~~~~~~~~~
icc.cpp:113:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                             for (int l = 0; l < g[vec[j]].size(); l++)
                                             ~~^~~~~~~~~~~~~~~~~~
icc.cpp:117:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                             for (int l = 0; l < g[vec[j]].size(); l++)
                                             ~~^~~~~~~~~~~~~~~~~~
icc.cpp:126:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int j = 0; j < vec.size(); j++){
                                     ~~^~~~~~~~~~~~
icc.cpp:128:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                             for (int l = 0; l < g[vec[j]].size(); l++)
                                             ~~^~~~~~~~~~~~~~~~~~
icc.cpp:132:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                             for (int l = 0; l < g[vec[j]].size(); l++)
                                             ~~^~~~~~~~~~~~~~~~~~

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