oj.uz

Submission #963351

# Submission time Handle Problem Language Result Execution time Memory
963351 2024-04-14T21:17:40 Z TimAni Bitaro’s Party (JOI18_bitaro) C++17
100 / 100
 1392 ms 419972 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int sq = 350,MAXN = 1e5+1;
bool take[MAXN],vis[MAXN];
int dp[MAXN];
vector<int>adj[MAXN],radj[MAXN];
vector<pii>good[MAXN];
//if y is >= k then run a naive dp,you will only encounter y>=K atmost n/k times so O(n * n/k)
//if y is < k then we only need to keep track of the k longest paths ending at each node,can do in O(m * k)
int main()
{
	owo
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=0;i<m;i++){
		int v,u;
		cin>>v>>u;
		adj[v].pb(u);
		radj[u].pb(v);
	}
	//good[i] stores the sq longest paths to i
	for(int i=1;i<=n;i++){
		for(int x:radj[i]){
			vector<pii>fin;
			good[x].pb({0,x});
			//duplicates are dangerous
			//remove duplicates while doing merge sort
			int a = 0,b=0;
			int sa = sz(good[x]);
			int sb = sz(good[i]);
			while(sz(fin)<sq  && (a<sa || b < sb)){
				if(b == sb ||  (a!=sa && good[x][a].fi+1 >= good[i][b].fi)){
					good[x][a].fi++;
					fin.pb(good[x][a]);
					vis[good[x][a].se] = 1;
					
					good[x][a].fi--;
					a++;
				}else{
					fin.pb(good[i][b]);
					vis[good[i][b].se] = 1;
					b++;
				}
				while(a<sa && vis[good[x][a].se])a++;
				while(b<sb && vis[good[i][b].se])b++;
			}
			good[x].pop_back();
			for(auto z:fin)vis[z.se] = 0;
			swap(good[i],fin);
		}
	}
	cout<<'\n';
	while(q--){
		int t,y;
		cin>>t>>y;
		vector<int>c(y);
		for(int i=0;i<y;i++){
			cin>>c[i];
			take[c[i]] = 1;
		}
		int ans = -1;
		if(y>=sq){
			for(int i=1;i<=n;i++)dp[i] = -1;
			dp[t] = 0;
			if(!take[t])ans = 0;
			for(int i=t-1;i;i--){
				for(int x:adj[i]){
					if(dp[x]!=-1)dp[i] = max(dp[i],dp[x]+1);
				}
				if(!take[i])ans = max(ans,dp[i]);
			}
		}else{
			for(auto x:good[t]){
				if(!take[x.se]){
					ans = x.fi;
					break;
				}
			}
			if(!take[t])ans = max(ans,0);
		}
		cout<<ans<<'\n';
		for(int i=0;i<y;i++)take[c[i]] = 0;
	}
	
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7260 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 2 ms 7512 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 4 ms 8028 KB Output is correct
6 Correct 4 ms 8024 KB Output is correct
7 Correct 3 ms 7772 KB Output is correct
8 Correct 12 ms 10984 KB Output is correct
9 Correct 10 ms 10844 KB Output is correct
10 Correct 10 ms 10844 KB Output is correct
11 Correct 9 ms 10332 KB Output is correct
12 Correct 5 ms 8796 KB Output is correct
13 Correct 9 ms 10332 KB Output is correct
14 Correct 7 ms 9564 KB Output is correct
15 Correct 6 ms 8544 KB Output is correct
16 Correct 7 ms 9304 KB Output is correct
17 Correct 7 ms 9596 KB Output is correct
18 Correct 5 ms 8756 KB Output is correct
19 Correct 7 ms 9560 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7260 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 2 ms 7512 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 4 ms 8028 KB Output is correct
6 Correct 4 ms 8024 KB Output is correct
7 Correct 3 ms 7772 KB Output is correct
8 Correct 12 ms 10984 KB Output is correct
9 Correct 10 ms 10844 KB Output is correct
10 Correct 10 ms 10844 KB Output is correct
11 Correct 9 ms 10332 KB Output is correct
12 Correct 5 ms 8796 KB Output is correct
13 Correct 9 ms 10332 KB Output is correct
14 Correct 7 ms 9564 KB Output is correct
15 Correct 6 ms 8544 KB Output is correct
16 Correct 7 ms 9304 KB Output is correct
17 Correct 7 ms 9596 KB Output is correct
18 Correct 5 ms 8756 KB Output is correct
19 Correct 7 ms 9560 KB Output is correct
20 Correct 515 ms 14584 KB Output is correct
21 Correct 494 ms 14800 KB Output is correct
22 Correct 514 ms 14776 KB Output is correct
23 Correct 542 ms 14604 KB Output is correct
24 Correct 714 ms 259416 KB Output is correct
25 Correct 718 ms 271076 KB Output is correct
26 Correct 689 ms 270164 KB Output is correct
27 Correct 860 ms 418824 KB Output is correct
28 Correct 864 ms 418804 KB Output is correct
29 Correct 886 ms 418996 KB Output is correct
30 Correct 851 ms 417876 KB Output is correct
31 Correct 958 ms 403296 KB Output is correct
32 Correct 901 ms 417736 KB Output is correct
33 Correct 688 ms 260748 KB Output is correct
34 Correct 611 ms 214492 KB Output is correct
35 Correct 718 ms 259004 KB Output is correct
36 Correct 777 ms 339708 KB Output is correct
37 Correct 736 ms 307792 KB Output is correct
38 Correct 758 ms 340672 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7260 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 2 ms 7512 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 4 ms 8028 KB Output is correct
6 Correct 4 ms 8024 KB Output is correct
7 Correct 3 ms 7772 KB Output is correct
8 Correct 12 ms 10984 KB Output is correct
9 Correct 10 ms 10844 KB Output is correct
10 Correct 10 ms 10844 KB Output is correct
11 Correct 9 ms 10332 KB Output is correct
12 Correct 5 ms 8796 KB Output is correct
13 Correct 9 ms 10332 KB Output is correct
14 Correct 7 ms 9564 KB Output is correct
15 Correct 6 ms 8544 KB Output is correct
16 Correct 7 ms 9304 KB Output is correct
17 Correct 7 ms 9596 KB Output is correct
18 Correct 5 ms 8756 KB Output is correct
19 Correct 7 ms 9560 KB Output is correct
20 Correct 515 ms 14584 KB Output is correct
21 Correct 494 ms 14800 KB Output is correct
22 Correct 514 ms 14776 KB Output is correct
23 Correct 542 ms 14604 KB Output is correct
24 Correct 714 ms 259416 KB Output is correct
25 Correct 718 ms 271076 KB Output is correct
26 Correct 689 ms 270164 KB Output is correct
27 Correct 860 ms 418824 KB Output is correct
28 Correct 864 ms 418804 KB Output is correct
29 Correct 886 ms 418996 KB Output is correct
30 Correct 851 ms 417876 KB Output is correct
31 Correct 958 ms 403296 KB Output is correct
32 Correct 901 ms 417736 KB Output is correct
33 Correct 688 ms 260748 KB Output is correct
34 Correct 611 ms 214492 KB Output is correct
35 Correct 718 ms 259004 KB Output is correct
36 Correct 777 ms 339708 KB Output is correct
37 Correct 736 ms 307792 KB Output is correct
38 Correct 758 ms 340672 KB Output is correct
39 Correct 723 ms 263576 KB Output is correct
40 Correct 726 ms 265632 KB Output is correct
41 Correct 691 ms 267856 KB Output is correct
42 Correct 806 ms 266192 KB Output is correct
43 Correct 732 ms 265512 KB Output is correct
44 Correct 538 ms 16056 KB Output is correct
45 Correct 520 ms 15228 KB Output is correct
46 Correct 493 ms 15088 KB Output is correct
47 Correct 553 ms 14996 KB Output is correct
48 Correct 474 ms 14560 KB Output is correct
49 Correct 1184 ms 419704 KB Output is correct
50 Correct 869 ms 418356 KB Output is correct
51 Correct 525 ms 15760 KB Output is correct
52 Correct 493 ms 15004 KB Output is correct
53 Correct 858 ms 338676 KB Output is correct
54 Correct 802 ms 308736 KB Output is correct
55 Correct 776 ms 338092 KB Output is correct
56 Correct 790 ms 308436 KB Output is correct
57 Correct 506 ms 15824 KB Output is correct
58 Correct 503 ms 15732 KB Output is correct
59 Correct 502 ms 14852 KB Output is correct
60 Correct 541 ms 14872 KB Output is correct
61 Correct 1160 ms 418764 KB Output is correct
62 Correct 843 ms 339956 KB Output is correct
63 Correct 845 ms 307436 KB Output is correct
64 Correct 1177 ms 418748 KB Output is correct
65 Correct 827 ms 338272 KB Output is correct
66 Correct 822 ms 309172 KB Output is correct
67 Correct 894 ms 418300 KB Output is correct
68 Correct 791 ms 339316 KB Output is correct
69 Correct 827 ms 304736 KB Output is correct
70 Correct 1085 ms 418908 KB Output is correct
71 Correct 799 ms 340056 KB Output is correct
72 Correct 782 ms 308560 KB Output is correct
73 Correct 1134 ms 418884 KB Output is correct
74 Correct 869 ms 339940 KB Output is correct
75 Correct 836 ms 308908 KB Output is correct
76 Correct 1167 ms 419972 KB Output is correct
77 Correct 877 ms 418692 KB Output is correct
78 Correct 1168 ms 419140 KB Output is correct
79 Correct 503 ms 16008 KB Output is correct
80 Correct 490 ms 15208 KB Output is correct
81 Correct 509 ms 14676 KB Output is correct
82 Correct 1165 ms 418640 KB Output is correct
83 Correct 1138 ms 404496 KB Output is correct
84 Correct 841 ms 417512 KB Output is correct
85 Correct 1062 ms 402908 KB Output is correct
86 Correct 1392 ms 417860 KB Output is correct
87 Correct 1114 ms 404140 KB Output is correct
88 Correct 518 ms 16052 KB Output is correct
89 Correct 525 ms 16068 KB Output is correct
90 Correct 486 ms 14980 KB Output is correct
91 Correct 497 ms 14952 KB Output is correct
92 Correct 496 ms 14672 KB Output is correct
93 Correct 529 ms 14676 KB Output is correct
94 Correct 702 ms 261728 KB Output is correct
95 Correct 628 ms 214384 KB Output is correct
96 Correct 666 ms 259452 KB Output is correct
97 Correct 597 ms 217244 KB Output is correct
98 Correct 657 ms 260564 KB Output is correct
99 Correct 582 ms 216928 KB Output is correct
100 Correct 558 ms 16124 KB Output is correct
101 Correct 563 ms 15908 KB Output is correct
102 Correct 564 ms 15196 KB Output is correct
103 Correct 522 ms 15140 KB Output is correct
104 Correct 569 ms 14672 KB Output is correct
105 Correct 556 ms 14756 KB Output is correct
106 Correct 857 ms 339472 KB Output is correct
107 Correct 849 ms 309400 KB Output is correct
108 Correct 871 ms 340456 KB Output is correct
109 Correct 754 ms 307860 KB Output is correct
110 Correct 835 ms 341036 KB Output is correct
111 Correct 774 ms 309328 KB Output is correct
112 Correct 507 ms 15988 KB Output is correct
113 Correct 571 ms 15956 KB Output is correct
114 Correct 482 ms 15256 KB Output is correct
115 Correct 493 ms 15084 KB Output is correct
116 Correct 532 ms 14624 KB Output is correct
117 Correct 515 ms 14788 KB Output is correct
118 Correct 1134 ms 418392 KB Output is correct
119 Correct 766 ms 340068 KB Output is correct
120 Correct 742 ms 307564 KB Output is correct
121 Correct 1082 ms 418428 KB Output is correct
122 Correct 797 ms 338672 KB Output is correct
123 Correct 745 ms 307584 KB Output is correct
124 Correct 867 ms 418388 KB Output is correct
125 Correct 763 ms 340280 KB Output is correct
126 Correct 802 ms 306404 KB Output is correct