#include "key.h"
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
using pii = pair<int,int>;
int par[1005];
vector<int> cyc[1005], P[1005];
int sz[1005];
int n_cyc, clk;
int cycid[1005];
int chk[1005];
int gsz(int i){
TakeKey(i);
return Explore();
}
int gsz_range(int s, int e, vector<int>& T, int u){
for(int i = s; i <= e; i++) TakeKey(T[i]);
TakeKey(u);
int K = Explore();
//cout << "gsz_range = " << K << '\n';
return K;
}
int get_union(int s, int e, vector<int>& T, int lim){
++clk;
int cnt = 0;
for(int i = s; i <= e && i < lim; i++){
int t = T[i];
while(true){
if(!par[t]){
if(chk[t] == clk) break;
for(int u : cyc[ cycid[t] ]){
chk[u] = clk;
++cnt;
}
break;
}
if(chk[t] == clk) break;
chk[t] = clk; ++cnt;
t = par[t];
}
}
for(int i = lim; i <= e; i++) cnt += sz[ T[i] ];
//cout << "get_union = " << cnt << '\n';
return cnt;
}
void Report_tree(int s, int t){
while(par[t]){
Report(s, t);
t = par[t];
}
for(int u : cyc[cycid[t]]) Report(s, u);
}
void Report_cycle(vector<int>& C){
for(int u : C){
for(int v : C){
if(u != v) Report(u, v);
}
}
}
void EnsureKeyInfo(int n) {
for(int i = 1; i <= n; i++){
int g = gsz(i);
P[g].push_back(i);
sz[i] = g;
Report(i, i);
}
for(int u : P[1]){
cycid[u] = ++n_cyc;
cyc[n_cyc].push_back(u);
}
for(int j = 2; j <= n; j++){
int s_cyc = n_cyc + 1;
//cout << "j = " << j << '\n';
int capt = P[j-1].size();
for(int u : P[j]){
//cout << "u = " << u << '\n';
int lo = 0, hi = (int)P[j-1].size()-1, mi;
//cout << "P : "; for(int k : P[j-1]) cout << k << ' '; cout << '\n';
if(gsz_range(lo, hi, P[j-1], u) > get_union(lo, hi, P[j-1], capt) + 1){
//cout << "making new cycle\n";
P[j-1].push_back(u);
cycid[u] = ++n_cyc;
cyc[n_cyc].push_back(u);
continue;
}
while(lo < hi){
mi = lo + hi >> 1;
if(gsz_range(lo, mi, P[j-1], u) > get_union(lo, mi, P[j-1], capt) + 1) lo = mi + 1;
else hi = mi;
}
//cout << "bs result : " << P[j-1][lo] << '\n';
if(lo < capt){
par[u] = P[j-1][lo];
Report_tree(u, P[j-1][lo]);
}
else{
cycid[u] = cycid[ P[j-1][lo] ];
cyc[cycid[ P[j-1][lo] ]].push_back(u);
}
}
for(int i = s_cyc; i <= n_cyc; i++){
assert(cyc[i].size() == j);
Report_cycle(cyc[i]);
}
//cout << '\n';
}
}
Compilation message
key.cpp: In function 'void EnsureKeyInfo(int)':
key.cpp:95:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mi = lo + hi >> 1;
~~~^~~~
In file included from /usr/include/c++/7/cassert:44:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
from key.cpp:2:
key.cpp:111:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(cyc[i].size() == j);
~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
760 KB |
Output is correct |
| 3 |
Correct |
2 ms |
760 KB |
Output is correct |
| 4 |
Runtime error |
3 ms |
1144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
760 KB |
Output is correct |
| 3 |
Correct |
2 ms |
760 KB |
Output is correct |
| 4 |
Runtime error |
3 ms |
1144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
760 KB |
Output is correct |
| 3 |
Correct |
2 ms |
760 KB |
Output is correct |
| 4 |
Runtime error |
3 ms |
1144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
