oj.uz

Submission #111739

# Submission time Handle Problem Language Result Execution time Memory
111739 2019-05-16T05:28:55 Z zscoder Bitaro’s Party (JOI18_bitaro) C++17
14 / 100
 2000 ms 217724 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;
 
const int C = 200;
 
vi adj[111111];
vi radj[111111];
vector<ii> dp[111111];
int n,m,q; 
bool isbad[111111];
 
void solve_large(int u)
{
	int ans = -1;
	vi innerdp(n+1,-1);
	innerdp[u] = 0;
	for(int i=u;i>=0;i--)
	{
		for(int v:adj[i])
		{
			if(innerdp[v]!=-1) innerdp[i] = max(innerdp[i], innerdp[v] + 1);
		}
		if(!isbad[i]) ans = max(ans, innerdp[i]);
	}
	cout<<ans<<'\n';
}
 
bool appeared[111111];
vector<ii> mergevector(vector<ii> &v1, vector<ii> &v2)
{
	vector<ii> V; vi A;
	int p1 = 0; int p2 = 0;
	while((p1<v1.size()||p2<v2.size())&&V.size()<C+3)
	{
		int val1 = -100000; int val2 = -100000;
		if(p1<v1.size()) val1 = v1[p1].fi;
		if(p2<v2.size()) val2 = v2[p2].fi+1;
		if(val1>val2)
		{
			V.pb(mp(val1, v1[p1].se));
			appeared[v1[p1].se]=1;A.pb(v1[p1].se);
			p1++;
		}
		else
		{
			V.pb(mp(val2, v2[p2].se));
			appeared[v2[p2].se]=1;A.pb(v2[p2].se);
			p2++;
		}
		while(p1<v1.size()&&appeared[v1[p1].se]) p1++;
		while(p2<v2.size()&&appeared[v2[p2].se]) p2++;
	}
	for(int x:A) appeared[x]=0;
	return V;
}
 
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m>>q;
	for(int i=0;i<m;i++)
	{
		int u, v; cin>>u>>v;u--;v--;
		adj[u].pb(v); radj[v].pb(u);
	}
	for(int i=0;i<n;i++)
	{
		dp[i].pb(mp(0,i));
		for(int v:radj[i])
		{
			dp[i] = mergevector(dp[i], dp[v]);
		}
		/*
		cerr<<"DP "<<i<<'\n';
		for(ii x:dp[i])
		{
			cerr<<x.fi<<' '<<x.se<<'\n';
		}
		*/
	}
	for(int i=0;i<q;i++)
	{
		int u; cin>>u; u--;
		int k; cin>>k; vi vec;
		for(int j=0;j<k;j++)
		{
			int v; cin>>v; v--; vec.pb(v);
		}
		for(int v:vec) isbad[v]=1;
		if(k>=C-1)
		{
			solve_large(u);
		}
		else
		{
			int ans = -1;
			for(ii x:dp[u])
			{
				if(isbad[x.se]) continue;
				ans = max(ans, x.fi);
			}
			cout<<ans<<'\n';
		}
		for(int v:vec) isbad[v]=0;
	}
}

Compilation message

bitaro.cpp: In function 'std::vector<std::pair<int, int> > mergevector(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
bitaro.cpp:52:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while((p1<v1.size()||p2<v2.size())&&V.size()<C+3)
         ~~^~~~~~~~~~
bitaro.cpp:52:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while((p1<v1.size()||p2<v2.size())&&V.size()<C+3)
                       ~~^~~~~~~~~~
bitaro.cpp:55:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(p1<v1.size()) val1 = v1[p1].fi;
      ~~^~~~~~~~~~
bitaro.cpp:56:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(p2<v2.size()) val2 = v2[p2].fi+1;
      ~~^~~~~~~~~~
bitaro.cpp:69:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p1<v1.size()&&appeared[v1[p1].se]) p1++;
         ~~^~~~~~~~~~
bitaro.cpp:70:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p2<v2.size()&&appeared[v2[p2].se]) p2++;
         ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8192 KB Output is correct
2 Correct 9 ms 8192 KB Output is correct
3 Correct 9 ms 8192 KB Output is correct
4 Correct 9 ms 8192 KB Output is correct
5 Correct 14 ms 8704 KB Output is correct
6 Correct 14 ms 8684 KB Output is correct
7 Correct 17 ms 8576 KB Output is correct
8 Correct 19 ms 10112 KB Output is correct
9 Correct 23 ms 10108 KB Output is correct
10 Correct 19 ms 10084 KB Output is correct
11 Correct 19 ms 9984 KB Output is correct
12 Correct 17 ms 9344 KB Output is correct
13 Correct 21 ms 9984 KB Output is correct
14 Correct 19 ms 9344 KB Output is correct
15 Correct 18 ms 8812 KB Output is correct
16 Correct 17 ms 9344 KB Output is correct
17 Correct 23 ms 9600 KB Output is correct
18 Correct 21 ms 9088 KB Output is correct
19 Correct 19 ms 9540 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8192 KB Output is correct
2 Correct 9 ms 8192 KB Output is correct
3 Correct 9 ms 8192 KB Output is correct
4 Correct 9 ms 8192 KB Output is correct
5 Correct 14 ms 8704 KB Output is correct
6 Correct 14 ms 8684 KB Output is correct
7 Correct 17 ms 8576 KB Output is correct
8 Correct 19 ms 10112 KB Output is correct
9 Correct 23 ms 10108 KB Output is correct
10 Correct 19 ms 10084 KB Output is correct
11 Correct 19 ms 9984 KB Output is correct
12 Correct 17 ms 9344 KB Output is correct
13 Correct 21 ms 9984 KB Output is correct
14 Correct 19 ms 9344 KB Output is correct
15 Correct 18 ms 8812 KB Output is correct
16 Correct 17 ms 9344 KB Output is correct
17 Correct 23 ms 9600 KB Output is correct
18 Correct 21 ms 9088 KB Output is correct
19 Correct 19 ms 9540 KB Output is correct
20 Correct 976 ms 12496 KB Output is correct
21 Correct 898 ms 12408 KB Output is correct
22 Correct 951 ms 12460 KB Output is correct
23 Correct 792 ms 12484 KB Output is correct
24 Correct 1251 ms 156964 KB Output is correct
25 Correct 1279 ms 161036 KB Output is correct
26 Correct 1072 ms 161248 KB Output is correct
27 Correct 1351 ms 217596 KB Output is correct
28 Correct 1247 ms 217724 KB Output is correct
29 Correct 1348 ms 217524 KB Output is correct
30 Correct 1149 ms 216816 KB Output is correct
31 Correct 1183 ms 211492 KB Output is correct
32 Correct 1253 ms 216680 KB Output is correct
33 Correct 1014 ms 139380 KB Output is correct
34 Correct 915 ms 120684 KB Output is correct
35 Correct 1020 ms 138328 KB Output is correct
36 Correct 1176 ms 178468 KB Output is correct
37 Correct 1143 ms 166324 KB Output is correct
38 Correct 1201 ms 179008 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8192 KB Output is correct
2 Correct 9 ms 8192 KB Output is correct
3 Correct 9 ms 8192 KB Output is correct
4 Correct 9 ms 8192 KB Output is correct
5 Correct 14 ms 8704 KB Output is correct
6 Correct 14 ms 8684 KB Output is correct
7 Correct 17 ms 8576 KB Output is correct
8 Correct 19 ms 10112 KB Output is correct
9 Correct 23 ms 10108 KB Output is correct
10 Correct 19 ms 10084 KB Output is correct
11 Correct 19 ms 9984 KB Output is correct
12 Correct 17 ms 9344 KB Output is correct
13 Correct 21 ms 9984 KB Output is correct
14 Correct 19 ms 9344 KB Output is correct
15 Correct 18 ms 8812 KB Output is correct
16 Correct 17 ms 9344 KB Output is correct
17 Correct 23 ms 9600 KB Output is correct
18 Correct 21 ms 9088 KB Output is correct
19 Correct 19 ms 9540 KB Output is correct
20 Correct 976 ms 12496 KB Output is correct
21 Correct 898 ms 12408 KB Output is correct
22 Correct 951 ms 12460 KB Output is correct
23 Correct 792 ms 12484 KB Output is correct
24 Correct 1251 ms 156964 KB Output is correct
25 Correct 1279 ms 161036 KB Output is correct
26 Correct 1072 ms 161248 KB Output is correct
27 Correct 1351 ms 217596 KB Output is correct
28 Correct 1247 ms 217724 KB Output is correct
29 Correct 1348 ms 217524 KB Output is correct
30 Correct 1149 ms 216816 KB Output is correct
31 Correct 1183 ms 211492 KB Output is correct
32 Correct 1253 ms 216680 KB Output is correct
33 Correct 1014 ms 139380 KB Output is correct
34 Correct 915 ms 120684 KB Output is correct
35 Correct 1020 ms 138328 KB Output is correct
36 Correct 1176 ms 178468 KB Output is correct
37 Correct 1143 ms 166324 KB Output is correct
38 Correct 1201 ms 179008 KB Output is correct
39 Correct 1432 ms 157672 KB Output is correct
40 Correct 1402 ms 158576 KB Output is correct
41 Correct 1331 ms 159096 KB Output is correct
42 Correct 1418 ms 159736 KB Output is correct
43 Correct 1105 ms 158588 KB Output is correct
44 Correct 984 ms 12920 KB Output is correct
45 Correct 934 ms 12408 KB Output is correct
46 Correct 823 ms 12664 KB Output is correct
47 Correct 854 ms 12484 KB Output is correct
48 Correct 788 ms 12364 KB Output is correct
49 Correct 1486 ms 217336 KB Output is correct
50 Correct 1390 ms 216612 KB Output is correct
51 Correct 938 ms 12920 KB Output is correct
52 Correct 972 ms 12388 KB Output is correct
53 Correct 1508 ms 177792 KB Output is correct
54 Correct 1433 ms 165880 KB Output is correct
55 Correct 1269 ms 177232 KB Output is correct
56 Correct 1283 ms 166136 KB Output is correct
57 Correct 956 ms 12896 KB Output is correct
58 Correct 1117 ms 12792 KB Output is correct
59 Correct 897 ms 12708 KB Output is correct
60 Correct 886 ms 12536 KB Output is correct
61 Correct 1558 ms 217128 KB Output is correct
62 Correct 1379 ms 178640 KB Output is correct
63 Correct 1244 ms 165384 KB Output is correct
64 Execution timed out 2055 ms 217328 KB Time limit exceeded
65 Halted 0 ms 0 KB -