Submission #543977

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
543977	2022-03-31T17:52:54 Z	Lobo	ICC (CEOI16_icc)	C++14	Compilation error	0 ms	0 KB

icc

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

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 110;

int edgset[maxn][maxn];
int qtddd;
void setRoad(int u, int v) {
    cout << u << " " << v << endl;

    if(--qtddd != 0) {
        int x,y; cin >> x >> y;
        edgset[x][y] = edgset[y][x] = 1;
    }
}

int query(int sza, int szb, int32_t a[], int32_t b[]) {
    int ans = 0;
    for(int i = 0; i < sza; i++) {
        for(int j = 0; j < szb; j++) {
            ans|= edgset[a[i]][b[j]];
        }
    }
    return ans;
}


int n, ds[maxn], col[maxn];
vector<int> vc[2][maxn];

int find(int v) {
    if(v == ds[v]) return v;
    return ds[v] = find(ds[v]);
}

void run(int32_t N) {
    srand(time(0));
    n = N;
    for(int i = 1; i <= n; i++) {
        ds[i] = i;
        vc[0][i].pb(i);
        col[i] = 0;
    }

    for(int qt = 0; qt < n-1; qt++) {
        set<pair<int,int>> par;
        for(int i = 1; i <= n; i++) {
            for(int j = i+1; j <= n; j++) {
                if(find(i) != find(j)) {
                    par.insert(mp(i,j));
                }
            }
        }

        while(par.size() > 1) {
            //coloca randons no primeiro
            vector<int> qr[2];
            for(int i = 1; i <= n; i++) {
                if(find(i) != i) continue;
                
                int colr = rand()%2;
                if(vc[colr][i].size() == 0) colr^= 1;
                for(auto x : vc[colr][i]) {
                    qr[rand()%2].pb(x);
                }
            }

            if(qr[0].size() == 0 || qr[1].size() == 0) continue;

            int32_t qra[(int32_t) qr[0].size()];
            for(int i = 0; i < qr[0].size(); i++) {
                qra[i] = qr[0][i];
            }
            int32_t qrb[(int32_t) qr[1].size()];
            for(int i = 0; i < qr[1].size(); i++) {
                qrb[i] = qr[1][i];
            }

            if(query((int32_t) qr[0].size(), (int32_t) qr[1].size(), qra, qrb)) {
                //é entre um e outro
                for(auto x : qr[0]) {
                    for(auto y : qr[0]) {
                        assert(!(find(x) == find(y) && col[x] != col[y]));
                        par.erase(mp(x,y));
                        par.erase(mp(y,x));
                    }
                }
                for(auto x : qr[1]) {
                    for(auto y : qr[1]) {
                        assert(!(find(x) == find(y) && col[x] != col[y]));
                        par.erase(mp(x,y));
                        par.erase(mp(y,x));
                    }
                }
            }
            else {
                for(auto x : qr[0]) {
                    for(auto y : qr[1]) {
                        assert(!(find(x) == find(y) && col[x] != col[y]));
                        par.erase(mp(x,y));
                        par.erase(mp(y,x));
                    }
                }
            }
        }

        assert(par.size() != 0);

        for(auto X : par) {
            int u = X.fr;
            int v = X.sc;
            int32_t qra[1]; qra[0] = u;
            int32_t qrb[1]; qrb[0] = v;

            // cout << qt << " " << u << " " << v << " ---- " << query(1,1,qra,qrb) << endl;

            if(query(1,1,qra,qrb)) {
                //coloca o v no u
                int pu = find(u);
                int pv = find(v);
                ds[pv] = pu;
                //os caras com col igual a col[v] ficam com col[u]^1
                int colv = col[v];
                for(auto x : vc[colv][pv]) {
                    vc[col[u]^1][pu].pb(x);
                    col[x] = col[u]^1;
                }
                for(auto x : vc[colv^1][pv]) {
                    vc[col[u]][pu].pb(x);
                    col[x] = col[u];
                }
                setRoad(u,v);
                break;
            }
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);
    srand(time(0));

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);

    int N; cin >> N;
    qtddd = N-1;
    int x,y; cin >> x >> y;
    edgset[x][y] = edgset[y][x] = 1;
    run(N);

    // int v = find(1);
    // for(auto x : vc[0][v]) {
    //     cout << x << " ";
    // }cout << endl;
    // for(auto x : vc[1][v]) {
    //     cout << x << " ";
    // }cout << endl;
}

Compilation message

icc.cpp: In function 'void run(int32_t)':
icc.cpp:83:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             for(int i = 0; i < qr[0].size(); i++) {
      |                            ~~^~~~~~~~~~~~~~
icc.cpp:87:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |             for(int i = 0; i < qr[1].size(); i++) {
      |                            ~~^~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccsdri4v.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccAG4mPw.o:icc.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccsdri4v.o: in function `main':
grader.cpp:(.text.startup+0x17): undefined reference to `run'
collect2: error: ld returned 1 exit status