Submission #307063

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
307063	2020-09-26T22:31:04 Z	jungsnow	ICC (CEOI16_icc)	C++14	Compilation error	0 ms	0 KB

icc

#include<bits/stdc++.h>
#include "icc.h"
#define x first
#define y second

using namespace std;

const int N = 101;

typedef pair <int, int> ii;

struct dsu {
    int n, p[N], s[N], C;
    vector <int> child[N];

    dsu() {};

    void init(int _n) {
        n = _n;
        C = n;
        for (int i = 1; i <= n; ++i) {
            p[i] = i;
            s[i] = 1;
            child[i].push_back(i);
        }
    }

    int anc(int u) {
        return (p[u] == u ? u : p[u] = anc(p[u]));
    }

    void merge(int u, int v) {
        u = anc(u); v = anc(v);
        if (u == v) return;
        if (s[u] < s[v]) swap(u, v);
        p[v] = u;
        for (int x : child[v])
            child[u].push_back(x);
        child[v].clear();
        s[u] += s[v];
        --C;
        return;
    }
} d;

//int p[N], q[N];

//bool query(int n, int m, int a[], int b[]) {
//    bool ok;
//    cout<<"ask\n";
//    cout<<"a ";
//    for (int i = 0; i < n; ++i)
//        cout<<a[i]<<' ';
//    cout<<endl;
//    cout<<"b ";
//    for (int i = 0; i < m; ++i)
//        cout<<b[i]<< ' ';
//    cout<<endl;
//    cin >> ok;
//    return ok;
//}

bool ask(vector <int> C, vector <int> D, bool is) {
    vector <int> a, b;
    if (!is)
        a = C; b = D;
    else {
        for (int u : C) for (int x : d.child[u]) a.push_back(x);
        for (int u : D) for (int x : d.child[u]) b.push_back(x);
    }
    int sza = (int)a.size(), szb = (int)b.size();
    int p[sza], q[szb];
    for (int i = 0; i < sza; ++i)
        p[i] = a[i];
    for (int i = 0; i < szb; ++i)
        q[i] = b[i];
    return query(sza, szb, p, q);
}

vector <int> join(vector <int>& a, vector <int>& b) {
    vector <int> c;
    for (int u : a) c.push_back(u);
    for (int v : b) c.push_back(v);
    return c;
}

int c1, c2, u, v, n;
vector <int> a, b, a1, a2, b1, b2;

bool dfs(vector <int> all, bool has, bool is) {
    int tot = (int)all.size();
    if (tot < 2) return 0;
    a.clear();
    b.clear();
    a1.clear();
    a2.clear();
    b1.clear();
    b2.clear();
    bool ok = has;
    for (int i = 0; i < tot / 2; ++i)
        a.push_back(all[i]);
    for (int i = tot / 2; i < tot; ++i)
        b.push_back(all[i]);
    if (!ok)
        ok = ask(a, b, is);
    if (!ok) {
        if (dfs(a, 0, is)) return 1;
        if (dfs(b, 0, is)) return 1;
        return 0;
    }
    if (tot == 2) {
        c1 = a[0];
        c2 = b[0];
        return 1;
    }
    for (int i = 0; i < a.size() / 2; ++i)
        a1.push_back(a[i]);
    for (int i = a.size() / 2; i < a.size(); ++i)
        a2.push_back(a[i]);
    if (a.size() == 1) {
        a1 = a;
        a2 = a;
    }
    for (int i = 0; i < b.size() / 2; ++i)
        b1.push_back(b[i]);
    for (int i = b.size() / 2; i < b.size(); ++i)
        b2.push_back(b[i]);
    if (b.size() == 1) {
        b1 = b;
        b2 = b;
    }

    ok = ask(a1, b1, is);
    if (ok) return dfs(join(a1, b1), 1, is);

    ok = ask(a2, b2, is);
    if (ok) return dfs(join(a2, b2), 1, is);

    ok = ask(a1, b2, is);
    if (ok) return dfs(join(a1, b2), 1, is);

    return dfs(join(a2, b1), 1, is);
}

//void setRoad(int u, int v) {
//    cout<<"is "<<u<<' '<<v<<endl<<endl;
//}

void proc() {
    a.clear();
    for (int i = 1; i <= n; ++i)
        if (d.anc(i) == i)
            a.push_back(i);
    dfs(a, 0, 1);
    dfs(join(d.child[c1], d.child[c2]), 1, 0);
    setRoad(c1, c2);
    d.merge(c1, c2);
    return;
}

void run(int n) {
    d.init(n);
    for (int i = 1; i < n; ++i)
        proc();
}

//int main() {
//    cin >> n;
//    run(n);
//}

Compilation message

icc.cpp: In function 'bool ask(std::vector<int>, std::vector<int>, bool)':
icc.cpp:65:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   65 |     if (!is)
      |     ^~
icc.cpp:66:16: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   66 |         a = C; b = D;
      |                ^
icc.cpp:67:5: error: 'else' without a previous 'if'
   67 |     else {
      |     ^~~~
icc.cpp: In function 'bool dfs(std::vector<int>, bool, bool)':
icc.cpp:116:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for (int i = 0; i < a.size() / 2; ++i)
      |                     ~~^~~~~~~~~~~~~~
icc.cpp:118:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     for (int i = a.size() / 2; i < a.size(); ++i)
      |                                ~~^~~~~~~~~~
icc.cpp:124:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for (int i = 0; i < b.size() / 2; ++i)
      |                     ~~^~~~~~~~~~~~~~
icc.cpp:126:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     for (int i = b.size() / 2; i < b.size(); ++i)
      |                                ~~^~~~~~~~~~