Submission #606609

#	Time	Username	Problem	Language	Result	Execution time	Memory
606609		Vanilla	ICC (CEOI16_icc)	C++17	100 / 100	152 ms	632 KiB

icc

#include "icc.h"
#include <bits/stdc++.h>
using namespace std;const int maxn = 102;int _d[maxn];vector<int>el[maxn];int dad(int x) {return _d[x]=(x==_d[x]?x:dad(_d[x]));}void merge(int x,int y){x=dad(x),y=dad(y);if(x!=y) {for(int j:el[y])el[x].push_back(j);el[y].clear();_d[y]=x;}}int qq(vector<int>a,vector<int>b) {return query(a.size(),b.size(),a.data(),b.data());}void run(int n){srand(time(NULL));for(int i=1;i<=n;i++){_d[i]=i;el[i].push_back(i);}for(int p=0;p<n-1;p++){set<int>s;vector<int>c;for(int j=1;j<=n;j++)s.insert(dad(j));for(int k:s)c.push_back(k);sort(c.begin(),c.end(),[](int a,int b){return el[a].size()>el[b].size();});int m=c.size();vector<int>a,b;for(int i=0;i<8;i++){vector<int>v1,v2;for(int j=0;j<m;j++){if(j&(1<<i))for(int l:el[c[j]])v1.push_back(l);else for(int l:el[c[j]])v2.push_back(l);}if(qq(v1,v2)) {a=v1,b=v2;break;}}int l=0,r=a.size(),rs1=-1,rs2=-1;sort(a.begin(),a.end());sort(b.begin(),b.end());reverse(a.begin(),a.end());reverse(b.begin(),b.end());while(l<r){int m=(l+r)/2;vector<int>v;for (int i=0;i<=m;i++)v.push_back(a[i]);if(qq(v,b)) {rs1=v.back();r=m;}else{l=m+1;}}l=0,r=b.size();while(l<r){int m=(l+r)/2;vector<int>v;for(int i=0;i<=m;i++)v.push_back(b[i]);if(qq(v,a)) {rs2=v.back();r=m;}else{l=m+1;}}merge(rs1,rs2);setRoad(rs1,rs2);}}

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