| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 46759 |
2018-04-22T22:29:38 Z |
wzy |
ICC (CEOI16_icc) |
C++11 |
|
328 ms |
688 KB |
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
#define pb push_back
int pai[150] , peso[150];
vector<int> linked[152];
int fd(int x){
return pai[x] == x ? x : pai[x] = fd(pai[x]);
}
void join(int u , int v){
u = fd(u) , v= fd(v);
if(peso[u] > peso[v]) swap(u,v);
pai[u] = v , peso[v] += peso[u] + 1;
for(int j = 0 ; j < linked[u].size() ; j++) linked[v].push_back(linked[u][j]);
linked[u].clear();
}
bool queryL(int a , int b , vector<int> x , vector<int> y){
int xx[150] , yy[150];
for(int i = 0 ; i < a ; i++) xx[i] = x[i];
for(int i = 0 ; i < b ; i++) yy[i] = y[i];
return query(a , b , xx , yy);
}
bool get(vector<int> l , vector<int> r){
if(l.size() == 0 || r.size() == 0) return 0;
bool w = queryL(l.size() , r.size() , l , r);
if(!w){
vector<int> ll , rr;
for(int i = 0 ; i < l.size() ; i++){
if(ll.size() && fd(ll.back()) == fd(l[i])){
ll.pb(l[i]);
}
else if(rr.size() && fd(rr.back()) == fd(l[i])) rr.pb(l[i]);
else{
if(ll.size() < rr.size()) ll.pb(l[i]);
else rr.pb(l[i]);
}
}
bool q = get(ll , rr);
if(!q){
vector<int> lr, rl;
for(int i = 0 ; i < r.size() ; i++){
if(lr.size() && fd(r[i]) == fd(lr.back())){
lr.pb(r[i]);
}
else if(rl.size() && fd(r[i]) == fd(rl.back())) rl.pb(r[i]);
else{
if(lr.size() < rr.size()) lr.pb(r[i]);
else rl.pb(r[i]);
}
}
q = get(lr , rl);
}
return q;
}
else{
int ll = 0 , rr = l.size() - 1;
int ansj = -1;
while(ll<=rr){
int mid = (ll + rr) / 2;
vector<int> opt;
for(int j = 0 ; j <= mid ; j++) opt.pb(l[j]);
bool q = queryL(opt.size() , r.size() , opt, r);
if(q){
rr = mid - 1;
ansj = mid;
}
else ll = mid + 1;
}
ll = 0 , rr = r.size() - 1;
int ansj2 = -1;
while(ll <= rr){
int mid = (ll +rr)/2;
vector<int> opt;
for(int j = 0 ; j <= mid; j++) opt.pb(r[j]);
bool q = queryL(opt.size() , l.size() , opt, l);
if(q){
rr = mid - 1;
ansj2 = mid;
}
else ll = mid + 1;
}
join(l[ansj] , r[ansj2]);
setRoad(l[ansj] , r[ansj2]);
return true;
}
}
void run(int n){
for(int i = 0 ; i <= n; i++) pai[i] = i , peso[i] = 0 , linked[i].pb(i);
for(int i = 0 ; i < n - 1 ; i++){
set<int> dependencies;
for(int j = 1 ; j <= n; j ++) dependencies.insert(j);
vector<int> l , r;
for(int j = 1 ; j <= n; j++){
if(!dependencies.count(j)) continue;
if(l.size() < r.size()){
for(int w = 0 ; w < linked[fd(j)].size() ; w++){
l.pb(linked[fd(j)][w]);
dependencies.erase(linked[fd(j)][w]);
}
}
else{
for(int w = 0 ; w < linked[fd(j)].size(); w++){
r.pb(linked[fd(j)][w]);
dependencies.erase(linked[fd(j)][w]);
}
}
}
get(l , r);
}
}
Compilation message
icc.cpp: In function 'void join(int, int)':
icc.cpp:17:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0 ; j < linked[u].size() ; j++) linked[v].push_back(linked[u][j]);
~~^~~~~~~~~~~~~~~~~~
icc.cpp: In function 'bool get(std::vector<int>, std::vector<int>)':
icc.cpp:33:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < l.size() ; i++){
~~^~~~~~~~~~
icc.cpp:46:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < r.size() ; i++){
~~^~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:103:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int w = 0 ; w < linked[fd(j)].size() ; w++){
~~^~~~~~~~~~~~~~~~~~~~~~
icc.cpp:109:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int w = 0 ; w < linked[fd(j)].size(); w++){
~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
508 KB |
Ok! 104 queries used. |
| 2 |
Correct |
10 ms |
616 KB |
Ok! 124 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
116 ms |
616 KB |
Not all edges were guessed! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
328 ms |
628 KB |
Number of queries more than 4500 out of 2250 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
290 ms |
688 KB |
Number of queries more than 4000 out of 2000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
266 ms |
688 KB |
Number of queries more than 3550 out of 1775 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
268 ms |
688 KB |
Number of queries more than 3250 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
