Submission #1273533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273533		lovrot	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	17 ms	4248 KiB

bitaro

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>

#define X first
#define Y second
#define PB push_back

using namespace std; 

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e5 + 10;
const int S = 335;
const int OO = 1e9;

int n, m, q;
vector<int> g[N], h[N], topo;

vector<pii> s;
int t[N];

void dfs(int u) { 
	t[u] = 1;
	for(int v : g[u]) { 
		if(!t[v]) { dfs(v); }
	}
	topo.PB(u);
}

int bus[N];
vector<pii> can[N];

int main() { 
	scanf("%d%d%d", &n, &m, &q);
	for(; m--; ) { 
		int u, v;
		scanf("%d%d", &u, &v);
		g[u].PB(v);
		h[v].PB(u);
	}

	for(int i = 1; i <= n; ++i) { if(!t[i]) dfs(i); }
	reverse(topo.begin(), topo.end());

//	for(auto &i : topo) printf("%d\n", i); 
	
	memset(t, 0, sizeof(t));

	for(int u : topo) { 
		s.clear();
		s.PB({0, u});

		for(int v : h[u]) { 
			for(pii p : can[v]) { s.PB({p.X + 1, p.Y}); }
		}

		sort(s.begin(), s.end());
		reverse(s.begin(), s.end());

		for(pii p : s) { 
			if(!t[p.Y]) { can[u].PB(p); t[p.Y] = 1; }
			if(can[u].size() > S) { break; }
		}

//		printf("%d:\n", u);
//		for(auto &i : can[u]) printf("%d %d\n", i.X, i.Y); 
		for(pii p : can[u]) { t[p.Y] = 0; }
	}

	for(; q--; ) { 
		int u, k;
		scanf("%d%d", &u, &k);
		
		for(int i = 0; i < k; ++i) { scanf("%d", bus + i); }
		for(int i = 0; i < k; ++i) { t[bus[i]] = -OO; }

		bool flag = 0;
		if(k < S) { 
			for(auto &i : can[u]) { 
				if(!t[i.Y]) { 
					flag = 1;
					printf("%d\n", i.X);
					break;
				}
			}
			for(int i = 0; i < k; ++i) { t[bus[i]] = 0; }
		} else { 
			for(auto &v : topo) { 
				for(auto &w : h[v]) { t[v] = max(t[v], t[w] + 1); }
			}

			if(t[u] != -OO) { 
				flag = 1;
				printf("%d\n", t[u]);
			}

			memset(t, 0, sizeof(t));
		}

		if(!flag) { printf("-1\n"); }
	}

	return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d%d%d", &n, &m, &q);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:40:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |                 scanf("%d%d", &u, &v);
      |                 ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:75:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |                 scanf("%d%d", &u, &k);
      |                 ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:77:51: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |                 for(int i = 0; i < k; ++i) { scanf("%d", bus + i); }
      |                                              ~~~~~^~~~~~~~~~~~~~~

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