oj.uz

Submission #93601

# Submission time Handle Problem Language Result Execution time Memory
93601 2019-01-10T01:49:54 Z silxikys Bitaro’s Party (JOI18_bitaro) C++14
7 / 100
 2000 ms 7132 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 = sqrt(N) + 2; //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 4988 KB Output is correct
3 Correct 5 ms 4984 KB Output is correct
4 Correct 5 ms 4984 KB Output is correct
5 Correct 8 ms 5880 KB Output is correct
6 Correct 8 ms 5880 KB Output is correct
7 Correct 8 ms 5880 KB Output is correct
8 Correct 9 ms 6136 KB Output is correct
9 Correct 9 ms 6136 KB Output is correct
10 Correct 9 ms 6136 KB Output is correct
11 Correct 9 ms 6136 KB Output is correct
12 Correct 9 ms 6136 KB Output is correct
13 Correct 9 ms 6136 KB Output is correct
14 Correct 8 ms 5880 KB Output is correct
15 Correct 8 ms 5876 KB Output is correct
16 Correct 9 ms 5868 KB Output is correct
17 Correct 8 ms 6008 KB Output is correct
18 Correct 8 ms 5880 KB Output is correct
19 Correct 8 ms 5900 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 4988 KB Output is correct
3 Correct 5 ms 4984 KB Output is correct
4 Correct 5 ms 4984 KB Output is correct
5 Correct 8 ms 5880 KB Output is correct
6 Correct 8 ms 5880 KB Output is correct
7 Correct 8 ms 5880 KB Output is correct
8 Correct 9 ms 6136 KB Output is correct
9 Correct 9 ms 6136 KB Output is correct
10 Correct 9 ms 6136 KB Output is correct
11 Correct 9 ms 6136 KB Output is correct
12 Correct 9 ms 6136 KB Output is correct
13 Correct 9 ms 6136 KB Output is correct
14 Correct 8 ms 5880 KB Output is correct
15 Correct 8 ms 5876 KB Output is correct
16 Correct 9 ms 5868 KB Output is correct
17 Correct 8 ms 6008 KB Output is correct
18 Correct 8 ms 5880 KB Output is correct
19 Correct 8 ms 5900 KB Output is correct
20 Execution timed out 2072 ms 7132 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 4988 KB Output is correct
3 Correct 5 ms 4984 KB Output is correct
4 Correct 5 ms 4984 KB Output is correct
5 Correct 8 ms 5880 KB Output is correct
6 Correct 8 ms 5880 KB Output is correct
7 Correct 8 ms 5880 KB Output is correct
8 Correct 9 ms 6136 KB Output is correct
9 Correct 9 ms 6136 KB Output is correct
10 Correct 9 ms 6136 KB Output is correct
11 Correct 9 ms 6136 KB Output is correct
12 Correct 9 ms 6136 KB Output is correct
13 Correct 9 ms 6136 KB Output is correct
14 Correct 8 ms 5880 KB Output is correct
15 Correct 8 ms 5876 KB Output is correct
16 Correct 9 ms 5868 KB Output is correct
17 Correct 8 ms 6008 KB Output is correct
18 Correct 8 ms 5880 KB Output is correct
19 Correct 8 ms 5900 KB Output is correct
20 Execution timed out 2072 ms 7132 KB Time limit exceeded
21 Halted 0 ms 0 KB -