oj.uz

Submission #604813

# Submission time Handle Problem Language Result Execution time Memory
604813 2022-07-25T10:05:34 Z MadokaMagicaFan ICC (CEOI16_icc) C++14
100 / 100
 147 ms 636 KB 
#include "bits/stdc++.h"
#ifndef ONPC
#include "icc.h"
#endif

using namespace std;

using ll = long long;
using vi = vector<int>;
using pi = pair<int, int>;

#define forn(i,n)       for(int i = 0; i < n; ++i)
#define forr(i,n)       for(int i = n-1; i >= 0; --i)
#define forbe(i,b,e)    for(int i = b; i < e; ++i)

#define all(v)          (v).begin(),(v).end()
#define sort(v)         sort(all(v))
#define sz(v)           ((int)(v).size())

#define endl            '\n'
#define pb              push_back
#define f               first
#define s               second
//#define ONPC

const int N = 100;
int p[N];
int n;

#ifdef ONPC
int query(int size_a, int size_b, int *a, int *b);
void setRoad(int a, int b);
#endif

int getp(int x) { return p[x] = (x == p[x]) ? x : getp(p[x]); }

int uni(int a, int b) { a = getp(a); b = getp(b); p[a] = b; return(a != b); }

int
ask(bool par, vi va, vi vb)
{
    forn(i, sz(va)) {
        if (getp(va[i]) == va[i] && par) {
            forn(j, n) {
                if (va[i] == j) continue;
                if (getp(j) == va[i]) va.pb(j);
            }
        }
    }

    forn(i, sz(vb)) {
        if (getp(vb[i]) == vb[i] && par) {
            forn(j, n) {
                if (vb[i] == j) continue;
                if (getp(j) == vb[i]) vb.pb(j);
//                if (getp(j) == vb[i]) cout << "SPL " << j << endl;
            }
        }
    }


    int sa, sb;
    sa = sz(va);
    sb = sz(vb);
    int a[N];
    int b[N];

    forn(i, sz(va)) a[i] = va[i] + 1;
    forn(i, sz(vb)) b[i] = vb[i] + 1;

    return query(sa, sb, a, b);
}

vi conc(vi a, vi b) {
    if (sz(a) < sz(b)) swap(a,b);
    vi c = a;
    for(int x : b) c.pb(x);
    return c;
}

struct tr
{
    vi vl;
    vi vr;
    vi a;

    int n;

    tr(vi& _a) {
        a = _a;
        n = sz(a);

        vl.resize(4*n, -1); 
        vr.resize(4*n, -1); 
        
        build(1, 0, n-1);
    }

    void build(int i, int l, int r) {
//        cout << i << ' ' << l << ' ' << r << endl;
        int mid = (l+r)>>1;
        vl[i] = l;
        vr[i] = r;

        if (l == r) return;

        build(i<<1, l, mid);
        build(i<<1|1, mid+1, r);
    }

    vi get(int i) {
        if (vl[i] == vr[i]) return {a[vl[i]]};

        return conc(get(i<<1) , get(i<<1|1));
    }

    pi getc(int i) {
        if (vl[i<<1] == -1 || vl[i<<1|1] == -1) return {-1,-1};

        return {i<<1, i<<1|1};
    }
};

void
run (int _n)
{
    n = _n;
    forn(i, n) p[i] = i;

    forn(j, n-1) {
        vi vals;
        vi par, oldpar;
        vi ka, kb;


        forn(i, n) if (i == getp(i)) vals.pb(i);
        tr x(vals);
        par.pb(1);

//        cout << "SZ: " << sz(vals) << endl;

        ka = x.get(2);
        kb = x.get(3);

//        cout << sz(ka) << ' ' << sz(kb) << endl;

        int k = ask(1, ka, kb);

        while (!k) {
            oldpar = par;
            par.clear();

            ka.clear();
            kb.clear();

//            cout << "OLDPAR: ";
            for(int i : oldpar) {
//                cout << i << ' ';
                if (x.getc(i<<1).f != -1) par.pb(i<<1);
                if (x.getc(i<<1|1).f != -1) par.pb(i<<1|1);
            }
//            cout << endl;

//            cout << "Par: ";
            assert(sz(par));
            for(int i : par) {
//                cout << i << ' ';
                // TODO optimize
                ka = conc(ka,x.get(i<<1));
                kb = conc(kb,x.get(i<<1|1));
            }
//            cout << endl;
            
            k = ask(1, ka, kb);
        }

//        cout << "Stuff" << endl;

        vi ta, tb;
        forn(i, sz(ka)) {
            if (getp(ka[i]) == ka[i]) {
                forn(j, n) {
                    if (ka[i] == j) continue;
                    if (getp(j) == ka[i]) ka.pb(j);
                }
            }
        }

        forn(i, sz(kb)) {
            if (getp(kb[i]) == kb[i]) {
                forn(j, n) {
                    if (kb[i] == j) continue;
                    if (getp(j) == kb[i]) kb.pb(j);
                }
            }
        }

        ta = ka;
        tb = kb;

        int l = 0;
        int r = sz(tb);

        while(l < r-1) {
            kb.clear();
            int mid = (l+r)>>1;

            forbe(i, l, mid) kb.pb(tb[i]);

            if (ask(0,ka,kb)) r = mid;
            else l = mid;
        }

        int n1, n2;
        n1 = tb[l];

        kb = {n1};
        l = 0;
        r = sz(ka);

        while(l < r-1) {
            ka.clear();
            int mid = (l+r)>>1;

            forbe(i, l, mid) ka.pb(ta[i]);

            if (ask(0,ka,kb)) r = mid;
            else l = mid;
        }

        n2 = ta[l];

//        cout << n1+1 << ' ' << n2+1 << endl;

        setRoad(n1+1, n2+1);
        uni(n1,n2);
    }

//    cout << n << endl;
}


#ifdef ONPC
int rp[N];
pi rd[N];
int cnt = 1;

set<pi> edgs;

int rgtp(int x) {return rp[x] = (rp[x] == x) ? x : rp[x]; }

void
setRoad(int a, int b)
{
    if (a > b) swap(a,b);

    if (a == rd[cnt-1].f +1 && b == rd[cnt-1].s+1) {
        cout << "OK\n";
    } else {
        cout << "NO\n";
        exit(1);
    }
    if (cnt < n-1) {
        edgs.insert(rd[cnt]);
//        p[rgtp(rd[cnt].f)] = rd[cnt].s;
        ++cnt;
    }
}

int 
query(int size_a, int size_b, int *a, int *b)
{
//    cout << "1: ";
//    forn(i, size_a) cout << a[i] << ' ';
//    cout << endl;
//    cout << "2: ";
//    forn(i, size_b) cout << b[i] << ' ';
//    cout << endl;

    forn(i, size_a) --a[i];
    forn(i, size_b) --b[i];


//    cout << 'T' << endl;
    forn(i, size_a) assert(a[i]+1 <= n);
    forn(i, size_b) assert(b[i]+1 <= n);
    forn(i, size_a) assert(a[i]+1 > 0);
    forn(i, size_b) assert(b[i]+1 > 0);
    forn(i, size_a)
        forn(j, size_b)
            assert(a[i] != b[j]);
    forn(i, size_a) {
        forn(j, size_b) {
            if (edgs.count({a[i], b[j]}) || edgs.count({b[j], a[i]}))
            return 1;
        }
    }

//    cout << 'F' << endl;
//    int x;
//    cin >> x;
    return 0;
}
void
solve() {
    int n;
    cin >> n;
    forn(i,n) rp[i] = i;
    forn(i, n-1) cin >> rd[i].f >> rd[i].s;
    forn(i, n-1) --rd[i].f, --rd[i].s;
    forn(i, n-1) if (rd[i].f > rd[i].s) swap(rd[i].f, rd[i].s);
    
    edgs.insert(rd[0]);
    rp[rd[0].f] = rd[0].s;

    run(n);
}

int32_t
main(int argc, char** argv) {
    if (argc > 1)
        freopen(argv[1],"r", stdin);
    solve();
}
#endif

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Ok! 98 queries used.
2 Correct 5 ms 468 KB Ok! 102 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 528 KB Ok! 546 queries used.
2 Correct 41 ms 468 KB Ok! 629 queries used.
3 Correct 42 ms 508 KB Ok! 666 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 496 KB Ok! 1499 queries used.
2 Correct 135 ms 560 KB Ok! 1419 queries used.
3 Correct 139 ms 536 KB Ok! 1612 queries used.
4 Correct 126 ms 500 KB Ok! 1555 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 636 KB Ok! 1585 queries used.
2 Correct 137 ms 560 KB Ok! 1596 queries used.
3 Correct 137 ms 556 KB Ok! 1618 queries used.
4 Correct 127 ms 520 KB Ok! 1546 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 496 KB Ok! 1630 queries used.
2 Correct 120 ms 500 KB Ok! 1618 queries used.
3 Correct 147 ms 560 KB Ok! 1600 queries used.
4 Correct 131 ms 512 KB Ok! 1607 queries used.
5 Correct 113 ms 512 KB Ok! 1528 queries used.
6 Correct 119 ms 468 KB Ok! 1568 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 512 KB Ok! 1618 queries used.
2 Correct 119 ms 504 KB Ok! 1618 queries used.