// ~Be name khoda~ //
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 25e2 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
int grsz, mxed, pos = 0;
vector <int> verex, adj[maxn5], av[maxn5], tmp, esh;
int grsize, outedge, haveout[maxn5];
bool re, ntm[maxn5], ex[maxn5];
bool ex1[maxn5], ex2[maxn5];
bool ed[maxn5][maxn5], ab[maxn5];
int nn, exex[maxn5];
inline void kill(){
cout << "detention" << endl;
exit(0);
}
inline void solve(){
if(grsize > grsz || outedge > mxed)
return;
if(re)
return;
int v = -1;
for(auto u : verex) for(auto z : adj[u]) if(ntm[z]){
v = z;
}
if(v == -1){
//cout << "and now " << pos << ' ' << verex.size() << endl;
av[pos] = verex;
re = true;
haveout[pos] = outedge;
return;
}
//cout << verex.size() << ' ' << "this is " << v << endl;
ntm[v] = false;
ex[v] = true;
verex.pb(v);
grsize++;
int remem = outedge;
for(auto u : adj[v]) if(!ntm[u] && !ex[u])
outedge++;
solve();
//cout << "finaly see " << v << ' ' << verex.size() << endl;
if(re)
return;
verex.pop_back();
ex[v] = false;
grsize--;
outedge = remem;
for(auto u : adj[v]) if(!ntm[u] && ex[u])
outedge++;
solve();
if(re)
return;
outedge = remem;
ntm[v] = true;
return;
}
inline void mostaghel_kon(int id1, int id2){
if(av[id1].empty() || av[id2].empty())
return;
esh.clear();
for(auto u : av[id1])
ex1[u] = true;
for(auto u : av[id2])
ex2[u] = true;
for(auto u : av[id2]) if(ex1[u]){
esh.pb(u);
ab[u] = true;
}
if(esh.empty()){
for(auto u : av[id1])
ex1[u] = false;
for(auto u : av[id2])
ex2[u] = false;
for(auto u : esh)
ab[u] = false;
return;
}
int ext1 = 0, ext2 = 0;
for(auto u : esh) for(auto z : adj[u]) if(!ab[z]){
if(ex1[z])
ext1++;
if(ex2[z])
ext2++;
}
tmp.clear();
int rpid = id1;
if(ext1 + haveout[id1] <= mxed){
for(auto u : av[id1]) if(!ab[u])
tmp.pb(u);
haveout[id1] += ext1;
}
else{
rpid = id2;
for(auto u : av[id2]) if(!ab[u])
tmp.pb(u);
haveout[id2] += ext2;
}
for(auto u : av[id1])
ex1[u] = false;
for(auto u : av[id2])
ex2[u] = false;
for(auto u : esh)
ab[u] = false;
av[rpid] = tmp;
return;
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n; cin >> n >> grsz >> mxed;
nn = n;
for(int i = 0; i < n; i++){
int l; cin >> l;
while(l--){
int a; cin >> a;
ed[i][a] = true;
adj[i].pb(a);
}
}
for(int i = 0; i < n; i++) if(adj[i].size() > grsz + mxed)
kill();
for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++)
if(ed[i][j] != ed[j][i])
kill();
for(int i = 0; i < n; i++){
memset(ntm, true, sizeof ntm);
ex[i] = true;
ntm[i] = re = false;
outedge = 0;
grsize = 1;
verex.clear();
verex.pb(i);
solve();
if(!re)
kill();
//haveout[pos] = outedge;
pos++;
}
/*
cout << "___" << endl;
for(int i = 0; i < n; i++){
cout << av[i].size() << ' ';
for(auto u : av[i])
cout << u << ' ';
cout << endl;
}
//*/
//if(mxed > 2 && nn > 16)
//kill();
//assert(mxed <= 2 || nn <= 16);
cout << "home" << endl;
for(int i = 0; i < n; i++){
memset(ex, false, sizeof ex);
for(auto u : av[i])
ex[u] = true;
int cnt = 0;
for(auto u : av[i]) for(auto z : adj[u])
cnt += (!ex[z]);
assert(cnt <= mxed);
assert(haveout[i] != cnt);
}
memset(ex, false, sizeof ex);
for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++)
mostaghel_kon(i, j);
int cnt = 0;
for(int i = 0; i < n; i++) if(av[i].size()){
for(auto u : av[i]){
exex[u]++;
}
assert(av[i].size() <= grsz);
cnt++;
}
for(int i = 0; i < n; i++)
assert(exex[i] == 1);
cout << cnt << endl;
for(int i = 0; i < n; i++) if(av[i].size()){
cout << av[i].size() << ' ';
for(auto u : av[i])
cout << u << ' ';
cout << '\n';
}
}
Compilation message
friends.cpp: In function 'int main()':
friends.cpp:144:49: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
144 | for(int i = 0; i < n; i++) if(adj[i].size() > grsz + mxed)
| ~~~~~~~~~~~~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from friends.cpp:3:
friends.cpp:195:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
195 | assert(av[i].size() <= grsz);
| ~~~~~~~~~~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
452 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
1748 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
1748 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
452 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
724 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
