Submission #1244639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244639		erering	ICC (CEOI16_icc)	C++20	100 / 100	79 ms	632 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
#include <vector>
using namespace std;
#define pb push_back
const int MAXN=100+5;
int par[MAXN],sz[MAXN];
int find(int x){
    return par[x]=(par[x]==x?x:find(par[x]));
}
void merge(int a,int b){
    a=find(a);
    b=find(b);
    if(sz[a]>sz[b])swap(a,b);
    par[a]=b;
    sz[b]+=sz[a];
}
vector<int> vec[MAXN];
int Query(vector<int> a,vector<int> b,bool flag){
    if(flag){
        vector<int> c,d;
        for(auto i:a){
            for(auto j:vec[i])c.pb(j);
        }
        for(auto i:b){
            for(auto j:vec[i])d.pb(j);
        }
        a=c; b=d;
    }
    int arr[a.size()],arrb[b.size()];
    for(int i=0;i<a.size();i++)arr[i]=a[i];
    for(int i=0;i<b.size();i++)arrb[i]=b[i];
    return query(a.size(),b.size(),arr,arrb);
}
pair<int,int> start(vector<int> a,vector<int> b,bool flag){
    if(a.size()==1 && b.size()==1)return {a[0],b[0]};
    if(a.size()==1)swap(a,b);
    vector<int> c;
    for(int i=a.size()-1;i>=a.size()/2;i--)c.pb(a[i]);
    if(!Query(c,b,flag)){
        c.clear();
        for(int i=0;i<a.size()/2;i++)c.pb(a[i]);
    }
    if(b.size()==1)return start(c,b,flag);
    vector<int> d;
    for(int i=b.size()-1;i>=b.size()/2;i--)d.pb(b[i]);
        if(Query(c,d,flag))return start(c,d,flag);
    d.clear();
    for(int i=0;i<b.size()/2;i++)d.pb(b[i]);
    return start(c,d,flag);
}
void run(int N) {
    for(int i=1;i<=N;i++){
        par[i]=i;
        sz[i]=1;
    }
    for (int built = 0; built < N - 1; ++built) {
        for(int i=1;i<=N;i++)vec[i].clear();
        vector<int> all;
        for(int i=1;i<=N;i++){
            if(vec[find(i)].size()==0)all.pb(find(i));
            vec[find(i)].pb(i);
        }
        vector<int> a,b;
        int x=1,cnt=0;
        while(x<all.size()){
            x*=2;
            cnt++;
        }
        for(int i=0;i<cnt;i++){
            a.clear(); b.clear();
            for(int j=0;j<all.size();j++){
                if((j>>i)&1)a.pb(all[j]);
                else b.pb(all[j]);
            }
            if(a.empty() || b.empty())continue;
            if(Query(a,b,1))break;
        }
        vector<int> c,d;
        for(int i=0;i<a.size();i++){
            for(auto j:vec[a[i]])c.pb(j);
        }
        for(int i=0;i<b.size();i++){
            for(auto j:vec[b[i]])d.pb(j);
        }
        pair<int,int> ans=start(c,d,0);
        merge(ans.first,ans.second);
        setRoad(ans.first,ans.second);
    }
}

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