제출 #99391

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99391		long10024070	ICC (CEOI16_icc)	C++11	90 / 100	170 ms	640 KiB

icc

#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));
}

int Find(vector <pair<int,int> > v1, vector <pair<int,int> > v2)
{
    int na,nb,nc,a[maxn],b[maxn],c[maxn];
    Copy(nc,c,v1);
    Copy(nb,b,v2);
    int l = 0;
    int r = nc - 1;
    while (l <= r) {
        int m = (l + r) / 2;
        for (int i=0;i<=m;++i)
            a[i] = c[i];
        na = m + 1;
        if (!query(na,nb,a,b))
            l = m + 1;
        else
            r = m - 1;
    }
    return c[l];
}

void Step2()
{
    int a = Find(v1,v2);
    int b = Find(v2,v1);
    Union(Find_set(a),Find_set(b));
    setRoad(a,b);
}

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

컴파일 시 표준 에러 (stderr) 메시지

icc.cpp: In function 'void Step1()':
icc.cpp:88:9: warning: unused variable 't' [-Wunused-variable]
     int t = 0;
         ^

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 0 / 10