Submission #639505

#	Time	Username	Problem	Language	Result	Execution time	Memory
639505		Moses	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1847 ms	222972 KiB

bitaro

/*
           _                   _         _       __  __  _____ 
     /\   | |            /\   | |       | |     |  \/  |/ ____|
    /  \  | |__   ___   /  \  | |__   __| | ___ | \  / | |     
   / /\ \ | '_ \ / _ \ / /\ \ | '_ \ / _` |/ _ \| |\/| | |     
  / ____ \| |_) | (_) / ____ \| |_) | (_| | (_) | |  | | |____ 
 /_/    \_\_.__/ \___/_/    \_\_.__/ \__,_|\___/|_|  |_|\_____|
*/

// build command:
// g++ -o "exe" "%f" -Wall -Wextra -pedantic -std=c++11 -O2 -Wshadow -Wformat=2 -Wfloat-equal -Wconversion -Wlogical-op -Wshift-overflow=2 -Wduplicated-cond -Wcast-qual -Wcast-align -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC -D_FORTIFY_SOURCE=2 -fsanitize=address -fsanitize=undefined -fno-sanitize-recover -fstack-protector -D LOCAL -Wno-unused-result

#include <bits/stdc++.h>
using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const ld eps = 1e-9;
const int mod = 1e9 + 7;
const int oo = 1e9 + 7;
const ll lloo = 1e18 + 7;
const int N = 1e5 + 7;
const int SZ = 200;
int n,m,q;

vector<int> g[N],tg[N];
vector<int> toposort;
int vis[N];

void tsort(int u) {
	vis[u] = 1;
	for(auto v:g[u]) {
		if (!vis[v]) tsort(v);
	}
	toposort.pb(u);
}

vector<pii> dp[N]; // {dist[u],u}

int tmp[N];
int val[N];

bool cmp(int x,int y) {
	return val[x] > val[y];
}

void solve() {
	scanf("%d %d %d",&n,&m,&q);
	for(int i = 0 ; i < m ; i++) {
		int u,v;
		scanf("%d %d",&u,&v);
		g[u].pb(v);
		tg[v].pb(u);
	}
	for(int i = 1; i <= n ; i++) if (!vis[i]) tsort(i);
	reverse(all(toposort));
	vector<int> ok(n+1,0);
	for(auto u:toposort) {
		vector<int> ptr(sz(tg[u]),0);
		vector<int> alldp;
		for(auto v:tg[u]) {
			for(auto vvv:dp[v]) {
				int vv = vvv.S;
				if (ok[vv]) {
					val[vv] = val[vv] < vvv.F+1 ? vvv.F+1:val[vv];
				} else {
					val[vv] = vvv.F+1;
					alldp.pb(vv);
					ok[vv] = 1;
				}
			}
		}
		alldp.pb(u);
		val[u] = 0;
		sort(all(alldp),cmp);
		for(int i = 0 ; i < sz(alldp) && sz(dp[u]) < SZ+7 ; i++) {
			dp[u].pb({val[alldp[i]],alldp[i]});
		}
		
		for(auto x:alldp) ok[x] = 0;
	}
	
	vector<bool> yes(n+1,0);
	for(int i = 0 ; i < q ; i++) {
		int dest,k;
		scanf("%d %d",&dest,&k);
		vector<int> vec;
		for(int j = 0 ; j < k ; j++) {
			int v;
			scanf("%d",&v);
			vec.pb(v);
			yes[v] = 1;
		}
		
		if (k < SZ) {
			bool ok = 0;
			for(auto p:dp[dest]) {
				if (yes[p.S]) continue;
				printf("%d\n",p.F);
				ok = 1;
				break;
			}
			if (!ok) puts("-1");
		} else {
			memset(tmp,-1,sizeof tmp);
			for(auto u:toposort) {
				if (!yes[u]) tmp[u] = 0;
				for(auto v:tg[u]) {
					if (tmp[v] != -1) tmp[u] = max(tmp[u],tmp[v]+1);
				}
			}
			printf("%d\n",tmp[dest]);
		}
		
		for(auto v:vec) yes[v] = 0;
	}
}

int main() {
	// freopen("in","r",stdin);
	// freopen("out","w",stdout);
	int T = 1;
	//scanf("%d",&T);
	while(T--) solve();
	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void solve()':
bitaro.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  scanf("%d %d %d",&n,&m,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%d %d",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~~
bitaro.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |   scanf("%d %d",&dest,&k);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
bitaro.cpp:109:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |    scanf("%d",&v);
      |    ~~~~~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86