# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
62877 |
2018-07-30T15:35:08 Z |
IvanC |
ICC (CEOI16_icc) |
C++17 |
|
199 ms |
1032 KB |
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 110;
int pai[MAXN],N;
vector<int> filhos[MAXN];
int cjt_a[MAXN],cjt_b[MAXN],szA,szB;
int find(int x){
if(x == pai[x]) return x;
return pai[x] = find(pai[x]);
}
void join(int x,int y){
x = find(x);
y = find(y);
if(x == y) return;
if(x < y) swap(x,y);
pai[y] = x;
for(int z : filhos[y]) filhos[x].push_back(z);
}
int doQuery(vector<int> A,vector<int> B){
if(A.empty() || B.empty()) return 0;
szA = 0;
szB = 0;
memset(cjt_a,0,sizeof(cjt_a));
memset(cjt_b,0,sizeof(cjt_b));
for(int i : A){
cjt_a[szA] = i;
szA++;
}
for(int i : B){
cjt_b[szB] = i;
szB++;
}
return query(szA,szB,cjt_a,cjt_b);
}
int solve(vector<int> unknown_nodes, vector<int> fixed_nodes ){
if(unknown_nodes.size() == 1) return unknown_nodes[0];
vector<int> firstHalf,secondHalf;
int m = unknown_nodes.size()/2;
for(int i = 0;i<unknown_nodes.size();i++){
if(i < m) firstHalf.push_back(unknown_nodes[i]);
else secondHalf.push_back(unknown_nodes[i]);
}
if(doQuery(firstHalf,fixed_nodes)) return solve(firstHalf,fixed_nodes);
else return solve(secondHalf,fixed_nodes);
}
int test_partition(int bit,vector<int>& A,vector<int>& B,vector<int> possible,int flag){
for(int i = 0;i<possible.size();i++){
int j = possible[i];
if(i & (1 << bit)){
for(int k : filhos[j]) A.push_back(k);
}
else{
for(int k : filhos[j]) B.push_back(k);
}
}
if(flag) return 1;
else return doQuery(A,B);
}
void discover_edge(){
vector<int> possiveis,quaisbits,A,B;
for(int i = 1;i<=N;i++){
if(find(i) == i) possiveis.push_back(i);
}
for(int i = 0;(1 << i) <= possiveis.size();i++) quaisbits.push_back(i);
//random_shuffle(quaisbits.begin(),quaisbits.end());
for(int j = 0;j<quaisbits.size();j++){
A.clear();
B.clear();
int i = quaisbits[j],flag = (j == quaisbits.size() - 1);
if(!test_partition(i,A,B,possiveis,flag)) continue;
int x = solve(A,B);
int y = solve(B,A);
join(x,y);
setRoad(x,y);
break;
}
}
void run(int n){
N = n;
for(int i = 1;i<=N;i++){
pai[i] = i;
filhos[i].push_back(i);
}
for(int i = 1;i<N;i++){
discover_edge();
}
}
Compilation message
icc.cpp: In function 'int solve(std::vector<int>, std::vector<int>)':
icc.cpp:48:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<unknown_nodes.size();i++){
~^~~~~~~~~~~~~~~~~~~~~
icc.cpp: In function 'int test_partition(int, std::vector<int>&, std::vector<int>&, std::vector<int>, int)':
icc.cpp:59:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<possible.size();i++){
~^~~~~~~~~~~~~~~~
icc.cpp: In function 'void discover_edge()':
icc.cpp:80:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;(1 << i) <= possiveis.size();i++) quaisbits.push_back(i);
~~~~~~~~~^~~~~~~~~~~~~~~~~~~
icc.cpp:83:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0;j<quaisbits.size();j++){
~^~~~~~~~~~~~~~~~~
icc.cpp:86:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
int i = quaisbits[j],flag = (j == quaisbits.size() - 1);
~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
508 KB |
Ok! 94 queries used. |
2 |
Correct |
12 ms |
660 KB |
Ok! 100 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
704 KB |
Ok! 528 queries used. |
2 |
Correct |
49 ms |
736 KB |
Ok! 650 queries used. |
3 |
Correct |
59 ms |
836 KB |
Ok! 657 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
199 ms |
836 KB |
Ok! 1496 queries used. |
2 |
Correct |
174 ms |
836 KB |
Ok! 1611 queries used. |
3 |
Correct |
178 ms |
836 KB |
Ok! 1609 queries used. |
4 |
Correct |
167 ms |
880 KB |
Ok! 1528 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
163 ms |
880 KB |
Ok! 1575 queries used. |
2 |
Correct |
196 ms |
888 KB |
Ok! 1569 queries used. |
3 |
Correct |
175 ms |
888 KB |
Ok! 1611 queries used. |
4 |
Correct |
168 ms |
900 KB |
Ok! 1538 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
169 ms |
900 KB |
Ok! 1611 queries used. |
2 |
Correct |
184 ms |
1032 KB |
Ok! 1611 queries used. |
3 |
Correct |
153 ms |
1032 KB |
Ok! 1610 queries used. |
4 |
Correct |
149 ms |
1032 KB |
Ok! 1608 queries used. |
5 |
Correct |
175 ms |
1032 KB |
Ok! 1515 queries used. |
6 |
Correct |
181 ms |
1032 KB |
Ok! 1571 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
150 ms |
1032 KB |
Ok! 1611 queries used. |
2 |
Correct |
156 ms |
1032 KB |
Ok! 1611 queries used. |