oj.uz

답안 #858523

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
858523 2023-10-08T15:30:41 Z Tenis0206 CEOI16_icc (CEOI16_icc) C++11
100 / 100
 103 ms 640 KB 
#include <bits/stdc++.h>
#ifndef home
#include "icc.h"
#endif // home

using namespace std;

const int nmax = 100;

#ifdef home

pair<int,int> e[nmax + 5];

void output(string msg)
{
    cout<<msg<<'\n';
    exit(0);
}

int cnt = 1;

int query(int sza, int szb, int a[], int b[])
{
    bool ok = false;
    for(int i=0;i<sza;i++)
    {
        for(int j=0;j<szb;j++)
        {
            for(int nr=1;nr<=cnt;nr++)
            {
                if(e[nr].first==a[i] && e[nr].second==b[j])
                {
                    ok = true;
                    break;
                }
                if(e[nr].first==b[j] && e[nr].second==a[i])
                {
                    ok = true;
                    break;
                }
            }
        }
    }
    return ok;
}

void setRoad(int a, int b)
{
    bool ok = false;
    if(a==e[cnt].first && b==e[cnt].second)
    {
        ok = true;
    }
    if(a==e[cnt].second && b==e[cnt].first)
    {
        ok = true;
    }
    if(!ok)
    {
        output("Bad edge");
    }
    ++cnt;
}

#endif // home

int n;

int a[nmax + 5], b[nmax + 5];
int vst[nmax + 5];

int t[nmax + 5];
vector<int> l[nmax + 5];

mt19937 my_rand(time(NULL));

int my_rand_val(int x)
{
    return my_rand() % x;
}

int rep(int x)
{
    if(t[x]==x)
    {
        return x;
    }
    return rep(t[x]);
}

void uneste(int x, int y)
{
    x = rep(x);
    y = rep(y);
    if(x==y)
    {
        return;
    }
    if(l[x].size() > l[y].size())
    {
        for(auto it : l[y])
        {
            l[x].push_back(it);
        }
        l[y].clear();
        t[y] = x;
    }
    else
    {
        for(auto it : l[x])
        {
            l[y].push_back(it);
        }
        l[x].clear();
        t[x] = y;
    }
}

pair<int,int> find_dif(int nra, int nrb)
{
    random_shuffle(a,a+nra,my_rand_val);
    random_shuffle(b,b+nrb,my_rand_val);
    int val_a = 0, val_b = 0;
    int st = 1;
    int dr = nra;
    while(st<dr)
    {
        int mij = (st + dr) >> 1;
        int nrv = 0;
        for(int i=st;i<=mij;i++)
        {
            vst[nrv++] = a[i - 1];
        }
        int ok = query(nrv, nrb, vst, b);
        if(ok)
        {
            dr = mij;
        }
        else
        {
            st = mij + 1;
        }
    }
    val_a = a[st - 1];

    st = 1;
    dr = nrb;
    while(st<dr)
    {
        int mij = (st + dr) >> 1;
        int nrv = 0;
        for(int i=st;i<=mij;i++)
        {
            vst[nrv++] = b[i - 1];
        }
        int ok = query(nrv, nra, vst, a);
        if(ok)
        {
            dr = mij;
        }
        else
        {
            st = mij + 1;
        }
    }
    val_b = b[st - 1];

    return {val_a, val_b};
}

void find_new_edge()
{
    vector<int> c;
    for(int i=1;i<=n;i++)
    {
        if(rep(i)==i)
        {
            c.push_back(i);
        }
    }
    random_shuffle(c.begin(),c.end(),my_rand_val);
    pair<int,int> rez = {0,0};
    for(int bit=0;(1<<bit)<c.size();bit++)
    {
        int nra = 0, nrb = 0;
        for(int i=0;i<c.size();i++)
        {
            if((i & (1<<bit)) == 0)
            {
                for(auto it : l[c[i]])
                {
                    a[nra++] = it;
                }
            }
            else
            {
                for(auto it : l[c[i]])
                {
                    b[nrb++] = it;
                }
            }
        }
        int ok = query(nra, nrb, a, b);
        if(ok)
        {
            rez = find_dif(nra, nrb);
            break;
        }
    }
    setRoad(rez.first,rez.second);
    uneste(rez.first, rez.second);
}

void run(int N)
{
    srand(time(NULL));
    n = N;
    for(int i=1;i<=n;i++)
    {
        t[i] = i;
        l[i].push_back(i);
    }
    for(int i=1;i<n;i++)
    {
        find_new_edge();
    }
}


#ifdef home
int main()
{
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    int nn;
    cin>>nn;
    for(int i=1;i<nn;i++)
    {
        int x,y;
        cin>>x>>y;
        e[i] = {x,y};
    }
    run(nn);
    output("OK");
    return 0;
}
#endif // home

Compilation message

icc.cpp: In function 'void find_new_edge()':
icc.cpp:183:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |     for(int bit=0;(1<<bit)<c.size();bit++)
      |                   ~~~~~~~~^~~~~~~~~
icc.cpp:186:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |         for(int i=0;i<c.size();i++)
      |                     ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 604 KB Ok! 100 queries used.
2 Correct 4 ms 604 KB Ok! 99 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 604 KB Ok! 528 queries used.
2 Correct 34 ms 632 KB Ok! 657 queries used.
3 Correct 30 ms 604 KB Ok! 638 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 624 KB Ok! 1386 queries used.
2 Correct 103 ms 628 KB Ok! 1604 queries used.
3 Correct 91 ms 624 KB Ok! 1512 queries used.
4 Correct 90 ms 624 KB Ok! 1495 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 604 KB Ok! 1485 queries used.
2 Correct 93 ms 604 KB Ok! 1490 queries used.
3 Correct 97 ms 640 KB Ok! 1594 queries used.
4 Correct 86 ms 600 KB Ok! 1417 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 600 KB Ok! 1583 queries used.
2 Correct 97 ms 600 KB Ok! 1591 queries used.
3 Correct 99 ms 624 KB Ok! 1599 queries used.
4 Correct 96 ms 604 KB Ok! 1580 queries used.
5 Correct 88 ms 604 KB Ok! 1474 queries used.
6 Correct 95 ms 600 KB Ok! 1510 queries used.

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 620 KB Ok! 1578 queries used.
2 Correct 102 ms 600 KB Ok! 1602 queries used.