oj.uz

Submission #573496

# Submission time Handle Problem Language Result Execution time Memory
573496 2022-06-06T18:10:28 Z moonrabbit2 Friends (BOI17_friends) C++17
49 / 100
 9 ms 580 KB 
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
//#include <atcoder/all>
//using namespace atcoder;
//#include <bits/extc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/priority_queue.hpp>
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int> tii;
typedef tuple<db,db,db> tdb;
typedef tuple<ll,ll,ll> tll;
typedef tuple<int,int,int,int> ti4;
typedef tuple<ll,ll,ll,ll> tl4;
typedef tuple<db,db,db,db> td4;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //shuffle(a+1,a+1+n,rng)
uniform_int_distribution<> gen(1,100); //gen(rng)
ll modinv(ll a,ll m){
	if(m==1) return 0;
	a%=m;
	if(a<0) a+=m;
	if(a==1) return 1;
	return m-modinv(m,a)*m/a;
}
template <int MOD_> struct modnum{
private:
	int v;
public:
	static const int MOD = MOD_;
 
	modnum() : v(0) {}
	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int () const { return v; }
	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
	friend bool operator < (const modnum& a, const modnum& b) { return a.v < b.v; }
	friend bool operator <= (const modnum& a, const modnum& b) { return a.v <= b.v; }
	friend bool operator > (const modnum& a, const modnum& b) { return a.v > b.v; }
	friend bool operator >= (const modnum& a, const modnum& b) { return a.v >= b.v; }
 
	modnum operator ~ () const {
		modnum res;
		res.v = modinv(v, MOD);
		return res;
	}
 
	modnum& operator += (const modnum& o) {
		v += o.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modnum& operator -= (const modnum& o) {
		v -= o.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modnum& operator *= (const modnum& o) {
		v = int(ll(v) * ll(o.v) % MOD);
		return *this;
	}
	modnum& operator /= (const modnum& o) {
		return *this *= (~o);
	}
 
	modnum operator-() const { return modnum(-v); }
	modnum& operator++() { return *this += 1; }
	modnum operator++(int){ modnum tmp=*this; ++*this; return tmp; }
	modnum& operator--() { return *this -= 1; }
	modnum operator--(int){ modnum tmp=*this; --*this; return tmp; }
 
	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
	friend modnum pow(modnum a, ll p) {
		modnum ans = 1;
		for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans;
	}
	friend ostream& operator<<(std::ostream& os, const modnum& o)
	{
		os << o.v;
		return os;
	}
	friend istream& operator>>(std::istream& is, modnum& o)
	{
		is >> o.v;
		return is;
	}
};
const ll mod=998244353,inf=1e18;
using mi=modnum<mod>;
const int N=2505,M=2555,Q=1e6+5;
int n,p,q,m,ans;
bool vis[N];
vector<int> S[N];
vector<int> g[N];
bool in[N];
int adj[N],k,cp,cq;
bool inA[N];
vector<int> cur;
bool ok(vector<int> S){
	if(S.size()>p) return false;
	int cq=0;
	for(int u: S) in[u]=true;
	for(int u: S) for(int v: g[u]) if(!in[v]) cq++;
	for(int u: S) in[u]=false;
	return cq<=q;
}
bool Find(int i){
	int u=adj[i];
	if(cp+1<=p){
		cur.emplace_back(u);
		if(ok(cur)) return true;
		int cnt=0;
		for(int v: g[u]) if(!inA[v]) cnt++;
		if(k+cnt<=p+q){
			int nk=k;
			for(int v: g[u]) if(!inA[v]){
				adj[++k]=v;
				inA[v]=true;
			}
			cp++;
			if(Find(i+1)) return true;
			cp--;
			for(int i=nk+1;i<=k;i++) inA[adj[i]]=false;
			k=nk;
		}
		cur.pop_back();
	}
	if(i!=1&&cq+1<=q){
		cq++;
		if(Find(i+1)) return true;
		cq--;
	}
	return false;
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>p>>q;
	if(!p){
		cout<<"detention\n";
		return 0;
	}
	for(int m,i=1;i<=n;i++){
		cin>>m;
		if(m>p+q){
			cout<<"detention\n";
			return 0;
		}
		g[i].resize(m);
		for(int &u: g[i]){
			cin>>u; u++;
		}
	}
	for(int i=1;i<=n;i++) for(int u: g[i]) if(i<u){
		bool ok=false;
		for(int v: g[u]) if(i==v){
			ok=true;
			break;
		}
		if(!ok){
			cout<<"detention\n";
			return 0;
		}
	}
	for(int i=1;i<=n;i++) if(!vis[i]){
		m++;
		cp=cq=0;
		k=1; adj[1]=i; inA[i]=1;
		cur.clear();
		if(!Find(1)){
			cout<<"detention\n";
			return 0;
		}
		for(int u: cur) vis[u]=true;
		S[m]=cur;
		for(int i=1;i<=k;i++) inA[adj[i]]=0;
	}
	for(int i=1;i<=m;i++) for(int j=i+1;j<=m;j++){
		vector<int> nA,nB;
		for(int u: S[j]) in[u]=true;
		for(int u: S[i]) if(!in[u]) nA.emplace_back(u);
		for(int u: S[j]) in[u]=false;
		for(int u: S[i]) in[u]=true;
		for(int u: S[j]) if(!in[u]) nB.emplace_back(u);
		for(int u: S[i]) in[u]=false;
		if(ok(nA)) S[i]=nA;
		else S[j]=nB;
	}
	for(int i=1;i<=m;i++) if(S[i].size()) ans++;
	cout<<"home\n"<<ans<<"\n";
	for(int i=1;i<=m;i++) if(S[i].size()){
		cout<<S[i].size()<<" ";
		for(int u: S[i]) cout<<u-1<<" ";
		cout<<"\n";
	}
	return 0;
}

Compilation message

friends.cpp: In function 'bool ok(std::vector<int>)':
friends.cpp:116:13: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  116 |  if(S.size()>p) return false;
      |     ~~~~~~~~^~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Failed 0 ms 340 KB EMERGENCY!!! contestant found solution when jury didn't
9 Halted 0 ms 0 KB -

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 580 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 580 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 6 ms 468 KB Output is correct
11 Correct 9 ms 564 KB Output is correct
12 Correct 9 ms 552 KB Output is correct
13 Correct 8 ms 552 KB Output is correct
14 Correct 1 ms 464 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 464 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Failed 0 ms 340 KB EMERGENCY!!! contestant found solution when jury didn't
9 Halted 0 ms 0 KB -