oj.uz

Submission #93600

# Submission time Handle Problem Language Result Execution time Memory
93600 2019-01-10T01:48:58 Z silxikys Bitaro’s Party (JOI18_bitaro) C++14
7 / 100
 2000 ms 14204 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) begin(x),end(x)

const int maxn = 1e5+5, INF = 987654321;
int N, M, Q;
vector<int> ancestors[maxn];
int SZ;
list<pair<int,int>> bests[maxn];
auto cmp = [](const pair<int,int>& a, const pair<int,int>& b) { return a.first > b.first; };

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> M >> Q;
    for (int i = 0; i < M; i++) {
    	int s, e; cin >> s >> e;
    	ancestors[e].push_back(s);
    }
    SZ = 350; //each node will store at least the top SZ nodes
    //small queries are <= SZ - 1
    vector<bool> used(N+1,false);
    for (int i = 1; i <= N; i++) {
    	list<pair<int,int>>& li = bests[i];
    	li.push_back({0,i});
    	for (int j: ancestors[i]) {
    		list<pair<int,int>> add;
    		for (auto p: bests[j]) {
    			add.push_back({p.first+1,p.second});
    			if (add.size() >= SZ) break;
    		}
    		li.merge(add,cmp);
    	}
    	li.unique();
    	for (auto it = li.begin(); it != li.end();) {
    		if (used[it->second]) it = li.erase(it);
    		else { used[it->second] = true;	++it; }
    	}
    	for (auto& p: li) used[p.second] = false; //reset for next one
    	/*
    	cout << i << ": \n";
    	for (auto p: li) {
    		cout << p.first << ' ' << p.second << '\n';
    	}
    	cout << '\n';
    	*/
    }

	vector<bool> isBusy(N+1,false);
	while (Q--) {
		int town, num; cin >> town >> num;
		vector<int> busy(num);
		for (int i = 0; i < num; i++) {
			cin >> busy[i];
			isBusy[busy[i]] = true;
		}
		if (num <= SZ - 1) {
			//answer will be in first SZ answers, if it exists
			bool found = false;
			for (auto& p: bests[town]) {
				if (!isBusy[p.second]) {
					found = true;
					cout << p.first << '\n';
					break;
				}
			}
			if (!found) {
				cout << -1 << '\n';
			}
		}
		else {
			//do normal O(N) DP
			//this only happens about sqrt(N) times
			vector<int> dp(N+1,-INF);
			for (int i = 1; i <= town; i++) {
				if (!isBusy[i]) dp[i] = 0;
				for (int j: ancestors[i]) {
					dp[i] = max(dp[i],dp[j]+1);
				}
			}
			int ans = dp[town] >= 0 ? dp[town] : -1;
			cout << ans << '\n';
		}
		//reset isBusy[] for next query
		for (int i: busy) isBusy[i] = false;
	}
    return 0;
}

Compilation message

bitaro.cpp: In function 'int main()':
bitaro.cpp:31:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        if (add.size() >= SZ) break;
            ~~~~~~~~~~~^~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 4984 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 5 ms 4984 KB Output is correct
5 Correct 9 ms 6264 KB Output is correct
6 Correct 9 ms 6264 KB Output is correct
7 Correct 8 ms 6136 KB Output is correct
8 Correct 34 ms 14200 KB Output is correct
9 Correct 35 ms 14204 KB Output is correct
10 Correct 34 ms 14072 KB Output is correct
11 Correct 31 ms 13048 KB Output is correct
12 Correct 15 ms 8568 KB Output is correct
13 Correct 39 ms 12664 KB Output is correct
14 Correct 27 ms 10488 KB Output is correct
15 Correct 18 ms 8312 KB Output is correct
16 Correct 26 ms 10488 KB Output is correct
17 Correct 27 ms 11000 KB Output is correct
18 Correct 16 ms 8496 KB Output is correct
19 Correct 24 ms 11128 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 4984 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 5 ms 4984 KB Output is correct
5 Correct 9 ms 6264 KB Output is correct
6 Correct 9 ms 6264 KB Output is correct
7 Correct 8 ms 6136 KB Output is correct
8 Correct 34 ms 14200 KB Output is correct
9 Correct 35 ms 14204 KB Output is correct
10 Correct 34 ms 14072 KB Output is correct
11 Correct 31 ms 13048 KB Output is correct
12 Correct 15 ms 8568 KB Output is correct
13 Correct 39 ms 12664 KB Output is correct
14 Correct 27 ms 10488 KB Output is correct
15 Correct 18 ms 8312 KB Output is correct
16 Correct 26 ms 10488 KB Output is correct
17 Correct 27 ms 11000 KB Output is correct
18 Correct 16 ms 8496 KB Output is correct
19 Correct 24 ms 11128 KB Output is correct
20 Execution timed out 2052 ms 7736 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 4984 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 5 ms 4984 KB Output is correct
5 Correct 9 ms 6264 KB Output is correct
6 Correct 9 ms 6264 KB Output is correct
7 Correct 8 ms 6136 KB Output is correct
8 Correct 34 ms 14200 KB Output is correct
9 Correct 35 ms 14204 KB Output is correct
10 Correct 34 ms 14072 KB Output is correct
11 Correct 31 ms 13048 KB Output is correct
12 Correct 15 ms 8568 KB Output is correct
13 Correct 39 ms 12664 KB Output is correct
14 Correct 27 ms 10488 KB Output is correct
15 Correct 18 ms 8312 KB Output is correct
16 Correct 26 ms 10488 KB Output is correct
17 Correct 27 ms 11000 KB Output is correct
18 Correct 16 ms 8496 KB Output is correct
19 Correct 24 ms 11128 KB Output is correct
20 Execution timed out 2052 ms 7736 KB Time limit exceeded
21 Halted 0 ms 0 KB -