oj.uz

Submission #236163

# Submission time Handle Problem Language Result Execution time Memory
236163 2020-05-31T10:29:50 Z MvC Bitaro’s Party (JOI18_bitaro) C++11
100 / 100
 1065 ms 112940 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e5+50;
const ll mod=1e9+7;
const int c=100;
using namespace std;
int n,m,q,x,y,i,j,nr,f[nmax],d[nmax],v[nmax],id[nmax],a[nmax],t;
vector<pair<int,int> >vc[nmax];
vector<int>g[nmax],cl;
pair<int,int>mx;
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>m>>q;
	while(m--)
	{
		cin>>x>>y;
		g[y].pb(x);
	}
	for(i=1;i<=n;i++)
	{
		for(j=0;j<(int)g[i].size();j++)
		{
			x=g[i][j];
			f[i]=max(f[i],f[x]+1);
		}
		d[i]=f[i];
	}
	for(i=1;i<=n;i++)
	{
		for(j=0;j<(int)g[i].size();j++)id[g[i][j]]=0;
		nr=(int)g[i].size();
		for(t=0;t<c;t++)
		{
			mx=mkp(0,0);
			for(j=0;j<(int)g[i].size();j++)
			{
				x=g[i][j];
				if(id[x]==(int)vc[x].size())continue;
				while(id[x]<(int)vc[x].size() && v[vc[x][id[x]].sc])id[x]++;
				if(id[x]<(int)vc[x].size())mx=max(mx,vc[x][id[x]]);
				else nr--;
			}
			if(mx.sc)
			{
				vc[i].pb(mkp(mx.fr+1,mx.sc));
				v[mx.sc]=1;
				cl.pb(mx.sc);
			}
			else break;
			//if(!nr)break;
		}
		if((int)vc[i].size()<c)vc[i].pb(mkp(0,i));
		for(j=0;j<(int)cl.size();j++)v[cl[j]]=0;
		cl.clear();
	}
	while(q--)
	{
		cin>>x>>nr;
		for(i=1;i<=nr;i++)
		{
			cin>>a[i];
			v[a[i]]=1;
		}
		if(nr>=c)
		{
			for(i=a[1];i<=x;i++)
			{
				if(v[i])d[i]=-1;
				else d[i]=0;
				for(j=0;j<(int)g[i].size();j++)
				{
					y=g[i][j];
					if(d[y]==-1)continue;
					d[i]=max(d[i],d[y]+1);
				}
			}
			cout<<d[x]<<'\n';
			for(i=a[1];i<=x;i++)d[i]=f[i];
		}
		else
		{
			mx=mkp(-1,-1);
			for(i=0;i<(int)vc[x].size();i++)
			{
				if(!v[vc[x][i].sc])
				{
					mx=vc[x][i];
					break;
				}
			}
			cout<<mx.fr<<'\n';
		}
		for(i=1;i<=nr;i++)v[a[i]]=0;
	}
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 9 ms 5120 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 12 ms 5504 KB Output is correct
6 Correct 12 ms 5632 KB Output is correct
7 Correct 11 ms 5504 KB Output is correct
8 Correct 12 ms 6144 KB Output is correct
9 Correct 12 ms 6016 KB Output is correct
10 Correct 14 ms 6144 KB Output is correct
11 Correct 15 ms 6016 KB Output is correct
12 Correct 12 ms 5888 KB Output is correct
13 Correct 12 ms 6016 KB Output is correct
14 Correct 11 ms 5632 KB Output is correct
15 Correct 11 ms 5504 KB Output is correct
16 Correct 11 ms 5792 KB Output is correct
17 Correct 15 ms 5888 KB Output is correct
18 Correct 14 ms 5632 KB Output is correct
19 Correct 12 ms 5888 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 9 ms 5120 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 12 ms 5504 KB Output is correct
6 Correct 12 ms 5632 KB Output is correct
7 Correct 11 ms 5504 KB Output is correct
8 Correct 12 ms 6144 KB Output is correct
9 Correct 12 ms 6016 KB Output is correct
10 Correct 14 ms 6144 KB Output is correct
11 Correct 15 ms 6016 KB Output is correct
12 Correct 12 ms 5888 KB Output is correct
13 Correct 12 ms 6016 KB Output is correct
14 Correct 11 ms 5632 KB Output is correct
15 Correct 11 ms 5504 KB Output is correct
16 Correct 11 ms 5792 KB Output is correct
17 Correct 15 ms 5888 KB Output is correct
18 Correct 14 ms 5632 KB Output is correct
19 Correct 12 ms 5888 KB Output is correct
20 Correct 203 ms 7288 KB Output is correct
21 Correct 188 ms 7160 KB Output is correct
22 Correct 201 ms 7288 KB Output is correct
23 Correct 189 ms 7288 KB Output is correct
24 Correct 576 ms 87168 KB Output is correct
25 Correct 614 ms 88544 KB Output is correct
26 Correct 590 ms 88432 KB Output is correct
27 Correct 561 ms 111804 KB Output is correct
28 Correct 552 ms 111784 KB Output is correct
29 Correct 533 ms 111608 KB Output is correct
30 Correct 537 ms 111684 KB Output is correct
31 Correct 623 ms 109744 KB Output is correct
32 Correct 543 ms 111592 KB Output is correct
33 Correct 439 ms 73728 KB Output is correct
34 Correct 407 ms 66476 KB Output is correct
35 Correct 430 ms 73312 KB Output is correct
36 Correct 527 ms 92536 KB Output is correct
37 Correct 640 ms 87932 KB Output is correct
38 Correct 505 ms 92664 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 9 ms 5120 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 12 ms 5504 KB Output is correct
6 Correct 12 ms 5632 KB Output is correct
7 Correct 11 ms 5504 KB Output is correct
8 Correct 12 ms 6144 KB Output is correct
9 Correct 12 ms 6016 KB Output is correct
10 Correct 14 ms 6144 KB Output is correct
11 Correct 15 ms 6016 KB Output is correct
12 Correct 12 ms 5888 KB Output is correct
13 Correct 12 ms 6016 KB Output is correct
14 Correct 11 ms 5632 KB Output is correct
15 Correct 11 ms 5504 KB Output is correct
16 Correct 11 ms 5792 KB Output is correct
17 Correct 15 ms 5888 KB Output is correct
18 Correct 14 ms 5632 KB Output is correct
19 Correct 12 ms 5888 KB Output is correct
20 Correct 203 ms 7288 KB Output is correct
21 Correct 188 ms 7160 KB Output is correct
22 Correct 201 ms 7288 KB Output is correct
23 Correct 189 ms 7288 KB Output is correct
24 Correct 576 ms 87168 KB Output is correct
25 Correct 614 ms 88544 KB Output is correct
26 Correct 590 ms 88432 KB Output is correct
27 Correct 561 ms 111804 KB Output is correct
28 Correct 552 ms 111784 KB Output is correct
29 Correct 533 ms 111608 KB Output is correct
30 Correct 537 ms 111684 KB Output is correct
31 Correct 623 ms 109744 KB Output is correct
32 Correct 543 ms 111592 KB Output is correct
33 Correct 439 ms 73728 KB Output is correct
34 Correct 407 ms 66476 KB Output is correct
35 Correct 430 ms 73312 KB Output is correct
36 Correct 527 ms 92536 KB Output is correct
37 Correct 640 ms 87932 KB Output is correct
38 Correct 505 ms 92664 KB Output is correct
39 Correct 638 ms 87592 KB Output is correct
40 Correct 594 ms 88048 KB Output is correct
41 Correct 1022 ms 88152 KB Output is correct
42 Correct 660 ms 88092 KB Output is correct
43 Correct 579 ms 87520 KB Output is correct
44 Correct 233 ms 7544 KB Output is correct
45 Correct 214 ms 7160 KB Output is correct
46 Correct 367 ms 7200 KB Output is correct
47 Correct 235 ms 7164 KB Output is correct
48 Correct 189 ms 7204 KB Output is correct
49 Correct 591 ms 111840 KB Output is correct
50 Correct 1048 ms 111328 KB Output is correct
51 Correct 211 ms 7544 KB Output is correct
52 Correct 407 ms 7332 KB Output is correct
53 Correct 558 ms 92452 KB Output is correct
54 Correct 594 ms 88120 KB Output is correct
55 Correct 986 ms 92152 KB Output is correct
56 Correct 980 ms 88192 KB Output is correct
57 Correct 239 ms 7672 KB Output is correct
58 Correct 236 ms 7684 KB Output is correct
59 Correct 417 ms 7264 KB Output is correct
60 Correct 398 ms 7408 KB Output is correct
61 Correct 637 ms 111172 KB Output is correct
62 Correct 597 ms 92408 KB Output is correct
63 Correct 619 ms 87404 KB Output is correct
64 Correct 830 ms 111176 KB Output is correct
65 Correct 778 ms 92060 KB Output is correct
66 Correct 825 ms 88060 KB Output is correct
67 Correct 937 ms 111268 KB Output is correct
68 Correct 933 ms 92640 KB Output is correct
69 Correct 987 ms 87056 KB Output is correct
70 Correct 550 ms 111288 KB Output is correct
71 Correct 501 ms 92536 KB Output is correct
72 Correct 551 ms 87648 KB Output is correct
73 Correct 621 ms 111608 KB Output is correct
74 Correct 566 ms 92352 KB Output is correct
75 Correct 604 ms 87672 KB Output is correct
76 Correct 655 ms 112156 KB Output is correct
77 Correct 956 ms 112516 KB Output is correct
78 Correct 546 ms 112376 KB Output is correct
79 Correct 223 ms 8316 KB Output is correct
80 Correct 357 ms 8056 KB Output is correct
81 Correct 204 ms 7928 KB Output is correct
82 Correct 631 ms 112940 KB Output is correct
83 Correct 652 ms 110744 KB Output is correct
84 Correct 973 ms 112376 KB Output is correct
85 Correct 1032 ms 110304 KB Output is correct
86 Correct 534 ms 112352 KB Output is correct
87 Correct 645 ms 110944 KB Output is correct
88 Correct 222 ms 8568 KB Output is correct
89 Correct 241 ms 8544 KB Output is correct
90 Correct 358 ms 8184 KB Output is correct
91 Correct 364 ms 8188 KB Output is correct
92 Correct 191 ms 8160 KB Output is correct
93 Correct 214 ms 8184 KB Output is correct
94 Correct 491 ms 74968 KB Output is correct
95 Correct 491 ms 67424 KB Output is correct
96 Correct 768 ms 74232 KB Output is correct
97 Correct 749 ms 68088 KB Output is correct
98 Correct 457 ms 74616 KB Output is correct
99 Correct 449 ms 67832 KB Output is correct
100 Correct 217 ms 8568 KB Output is correct
101 Correct 225 ms 8544 KB Output is correct
102 Correct 390 ms 8280 KB Output is correct
103 Correct 305 ms 8184 KB Output is correct
104 Correct 196 ms 8156 KB Output is correct
105 Correct 205 ms 8184 KB Output is correct
106 Correct 594 ms 93688 KB Output is correct
107 Correct 615 ms 89208 KB Output is correct
108 Correct 1065 ms 93708 KB Output is correct
109 Correct 963 ms 88856 KB Output is correct
110 Correct 534 ms 93736 KB Output is correct
111 Correct 563 ms 89080 KB Output is correct
112 Correct 265 ms 8824 KB Output is correct
113 Correct 215 ms 8568 KB Output is correct
114 Correct 375 ms 8300 KB Output is correct
115 Correct 392 ms 8184 KB Output is correct
116 Correct 219 ms 8312 KB Output is correct
117 Correct 202 ms 8160 KB Output is correct
118 Correct 587 ms 112376 KB Output is correct
119 Correct 535 ms 93688 KB Output is correct
120 Correct 538 ms 88544 KB Output is correct
121 Correct 578 ms 112308 KB Output is correct
122 Correct 523 ms 93256 KB Output is correct
123 Correct 553 ms 88416 KB Output is correct
124 Correct 569 ms 112248 KB Output is correct
125 Correct 513 ms 93688 KB Output is correct
126 Correct 551 ms 88552 KB Output is correct