Submission #128727

#	Time	Username	Problem	Language	Result	Execution time	Memory
128727		Nazik_number_one	ICC (CEOI16_icc)	C++14	10 / 100	192 ms	760 KiB

icc

#include "icc.h"

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

#ifdef __WIN32

int ansa, ansb, g[105][105], M;
pair < int, int > p[105];

void setRoad(int a, int b){
    cout <<a<<" "<<b<<endl;
    int x = p[M].first, y = p[M].second;
    M++;
    g[x][y] = g[y][x] = 1;
}

int query(int size_a, int size_b, int a[], int b[]){
    for (int i = 0; i < size_a; ++i){
        for (int j = 0; j < size_b; ++j){
            if (g[a[i]][b[j]])return 1;
        }
    }
    return 0;
}
#endif // __WIN32

int n, nm;
bool us[105];
vector < int > c[105], r[105];

void dfs(int x){
    us[x] = 1;
    c[nm].push_back(x);
    for (int i = 0; i < r[x].size(); ++i){
        if (!us[r[x][i]])dfs(r[x][i]);
    }
}

void run(int N){
    n = N;
    int a[105], b[105], sza, szb;
    for (int it = 1; it < n; ++it){
        for (int i = 0; i <= n; ++i)c[i].clear();
        nm = 0;
        memset(us, 0, sizeof(us));
        for (int i = 1; i <= n; ++i){
            if (!us[i]){
                dfs(i);
                nm++;
            }
        }
        int xx = 0, last = 0, lll = 0;
        for (int i = 0; ; ++i){
            sza = 0, szb = 0;
            for (int j = 0; j < nm; ++j){
                if (j & (1 << i)){
                    for (int e = 0; e < c[j].size(); ++e){
                        a[sza++] = c[j][e];
                    }
                }else {
                    for (int e = 0; e < c[j].size(); ++e){
                        b[szb++] = c[j][e];
                    }
                }
            }
            if (sza == 0 || szb == 0)break;
            if (query(sza, szb, a, b)){
                xx += (1 << i);
                last = i;
            }
        }
        //cout <<xx<<endl;
        int numa = 0, numb = (1 << last);
        //cout <<numa<<" "<<numb<<endl;
        for (int i = last - 1; i >= 0; --i){
            if (xx & (1 << i)){
                sza = szb = 0;
                for (int j = 0; j < nm; ++j){
                    if ((j & (1 << i)) && (j & (1 << last))){
                        for (int e = 0; e < c[j].size(); ++e){
                            a[sza++] = c[j][e];
                        }
                    }else if (!(j & (1 << i)) && !(j & (1 << last))){
                        for (int e = 0; e < c[j].size(); ++e){
                            b[szb++] = c[j][e];
                        }
                    }
                }
                if (sza == 0 || szb == 0 || !query(sza, szb, a, b))numa += (1 << i);else numb += (1 << i);
            }else {
                sza = szb = 0;
                for (int j = 0; j < nm; ++j){
                    if (!(j & (1 << i)) && (j & (1 << last))){
                        for (int e = 0; e < c[j].size(); ++e){
                            a[sza++] = c[j][e];
                        }
                    }else if (!(j & (1 << i)) && !(j & (1 << last))){
                        for (int e = 0; e < c[j].size(); ++e){
                            b[szb++] = c[j][e];
                        }
                    }
                }
                //cout <<sza<<" "<<szb<<endl;
                //for (int i = 0; i < sza; ++i)cout <<a[i]<<" ";cout <<endl;
                //for (int i = 0; i < szb; ++i)cout <<b[i]<<" ";cout <<endl;
                if (sza == 0 || szb == 0 || !query(sza, szb, a, b)){
                    numa += (1 << i);
                    numb += (1 << i);
                }
            }
        }
        //cout <<numa<<" "<<numb<<endl;
        sza = 0, szb = 0;
        for (int i = 0; i < c[numa].size(); ++i){
            a[sza++] = c[numa][i];
        }
        for (int i = 0; i < c[numb].size(); ++i){
            b[szb++] = c[numb][i];
        }
        int l = 0, r = sza - 1;
        while (l < r){
            int mid = (l + r) / 2;
            if (query(mid + 1, szb, a, b))r = mid;else l = mid + 1;
        }
        int ll = l;
        int aa = a[ll];
        l = 0, r = szb - 1;
        while (l < r){
            int mid = (l + r) / 2;
            if (query(ll + 1, mid + 1, a, b))r = mid;else l = mid + 1;
        }
        int rr = l;
        int bb = b[rr];
        setRoad(aa, bb);
        ::r[aa].push_back(bb);
        ::r[bb].push_back(aa);
    }
}

#ifdef __WIN32

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin >>n;
    for (int i = 1; i < n; ++i)cin >>p[i].first>>p[i].second;
    M = 2;
    int x = p[1].first, y = p[1].second;
    g[x][y] = g[y][x] = 1;
    run(n);
}

#endif // __WIN32

/*

4
2 4
1 3
4 1

*/

Compilation message (stderr)

icc.cpp: In function 'void dfs(int)':
icc.cpp:35:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < r[x].size(); ++i){
                     ~~^~~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:58:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int e = 0; e < c[j].size(); ++e){
                                     ~~^~~~~~~~~~~~~
icc.cpp:62:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int e = 0; e < c[j].size(); ++e){
                                     ~~^~~~~~~~~~~~~
icc.cpp:81:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for (int e = 0; e < c[j].size(); ++e){
                                         ~~^~~~~~~~~~~~~
icc.cpp:85:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for (int e = 0; e < c[j].size(); ++e){
                                         ~~^~~~~~~~~~~~~
icc.cpp:95:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for (int e = 0; e < c[j].size(); ++e){
                                         ~~^~~~~~~~~~~~~
icc.cpp:99:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for (int e = 0; e < c[j].size(); ++e){
                                         ~~^~~~~~~~~~~~~
icc.cpp:115:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < c[numa].size(); ++i){
                         ~~^~~~~~~~~~~~~~~~
icc.cpp:118:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < c[numb].size(); ++i){
                         ~~^~~~~~~~~~~~~~~~
icc.cpp:53:31: warning: unused variable 'lll' [-Wunused-variable]
         int xx = 0, last = 0, lll = 0;
                               ^~~

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