oj.uz

답안 #606609

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
606609 2022-07-26T07:25:23 Z Vanilla CEOI16_icc (CEOI16_icc) C++17
100 / 100
 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);}}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 468 KB Ok! 104 queries used.
2 Correct 5 ms 432 KB Ok! 110 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 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.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 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.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 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.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 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.

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 110 ms 508 KB Ok! 1549 queries used.
2 Correct 120 ms 512 KB Ok! 1568 queries used.