oj.uz

Submission #99406

# Submission time Handle Problem Language Result Execution time Memory
99406 2019-03-03T15:47:10 Z long10024070 ICC (CEOI16_icc) C++11
100 / 100
 178 ms 636 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;
    }

    na = l;

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

    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

Compilation message

icc.cpp: In function 'void Step2()':
icc.cpp:129:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int t=0;t<v1.size();++t) {
                  ~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 512 KB Ok! 105 queries used.
2 Correct 8 ms 512 KB Ok! 97 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 512 KB Ok! 530 queries used.
2 Correct 38 ms 512 KB Ok! 523 queries used.
3 Correct 34 ms 512 KB Ok! 552 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 636 KB Ok! 1359 queries used.
2 Correct 111 ms 540 KB Ok! 1259 queries used.
3 Correct 135 ms 560 KB Ok! 1421 queries used.
4 Correct 169 ms 632 KB Ok! 1475 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 556 KB Ok! 1509 queries used.
2 Correct 119 ms 596 KB Ok! 1364 queries used.
3 Correct 120 ms 560 KB Ok! 1486 queries used.
4 Correct 117 ms 512 KB Ok! 1506 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 636 KB Ok! 1413 queries used.
2 Correct 120 ms 512 KB Ok! 1420 queries used.
3 Correct 150 ms 556 KB Ok! 1425 queries used.
4 Correct 178 ms 564 KB Ok! 1509 queries used.
5 Correct 117 ms 636 KB Ok! 1433 queries used.
6 Correct 134 ms 632 KB Ok! 1540 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 512 KB Ok! 1532 queries used.
2 Correct 111 ms 632 KB Ok! 1281 queries used.