Submission #639486

#	Time	Username	Problem	Language	Result	Execution time	Memory
639486		Moses	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	1053 ms	524288 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 = 300;
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];

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));
	for(auto u:toposort) {
		vector<int> ptr(sz(tg[u]),0);
		int ssz = sz(tg[u]);
		while(sz(dp[u]) < 2*SZ) {
			pair<pii,int> mx = {{-1,-1},-1}; // {{dist[u],u},ptridx}
			int cnt = 0;
			for(auto v:tg[u]) {
				if (ptr[cnt] >= sz(dp[v])) {cnt++;continue;}
				mx = mx < pair<pii,int>{dp[v][ptr[cnt]],cnt} ? pair<pii,int>{dp[v][ptr[cnt]],cnt}:mx;
				cnt++;
			}
			if (mx.S == -1) break;
			
			cnt = 0;
			for(auto v:tg[u]) {
				if (ptr[cnt] >= sz(dp[v])) {cnt++;continue;}
				if (dp[v][ptr[cnt]].S == mx.F.S) ptr[cnt]++;
				cnt++;
			}
			
			mx.F.F++;
			dp[u].pb(mx.F);
		}
		dp[u].pb({0,u});
	}
	
	reverse(all(toposort));
	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 {
			int ans = -1;
			for(auto u:toposort) {
				if (u == dest) tmp[u] = 0;
				else tmp[u] = -1;
				for(auto v:g[u]) {
					if (tmp[v] == -1) continue;
					tmp[u] = max(tmp[u],tmp[v]+1);
				}
				if (!yes[u]) ans = max(ans,tmp[u]);
			}
			printf("%d\n",ans);
		}
		
		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:73:7: warning: unused variable 'ssz' [-Wunused-variable]
   73 |   int ssz = sz(tg[u]);
      |       ^~~
bitaro.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%d %d %d",&n,&m,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   scanf("%d %d",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~~
bitaro.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   scanf("%d %d",&dest,&k);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
bitaro.cpp:105:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |    scanf("%d",&v);
      |    ~~~~~^~~~~~~~~

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