Submission #1185697

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185697		Hanksburger	ICC (CEOI16_icc)	C++20	100 / 100	75 ms	632 KiB

icc

#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[105];
void run(int n)
{
    for (int i=1; i<n; i++)
    {
        vector<vector<int> > components;
        queue<int> q;
        int visited[n+5]={};
        for (int j=1; j<=n; j++)
        {
            if (visited[j])
                continue;
            vector<int> tmp;
            visited[j]=1;
            q.push(j);
            tmp.push_back(j);
            while (!q.empty())
            {
                int u=q.front();
                q.pop();
                for (int v:adj[u])
                {
                    if (!visited[v])
                    {
                        visited[v]=1;
                        q.push(v);
                        tmp.push_back(v);
                    }
                }
            }
            components.push_back(tmp);
            /*cout << "component: ";
            for (int u:tmp)
                cout << u << ' ';
            cout << '\n';*/
        }
        int sz=components.size(), loog=log2(sz-0.5), ind=0;
        for (int j=loog; j; j--)
        {
            vector<int> vec1, vec0;
            for (int k=0; k<sz; k++)
            {
                if (k&(1<<j))
                {
                    for (int u:components[k])
                        vec1.push_back(u);
                }
                else
                {
                    for (int u:components[k])
                        vec0.push_back(u);
                }
            }
            int a[vec1.size()], b[vec0.size()];
            for (int k=0; k<vec1.size(); k++)
                a[k]=vec1[k];
            for (int k=0; k<vec0.size(); k++)
                b[k]=vec0[k];
            int res=query(vec1.size(), vec0.size(), a, b);
            if (res)
            {
                ind=j;
                break;
            }
        }
        int l=0, r=(sz-1)/(1<<(ind+1));
        while (l<r)
        {
            int mid=(l+r)/2;
            vector<int> vec1, vec0;
            for (int j=(1<<(ind+1))*l; j<min(sz, (1<<(ind+1))*(mid+1)); j++)
            {
                if (j&(1<<ind))
                {
                    for (int u:components[j])
                        vec1.push_back(u);
                }
                else
                {
                    for (int u:components[j])
                        vec0.push_back(u);
                }
            }
            int a[vec1.size()], b[vec0.size()];
            for (int k=0; k<vec1.size(); k++)
                a[k]=vec1[k];
            for (int k=0; k<vec0.size(); k++)
                b[k]=vec0[k];
            int res=query(vec1.size(), vec0.size(), a, b);
            if (res)
                r=mid;
            else
                l=mid+1;
        }
        vector<int> vec1, vec0;
        for (int j=(1<<(ind+1))*l; j<min(sz, (1<<(ind+1))*(l+1)); j++)
        {
            if (j&(1<<ind))
            {
                for (int u:components[j])
                    vec1.push_back(u);
            }
            else
            {
                for (int u:components[j])
                    vec0.push_back(u);
            }
        }
        /*cout << "edge must be between ";
        for (int u:vec1)
            cout << u << ' ';
        cout << "and ";
        for (int v:vec0)
            cout << v << ' ';
        cout << '\n';*/
        int ll=0, rr=vec1.size()-1;
        while (ll<rr)
        {
            int mid=(ll+rr)/2;
            int a[mid-ll+1], b[vec0.size()];
            for (int k=ll; k<=mid; k++)
                a[k-ll]=vec1[k];
            for (int k=0; k<vec0.size(); k++)
                b[k]=vec0[k];
            int res=query(mid-ll+1, vec0.size(), a, b);
            if (res)
                rr=mid;
            else
                ll=mid+1;
        }
        int lll=0, rrr=vec0.size()-1;
        while (lll<rrr)
        {
            int mid=(lll+rrr)/2;
            int a[1]={vec1[ll]}, b[mid-lll+1];
            for (int k=lll; k<=mid; k++)
                b[k-lll]=vec0[k];
            int res=query(1, mid-lll+1, a, b);
            if (res)
                rrr=mid;
            else
                lll=mid+1;
        }
        int U=vec1[ll], V=vec0[lll];
        adj[U].push_back(V);
        adj[V].push_back(U);
        setRoad(U, V);
    }
}

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