oj.uz

Submission #99393

# Submission time Handle Problem Language Result Execution time Memory
99393 2019-03-03T15:15:20 Z long10024070 ICC (CEOI16_icc) C++11
0 / 100
 16 ms 896 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});
    int t = 0;
    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;
    }
//    cerr << 0 << endl;
    int S = 0;
    for (auto p : v2) {
        int s = 0;
        for (int i=p.first;i<=p.second;++i)
            s += -lab[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;//, cerr << ' ' << u << ' ';
        }
        else
            S += s;
    }
//    cerr << endl;
    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;
    }
//    cerr << l << ' ' << l2 << ' ' << a[l-1] << ' ' << b[l2-1] << endl;
    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 Step1()':
icc.cpp:88:9: warning: unused variable 't' [-Wunused-variable]
     int t = 0;
         ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 29.0

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

Subtask #6
0 / 10.0

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