oj.uz

Submission #90472

# Submission time Handle Problem Language Result Execution time Memory
90472 2018-12-21T19:21:19 Z radoslav11 Bitaro’s Party (JOI18_bitaro) C++14
14 / 100
 2000 ms 317492 KB 
#include <bits/stdc++.h>
#define endl '\n'
 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace std;
template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
const int MAXN = (int)1e5 + 17 + 42;
const int B = 100;
 
int n, m, q;
vector<int> adj[MAXN];
 
void read()
{
	cin >> n >> m >> q;
	for(int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		adj[v].push_back(u);
	}
}
 
bool ok[MAXN];
 
int _dp[MAXN];
int Tm_vis[MAXN], cnt_t;
int TMS = 0;
 
vector<pair<int, int> > dp[MAXN];
 
int rec(int u)
{
	if(Tm_vis[u] >= cnt_t) return _dp[u];
	Tm_vis[u] = cnt_t;
	if(ok[u]) _dp[u] = 0;
	else _dp[u] = -1e9;
 
	for(int v: adj[u])
		chkmax(_dp[u], rec(v) + 1);
 
	return _dp[u];
}
 
int solve_brute(int u, vector<int> blocked)
{
	for(int x: blocked) ok[x] = 0;
	cnt_t++;
	int ans = rec(u);
	for(int x: blocked) ok[x] = 1;
	return ans < 0 ? -1 : ans;
}
 
bool same[MAXN];
 
bool cmp(pair<int, int> a, pair<int, int> b) { return a.second > b.second; }
 
void solve()
{
	for(int i = 1; i <= n; i++) ok[i] = 1;
 
	for(int u = 1; u <= n; u++)
	{
		dp[u].push_back({u, 0});
		for(auto v: adj[u])
			for(auto it: dp[v])
				dp[u].push_back({it.first, it.second + 1});
 
		sort(dp[u].begin(), dp[u].end());
		vector<pair<int, int> > rl;
	
		for(auto it: dp[u])
			if(rl.empty() || rl.back().first != it.first) rl.push_back(it);
			else rl[rl.size() - 1].second = it.second;
	
		if(rl.size() > B)
        {
         	sort(rl.begin(), rl.end(), cmp);
			while((int)rl.size() > B) rl.pop_back();	
        }
        
      dp[u] = rl;
	}
	while(q--)
	{
		int st, sz;
		vector<int> li;
	
		cin >> st >> sz;
		bool has_large = 0;
		for(int i = 0; i < sz; i++)
		{
			int x;
			cin >> x;
			li.push_back(x);
        }
 
		vector<int> initial_li = li;
 
		if(li.size() >= B)
		{
			cout << solve_brute(st, li) << endl;
			continue;
		}
 
		for(auto it: li) same[it] = 1;
 
		int answer = 0;
		for(auto it: dp[st])
			if(!same[it.first])
				chkmax(answer, it.second);
 
		for(auto it: li) same[it] = 0;
 
		if(answer < 0) answer = -1;
		if(answer == 0)
		{
			for(auto it: initial_li)
				if(it == st) answer = -1;
		}
		
		cout << answer << endl;
	}
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	read();
	solve();
	return 0;
}

Compilation message

bitaro.cpp: In function 'void solve()':
bitaro.cpp:93:8: warning: unused variable 'has_large' [-Wunused-variable]
   bool has_large = 0;
        ^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5228 KB Output is correct
3 Correct 6 ms 5228 KB Output is correct
4 Correct 5 ms 5228 KB Output is correct
5 Correct 11 ms 5848 KB Output is correct
6 Correct 12 ms 5848 KB Output is correct
7 Correct 10 ms 5848 KB Output is correct
8 Correct 19 ms 7444 KB Output is correct
9 Correct 19 ms 7444 KB Output is correct
10 Correct 19 ms 7444 KB Output is correct
11 Correct 19 ms 7444 KB Output is correct
12 Correct 16 ms 7444 KB Output is correct
13 Correct 20 ms 7444 KB Output is correct
14 Correct 16 ms 7444 KB Output is correct
15 Correct 14 ms 7444 KB Output is correct
16 Correct 17 ms 7444 KB Output is correct
17 Correct 19 ms 7444 KB Output is correct
18 Correct 15 ms 7444 KB Output is correct
19 Correct 17 ms 7444 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5228 KB Output is correct
3 Correct 6 ms 5228 KB Output is correct
4 Correct 5 ms 5228 KB Output is correct
5 Correct 11 ms 5848 KB Output is correct
6 Correct 12 ms 5848 KB Output is correct
7 Correct 10 ms 5848 KB Output is correct
8 Correct 19 ms 7444 KB Output is correct
9 Correct 19 ms 7444 KB Output is correct
10 Correct 19 ms 7444 KB Output is correct
11 Correct 19 ms 7444 KB Output is correct
12 Correct 16 ms 7444 KB Output is correct
13 Correct 20 ms 7444 KB Output is correct
14 Correct 16 ms 7444 KB Output is correct
15 Correct 14 ms 7444 KB Output is correct
16 Correct 17 ms 7444 KB Output is correct
17 Correct 19 ms 7444 KB Output is correct
18 Correct 15 ms 7444 KB Output is correct
19 Correct 17 ms 7444 KB Output is correct
20 Correct 1608 ms 148268 KB Output is correct
21 Correct 1621 ms 149820 KB Output is correct
22 Correct 1583 ms 151356 KB Output is correct
23 Correct 1787 ms 162120 KB Output is correct
24 Correct 1707 ms 176592 KB Output is correct
25 Correct 1672 ms 185920 KB Output is correct
26 Correct 1702 ms 187684 KB Output is correct
27 Correct 1405 ms 256728 KB Output is correct
28 Correct 1399 ms 259764 KB Output is correct
29 Correct 1436 ms 263240 KB Output is correct
30 Correct 1498 ms 263240 KB Output is correct
31 Correct 1914 ms 263240 KB Output is correct
32 Correct 1545 ms 267632 KB Output is correct
33 Correct 1246 ms 267632 KB Output is correct
34 Correct 1288 ms 267632 KB Output is correct
35 Correct 1164 ms 267632 KB Output is correct
36 Correct 1445 ms 267632 KB Output is correct
37 Correct 1662 ms 267632 KB Output is correct
38 Correct 1512 ms 267632 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5228 KB Output is correct
3 Correct 6 ms 5228 KB Output is correct
4 Correct 5 ms 5228 KB Output is correct
5 Correct 11 ms 5848 KB Output is correct
6 Correct 12 ms 5848 KB Output is correct
7 Correct 10 ms 5848 KB Output is correct
8 Correct 19 ms 7444 KB Output is correct
9 Correct 19 ms 7444 KB Output is correct
10 Correct 19 ms 7444 KB Output is correct
11 Correct 19 ms 7444 KB Output is correct
12 Correct 16 ms 7444 KB Output is correct
13 Correct 20 ms 7444 KB Output is correct
14 Correct 16 ms 7444 KB Output is correct
15 Correct 14 ms 7444 KB Output is correct
16 Correct 17 ms 7444 KB Output is correct
17 Correct 19 ms 7444 KB Output is correct
18 Correct 15 ms 7444 KB Output is correct
19 Correct 17 ms 7444 KB Output is correct
20 Correct 1608 ms 148268 KB Output is correct
21 Correct 1621 ms 149820 KB Output is correct
22 Correct 1583 ms 151356 KB Output is correct
23 Correct 1787 ms 162120 KB Output is correct
24 Correct 1707 ms 176592 KB Output is correct
25 Correct 1672 ms 185920 KB Output is correct
26 Correct 1702 ms 187684 KB Output is correct
27 Correct 1405 ms 256728 KB Output is correct
28 Correct 1399 ms 259764 KB Output is correct
29 Correct 1436 ms 263240 KB Output is correct
30 Correct 1498 ms 263240 KB Output is correct
31 Correct 1914 ms 263240 KB Output is correct
32 Correct 1545 ms 267632 KB Output is correct
33 Correct 1246 ms 267632 KB Output is correct
34 Correct 1288 ms 267632 KB Output is correct
35 Correct 1164 ms 267632 KB Output is correct
36 Correct 1445 ms 267632 KB Output is correct
37 Correct 1662 ms 267632 KB Output is correct
38 Correct 1512 ms 267632 KB Output is correct
39 Correct 1856 ms 267632 KB Output is correct
40 Correct 1788 ms 267632 KB Output is correct
41 Correct 1835 ms 267632 KB Output is correct
42 Correct 1764 ms 267632 KB Output is correct
43 Correct 1723 ms 267632 KB Output is correct
44 Correct 1707 ms 267632 KB Output is correct
45 Correct 1675 ms 267632 KB Output is correct
46 Correct 1807 ms 267632 KB Output is correct
47 Correct 1624 ms 267632 KB Output is correct
48 Correct 1573 ms 267632 KB Output is correct
49 Correct 1673 ms 311456 KB Output is correct
50 Execution timed out 2048 ms 317492 KB Time limit exceeded
51 Halted 0 ms 0 KB -