Submission #46865

#	Time	Username	Problem	Language	Result	Execution time	Memory
46865		kyleliu	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2081 ms	12840 KiB

bitaro

#include <bits/stdc++.h> // PLEASE

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pp;
#define MAXN 100005
#define MAXM 1005
#define MAXP 25
#define A first
#define B second
#define MP make_pair
#define PB push_back
const ll INF = 2e9+13;
const ll MOD = 1e9+7;
const int K = 200;

int N, M, Q;
vector <pp> farth[MAXN];
vector <int> f[MAXN];
vector <int> g[MAXN];
int in[MAXN];
int dp[MAXN];
bool can[MAXN];
bool vis[MAXN];
void solve() {
	queue <int> q;
	memset(vis, 0, sizeof(vis));
	for(int i=1; i<=N; i++) {
		dp[i] = -1;
		if(in[i] == 0) {
			q.push(i);
			if(can[i]) dp[i] = 0;
		}
	}
	while(!q.empty()) {
		int u = q.front(); q.pop();
		if(can[u]) dp[u] = max(dp[u], 0);
		if(vis[u]) continue; vis[u] = 1;
		for(auto v : g[u]) {
			if(dp[u] >= 0) dp[v] = max(dp[v], dp[u] + 1);
			in[v]--;
			if(in[v] == 0) q.push(v);
		}
	}  
	for(int i=1; i<=N; i++) for(auto v : g[i]) in[v]++;
} 

bool cmp(pp a, pp b)
{
	return a.A > b.A;
}

void pre()
{
	queue <int> q;
	memset(vis, 0, sizeof(vis));
	for(int i=1; i<=N; i++) {
		if(in[i] == 0) {
			q.push(i);
			farth[i].PB({0, i});
		}
	}
	while(!q.empty()) {
		int u = q.front(); q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(auto v : g[u]) {
			in[v]--; if(in[v] == 0) if(!vis[v]) q.push(v);
		}
		// merge it
		vector <pp> ret;
		ret.PB({0, u});
		for(auto v : f[u]) for(auto e : farth[v]) ret.PB({e.A+1, e.B});
		sort(ret.begin(), ret.end(), cmp);
		for(int i=0; i<min(K, (int)ret.size()); i++) farth[u].PB(ret[i]);
	}
	for(int i=1; i<=N; i++) for(auto v : g[i]) in[v]++;
}
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M >> Q;
	for(int i=1; i<=N; i++) can[i] = 1;
	for(int i=0; i<M; i++) {
		int a, b; cin >> a >> b;
		g[a].PB(b); in[b]++;
		f[b].PB(a);
	}
	pre();
	while(Q--) {
		int t, n;
		cin >> t >> n;
		if(n > K) {
			vector <int> v;
			for(int i=1; i<=n; i++) { int x; cin >> x; v.PB(x); }
			for(auto x : v) can[x] = 0;
			solve();
			cout << dp[t] << endl;
			for(auto x : v) can[x] = 1;
		}
		else {
			vector <int> v;
			for(int i=1; i<=n; i++) { int x; cin >> x; v.PB(x); }
			for(auto x : v) can[x] = 0;
			bool printed = 0;
			//cout << "TARG " << t << endl;
			for(auto x : farth[t]) {
			//	cout << "DIST " << x.A << " NODE " << x.B << endl;
				if(can[x.B]) {
					cout << x.A << endl;
					printed = 1; break;
				}
			}
			if(!printed) cout << -1 << endl;
			for(auto x : v) can[x] = 1;
		}
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'void solve()':
bitaro.cpp:39:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if(vis[u]) continue; vis[u] = 1;
   ^~
bitaro.cpp:39:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   if(vis[u]) continue; vis[u] = 1;
                        ^~~

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