oj.uz

Submission #46865

# Submission time Handle Problem Language Result Execution time Memory
46865 2018-04-24T07:24:27 Z kyleliu Bitaro’s Party (JOI18_bitaro) C++14
7 / 100
 2000 ms 12840 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 9 ms 7668 KB Output is correct
3 Correct 8 ms 7712 KB Output is correct
4 Correct 9 ms 7712 KB Output is correct
5 Correct 22 ms 9272 KB Output is correct
6 Correct 21 ms 9272 KB Output is correct
7 Correct 23 ms 9272 KB Output is correct
8 Correct 32 ms 9848 KB Output is correct
9 Correct 32 ms 9848 KB Output is correct
10 Correct 31 ms 9848 KB Output is correct
11 Correct 28 ms 9848 KB Output is correct
12 Correct 24 ms 9848 KB Output is correct
13 Correct 29 ms 9848 KB Output is correct
14 Correct 24 ms 9848 KB Output is correct
15 Correct 21 ms 9848 KB Output is correct
16 Correct 24 ms 9848 KB Output is correct
17 Correct 27 ms 9848 KB Output is correct
18 Correct 22 ms 9848 KB Output is correct
19 Correct 26 ms 9848 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 9 ms 7668 KB Output is correct
3 Correct 8 ms 7712 KB Output is correct
4 Correct 9 ms 7712 KB Output is correct
5 Correct 22 ms 9272 KB Output is correct
6 Correct 21 ms 9272 KB Output is correct
7 Correct 23 ms 9272 KB Output is correct
8 Correct 32 ms 9848 KB Output is correct
9 Correct 32 ms 9848 KB Output is correct
10 Correct 31 ms 9848 KB Output is correct
11 Correct 28 ms 9848 KB Output is correct
12 Correct 24 ms 9848 KB Output is correct
13 Correct 29 ms 9848 KB Output is correct
14 Correct 24 ms 9848 KB Output is correct
15 Correct 21 ms 9848 KB Output is correct
16 Correct 24 ms 9848 KB Output is correct
17 Correct 27 ms 9848 KB Output is correct
18 Correct 22 ms 9848 KB Output is correct
19 Correct 26 ms 9848 KB Output is correct
20 Execution timed out 2081 ms 12840 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 9 ms 7668 KB Output is correct
3 Correct 8 ms 7712 KB Output is correct
4 Correct 9 ms 7712 KB Output is correct
5 Correct 22 ms 9272 KB Output is correct
6 Correct 21 ms 9272 KB Output is correct
7 Correct 23 ms 9272 KB Output is correct
8 Correct 32 ms 9848 KB Output is correct
9 Correct 32 ms 9848 KB Output is correct
10 Correct 31 ms 9848 KB Output is correct
11 Correct 28 ms 9848 KB Output is correct
12 Correct 24 ms 9848 KB Output is correct
13 Correct 29 ms 9848 KB Output is correct
14 Correct 24 ms 9848 KB Output is correct
15 Correct 21 ms 9848 KB Output is correct
16 Correct 24 ms 9848 KB Output is correct
17 Correct 27 ms 9848 KB Output is correct
18 Correct 22 ms 9848 KB Output is correct
19 Correct 26 ms 9848 KB Output is correct
20 Execution timed out 2081 ms 12840 KB Time limit exceeded
21 Halted 0 ms 0 KB -