답안 #128987

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
128987 2019-07-11T11:52:29 Z I_Hate_AHDPIYKO CEOI16_icc (CEOI16_icc) C++17
100 / 100
146 ms 804 KB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define lll __int128
#define ull unsigned long long
#define fi first
#define se second
#define db double
#define ld long double
#define lld __float128

/// order_of_key, find_by_order

template<class T, class COMP>
using custom_set = tree<T, null_type, COMP, rb_tree_tag, tree_order_statistics_node_update>;

template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<class T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<class T, class U>
using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd_64(chrono::steady_clock::now().time_since_epoch().count());

#include "icc.h"

//int query(int size_a, int size_b, int a[], int b[])
//{
//    for(int i = 0; i < size_a; i++)
//    {
//        cout << a[i] << ' ';
//    } cout << '\n';
//    for(int i = 0; i < size_b; i++)
//    {
//        cout << b[i] << ' ';
//    } cout << '\n';
//    int res; cin >> res; return res;
//}
//
//void setRoad(int a, int b)
//{
//    cout << a << " - " << b << '\n';
//}


int qrr(set<int> a, set<int> b)
{
    int n = a.size(), m = b.size();
    int A[n], B[m], i = 0;
    for(auto j : a)
    {
        A[i++] = j+1;
    }
    i = 0;
    for(auto j : b)
    {
        B[i++] = j+1;
    }
    if(!n || !m)
        return 0;
    return query(n, m, A, B);
}


const int MAXN = 1005;

int pr[MAXN], sz[MAXN], cur;

vector<int> lc[MAXN], rc[MAXN], ind[MAXN];
vector<pair<int, int> > dat;

void solve(int l, int r, int d)
{
    if(l > r)
        return;
    int m = (l+r) / 2;

    ind[d].push_back(cur);
    lc[cur].clear();
    rc[cur].clear();
    int m1 = m, m2 = m;
    while(m2 < r && dat[m2+1].fi == dat[m].fi) m2++;
    while(m1 >= l && dat[m1].fi == dat[m+1].fi) m1--;
    if(m1+1 == l && m2 == r)
    {
        cur++;
        return;
    }
    if(m1+1 != l)
        m = m1;
    else
        m = m2;

    for(int i = l; i <= m; i++)
    {
        lc[cur].push_back(dat[i].se);
    }
    for(int i = m+1; i <= r; i++)
    {
        rc[cur].push_back(dat[i].se);
    }
    cur++;
    if(l == r)
        return;
    solve(l, m, d+1);
    solve(m+1, r, d+1);
}

int lead(int v)
{
    if(v == pr[v])
        return v;
    return pr[v] = lead(pr[v]);
}

bool comb(int a, int b)
{
    a = lead(a);
    b = lead(b);
    if(a == b)
        return 0;
    if(sz[a] > sz[b])
        swap(a, b);
    sz[b] += sz[a];
    pr[a] = b;
    return 1;
}



void run(int n)
{
    for(int i = 0; i < n; i++)
    {
        pr[i] = i;
        sz[i] = 1;
    }
    for(int i = 0; i < n-1; i++)
    {
        for(int j = 0; j < n; j++)
        {
            dat.push_back({lead(j), j});
            ind[j].clear();
        }
        sort(dat.begin(), dat.end());
//        for(int j = 0; j < n; j++)
//        {
//            cout << dat[j].se+1 << ' ';
//        } cout << '\n';
        cur = 0;
        solve(0, n-1, 0);
        dat.clear();
        bool bb = 0;
        for(int j = 0; j < n; j++)
        {
//            cout << "J" << ": " << j << '\n';
            set<int> a, b, ca;
            for(auto v : ind[j])
            {
                for(auto kk : lc[v])
                {
                    a.insert(kk);
                    ca.insert(lead(kk));
                }
                for(auto kk : rc[v])
                {
                    if(ca.count(lead(kk)))
                        a.insert(kk);
                    else
                        b.insert(kk);
                }
            }
            if(!qrr(a, b))
                continue;
            int l = 0, r = ind[j].size()-1;
            while(l != r)
            {
                int m = (l+r) / 2;
                a.clear(); b.clear(); ca.clear();
                for(int v = l; v <= m; v++)
                {
                    for(auto k : lc[ind[j][v]])
                    {
                        a.insert(k);
                        ca.insert(lead(k));
                    }
                    for(auto k : rc[ind[j][v]])
                    {
                        if(ca.count(lead(k)))
                            a.insert(k);
                        else
                            b.insert(k);
                    }
                }
                if(qrr(a, b))
                    r = m;
                else
                    l = m+1;
            }
            vector<int> le, re;
            a.clear(); b.clear(); ca.clear();
            int kek = ind[j][l];
            for(auto v : lc[kek])
            {
                le.push_back(v); ca.insert(lead(v));
            }
            for(auto v : rc[kek])
            {
                if(ca.count(lead(v)))
                    le.push_back(v);
                else
                    re.push_back(v);
            }
            l = 0; r = le.size()-1;
            while(l != r)
            {
                int m = (l+r) / 2;
                a.clear(); b.clear(); ca.clear();
                for(int v = l; v <= m; v++)
                {
                    a.insert(le[v]);
                }
                for(auto v : re)
                {
                    b.insert(v);
                }
                if(qrr(a, b))
                    r = m;
                else
                    l = m+1;
            }
            int L = l;
            l = 0; r = re.size()-1;
            while(l != r)
            {
                int m = (l+r) / 2;
                a.clear(); b.clear(); ca.clear();
                for(int v = l; v <= m; v++)
                {
                    b.insert(re[v]);
                }
                for(auto v : le)
                {
                    a.insert(v);
                }
                if(qrr(a, b))
                    r = m;
                else
                    l = m+1;
            }
            int R = r;
            setRoad(le[L]+1, re[R]+1);
            comb(le[L], re[R]);
            bb = 1;
            break;
        }
    }
}
//
//int main()
//{
//    int n; cin >> n;
//    run(n);
//}






































/// shche ne vmerla Ykraina

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:162:14: warning: variable 'bb' set but not used [-Wunused-but-set-variable]
         bool bb = 0;
              ^~
# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 632 KB Ok! 98 queries used.
2 Correct 9 ms 760 KB Ok! 94 queries used.
# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 632 KB Ok! 503 queries used.
2 Correct 42 ms 632 KB Ok! 497 queries used.
3 Correct 42 ms 636 KB Ok! 493 queries used.
# 결과 실행 시간 메모리 Grader output
1 Correct 130 ms 804 KB Ok! 1239 queries used.
2 Correct 140 ms 632 KB Ok! 1232 queries used.
3 Correct 122 ms 704 KB Ok! 1164 queries used.
4 Correct 132 ms 636 KB Ok! 1217 queries used.
# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 712 KB Ok! 1147 queries used.
2 Correct 146 ms 676 KB Ok! 1179 queries used.
3 Correct 126 ms 632 KB Ok! 1150 queries used.
4 Correct 125 ms 760 KB Ok! 1193 queries used.
# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 776 KB Ok! 1144 queries used.
2 Correct 137 ms 688 KB Ok! 1204 queries used.
3 Correct 136 ms 688 KB Ok! 1220 queries used.
4 Correct 135 ms 632 KB Ok! 1219 queries used.
5 Correct 132 ms 632 KB Ok! 1252 queries used.
6 Correct 140 ms 760 KB Ok! 1254 queries used.
# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 760 KB Ok! 1198 queries used.
2 Correct 136 ms 700 KB Ok! 1213 queries used.