oj.uz

Submission #307069

# Submission time Handle Problem Language Result Execution time Memory
307069 2020-09-27T00:09:00 Z jungsnow ICC (CEOI16_icc) C++14
0 / 100
 1 ms 384 KB 
#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;

bool dfs(vector <int> all, bool has, bool is) {
    int tot = (int)all.size();
    if (tot < 2) return 0;
    vector <int> a, b, a1, a2, b1, b2;
    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() {
    vector <int> a;
    for (int i = 1; i <= n; ++i)
        if (d.anc(i) == i)
            a.push_back(i);
    dfs(a, 0, 1);
    if (d.child[c1].size() > 1 || d.child[c2].size() > 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 dfs(std::vector<int>, bool, bool)':
icc.cpp:110:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i = 0; i < a.size() / 2; ++i)
      |                     ~~^~~~~~~~~~~~~~
icc.cpp:112:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for (int i = a.size() / 2; i < a.size(); ++i)
      |                                ~~^~~~~~~~~~
icc.cpp:118:23: 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 = 0; i < b.size() / 2; ++i)
      |                     ~~^~~~~~~~~~~~~~
icc.cpp:120:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int i = b.size() / 2; i < b.size(); ++i)
      |                                ~~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Wrong road!
2 Halted 0 ms 0 KB -