#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <stack>
#include <utility>
#include <cmath>
#include <numeric>
#include <assert.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 3007;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
void close(){ cout << "detention" << endl; exit(0); }
stack <int> stk;
vector <int> adj[M], group[M], cur;
int n, P, Q, in[M], out[M];
bool vist[M], frnd[M][M];
bool valid(vector <int> v)
{
int q = 0;
for(auto i : v) vist[i] = 1;
for(auto i : v) for(auto j : adj[i]) if(!vist[j]) ++q;
for(auto i : v) vist[i] = 0;
return (v.size() <= P && q <= Q);
}
void get(int source, int p, int q, bool add)
{
if(!group[source].empty() || p > P || q > Q || p + q + stk.size() > P + Q) return;
if(stk.empty()){
group[source] = cur;
return;
}
int node = stk.top();
stk.pop();
if(add){
in[node] = 1;
cur.pb(node);
vector <int> neighbores;
for(auto i : adj[node]){
if(!vist[i]){
neighbores.pb(i);
stk.push(i);
vist[i] = 1;
}
q += out[i];
}
get(source, p + 1, q, 0);
if(group[source].empty()) get(source, p + 1, q, 1);
for(auto i : neighbores){
vist[i] = 0;
stk.pop();
}
for(auto i : adj[node]) q -= out[i];
cur.pop_back();
in[node] = 0;
}
else{
out[node] = 1;
vector <int> neighbores;
for(auto i : adj[node]) q += in[i];
get(source, p, q, 0);
if(group[source].empty())get(source, p, q, 1);
for(auto i : neighbores){
vist[i] = 0;
stk.pop();
}
for(auto i : adj[node]) q -= in[i];
out[node] = 0;
}
stk.push(node);
return;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> P >> Q;
for(int i = 1; i <= n; ++i){
int m;
cin >> m;
for(int j = 1; j <= m; ++j){
int x;
cin >> x; ++x;
adj[i].pb(x);
frnd[i][x] = 1;
}
}
for(int i = 1; i <= n; ++i) for(int j = i + 1; j <= n; ++j) if(frnd[i][j] != frnd[j][i]) close();
for(int i = 1; i <= n; ++i){
stk.push(i);
vist[i] = 1;
get(i, 0, 0, 1);
vist[i] = 0;
stk.pop();
if(group[i].empty()) close();
}
for(int i = 1; i <= n; ++i){
for(int j = i + 1; j <= n; ++j){
vector <int> xi, xj, yi, yj;
bool ins = 0;
for(auto k : group[i]) in[k] = 0;
for(auto k : group[j]) in[k] = 0;
for(auto k : group[i]) in[k] |= 1;
for(auto k : group[j]) in[k] |= 2, ins |= (in[k] == 3);
if(!ins) continue;
for(auto k : group[i]){
if(in[k] == 1){
xi.pb(k);
xj.pb(k);
}
else yj.pb(k);
}
for(auto k : group[j]){
if(in[k] == 2){
yi.pb(k);
yj.pb(k);
}
else xi.pb(k);
}
swap(group[i], xi);
swap(group[j], yi);
}
}
cout << "home\n";
vector < vector <int> > ans;
for(int i = 1; i <= n; ++i) if(group[i].size()){
vector <int> v;
for(auto j : group[i]) v.pb(j);
ans.pb(v);
}
cout << ans.size() << endl;
for(auto i : ans){
cout << i.size() << " ";
for(auto j : i) cout << j - 1 << " ";
cout << endl;
}
return 0;
}
Compilation message
friends.cpp: In function 'bool valid(std::vector<int>)':
friends.cpp:41:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
41 | return (v.size() <= P && q <= Q);
| ~~~~~~~~~^~~~
friends.cpp: In function 'void get(int, int, int, bool)':
friends.cpp:46:75: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
46 | if(!group[source].empty() || p > P || q > Q || p + q + stk.size() > P + Q) return;
| ~~~~~~~~~~~~~~~~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
2 ms |
980 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
844 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
2 ms |
980 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
844 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
