oj.uz

답안 #99401

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
99401 2019-03-03T15:37:48 Z long10024070 CEOI16_icc (CEOI16_icc) C++11
90 / 100
 164 ms 632 KB 
#define Link "https://oj.uz/problem/view/CEOI16_icc?fbclid=IwAR3zUkXphYZ03X19rLXUiIzsinARdfw73iiD643HvAo307t3OS9ExkNZRTs"

#include <iostream>
#include <cstdio>
#include <vector>

#define TASK "ICC"

using namespace std;

const int maxn = 1e2 + 10;
int lab[maxn];
vector <int> member[maxn],use;
vector <pair<int,int> > v1,v2,_v1,_v2;

#ifdef LHL
bool e[maxn][maxn];
int n,newa,newb,cnt,point;

int query(int na, int nb, int a[], int b[])
{
    for (int i=0;i<na;++i)
        for (int j=0;j<nb;++j)
            if (e[a[i]][b[j]])
                return 1;
    return 0;
}

void setRoad(int a, int b)
{
    ++cnt;
    if (cnt >= n)
        return;
    if (a > b)
        swap(a,b);
    if (newa == a && newb == b)
        ++point;
    if (cnt < n - 1) {
        cin >> newa >> newb;
        if (newa > newb)
            swap(newa,newb);
        e[newa][newb] = e[newb][newa] = 1;
    }
    if (cnt == n - 1)
        cout << point;
}
#else
#include "icc.h"
#endif // LHL

int Find_set(int n)
{
    return lab[n] > 0 ? lab[n] = Find_set(lab[n]) : n;
}

void Union(int s, int t)
{
    if (lab[s] > lab[t])
        swap(s,t);
    lab[s] += lab[t];
    lab[t] = s;
    for (int u : member[t])
        member[s].push_back(u);
}

void Copy(int &n, int a[], vector <pair<int,int> > v)
{
    n = 0;
    for (auto p : v)
        for (int i=p.first;i<=p.second;++i)
            for (int u : member[use[i]])
                a[n++] = u;
}

bool Check(vector <pair<int,int> > v1, vector <pair<int,int> > v2)
{
    int na,nb,a[maxn],b[maxn];
    Copy(na,a,v1);
    Copy(nb,b,v2);
    return query(na,nb,a,b);
}

void Step1()
{
    v1.clear();
    v2.clear();
    v1.push_back({0,use.size()-1});
    do {
        _v1.clear();
        _v2.clear();
        for (auto p : v1)
            if (p.first != p.second) {
                int l = p.first;
                int r = p.second;
                _v1.push_back({l,(l+r)/2});
                _v2.push_back({(l+r)/2+1,r});
           }
        for (auto p : v2)
            if (p.first != p.second) {
                int l = p.first;
                int r = p.second;
                _v1.push_back({l,(l+r)/2});
                _v2.push_back({(l+r)/2+1,r});
           }
        v1 = _v1;
        v2 = _v2;
    } while (!Check(v1,v2));
}

void Step2()
{
    int na,nb,a[maxn],b[maxn];
    Copy(na,a,v1);
    Copy(nb,b,v2);
    int l = 1;
    int r = na;
    while (l <= r) {
        int m = (l + r) / 2;
        na = m;
        if (!query(na,nb,a,b))
            l = m + 1;
        else
            r = m - 1;
    }

//    int S = 0;
//    for (auto p : v2) {
//        int s = 0;
//        for (int i=p.first;i<=p.second;++i)
//            s -= lab[use[i]];
//        if (S <= l && l <= S + s) {
//            nb = 0;
//            for (int i=p.first;i<=p.second;++i)
//                for (int u : member[use[i]])
//                    b[nb++] = u;
//            break;
//        }
//        else
//            S += s;
//    }

    a[0] = a[l-1];
    na = 1;

    int l2 = 1;
    int r2 = nb;
    while (l2 <= r2) {
        int m = (l2 + r2) / 2;
        nb = m;
        if (!query(na,nb,a,b))
            l2 = m + 1;
        else
            r2 = m - 1;
    }

    Union(Find_set(a[l-1]),Find_set(b[l2-1]));
    setRoad(a[l-1],b[l2-1]);
}

void run(int n)
{
    for (int i=1;i<=n;++i) {
        lab[i] = -1;
        member[i].push_back(i);
    }
    for (int t=1;t<n;++t) {
        use.clear();
        for (int i=1;i<=n;++i)
            if (lab[i] < 0)
                use.push_back(i);
        Step1();
        Step2();
    }
}

#ifdef LHL
void Enter()
{
    cin >> n >> newa >> newb;
    if (newa > newb)
        swap(newa,newb);
    e[newa][newb] = e[newb][newa] = 1;
}

void Init()
{

}

void Solve()
{
    run(n);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    freopen(".INP","r",stdin);
    freopen(".OUT","w",stdout);

    Enter();
    Init();
    Solve();
}
#else
#endif //LHL

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 512 KB Ok! 105 queries used.
2 Correct 9 ms 512 KB Ok! 109 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 512 KB Ok! 544 queries used.
2 Correct 56 ms 512 KB Ok! 622 queries used.
3 Correct 50 ms 512 KB Ok! 651 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 512 KB Ok! 1467 queries used.
2 Correct 122 ms 632 KB Ok! 1531 queries used.
3 Correct 120 ms 512 KB Ok! 1555 queries used.
4 Correct 155 ms 556 KB Ok! 1590 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 632 KB Ok! 1611 queries used.
2 Correct 120 ms 512 KB Ok! 1533 queries used.
3 Correct 138 ms 592 KB Ok! 1623 queries used.
4 Correct 137 ms 604 KB Ok! 1578 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 568 KB Ok! 1632 queries used.
2 Correct 164 ms 568 KB Ok! 1602 queries used.
3 Correct 133 ms 632 KB Ok! 1619 queries used.
4 Correct 129 ms 512 KB Ok! 1637 queries used.
5 Correct 125 ms 512 KB Ok! 1522 queries used.
6 Correct 128 ms 512 KB Ok! 1641 queries used.

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 150 ms 596 KB Too many queries! 1652 out of 1625
2 Halted 0 ms 0 KB -