| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 606609 |
2022-07-26T07:25:23 Z |
Vanilla |
ICC (CEOI16_icc) |
C++17 |
|
152 ms |
632 KB |
#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);}}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
468 KB |
Ok! 104 queries used. |
| 2 |
Correct |
5 ms |
432 KB |
Ok! 110 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
500 KB |
Ok! 525 queries used. |
| 2 |
Correct |
32 ms |
468 KB |
Ok! 650 queries used. |
| 3 |
Correct |
39 ms |
504 KB |
Ok! 662 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
500 KB |
Ok! 1453 queries used. |
| 2 |
Correct |
114 ms |
512 KB |
Ok! 1566 queries used. |
| 3 |
Correct |
112 ms |
496 KB |
Ok! 1615 queries used. |
| 4 |
Correct |
108 ms |
588 KB |
Ok! 1476 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
632 KB |
Ok! 1537 queries used. |
| 2 |
Correct |
105 ms |
512 KB |
Ok! 1512 queries used. |
| 3 |
Correct |
113 ms |
520 KB |
Ok! 1595 queries used. |
| 4 |
Correct |
117 ms |
504 KB |
Ok! 1487 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
113 ms |
512 KB |
Ok! 1575 queries used. |
| 2 |
Correct |
114 ms |
508 KB |
Ok! 1566 queries used. |
| 3 |
Correct |
120 ms |
616 KB |
Ok! 1572 queries used. |
| 4 |
Correct |
152 ms |
508 KB |
Ok! 1621 queries used. |
| 5 |
Correct |
120 ms |
508 KB |
Ok! 1481 queries used. |
| 6 |
Correct |
113 ms |
500 KB |
Ok! 1498 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
508 KB |
Ok! 1549 queries used. |
| 2 |
Correct |
120 ms |
512 KB |
Ok! 1568 queries used. |
