oj.uz

Submission #107358

# Submission time Handle Problem Language Result Execution time Memory
107358 2019-04-23T12:27:13 Z alishahali1382 Bitaro’s Party (JOI18_bitaro) C++14
14 / 100
 274 ms 14936 KB 
#include <bits/stdc++.h>
#if defined(__GNUC__)
#pragma GCC optimize ("Ofast")
#endif
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<x<<endl;
#define debugp(x) cerr<<#x<<"= {"<<x.first<<", "<<x.second<<"}"<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
#define SZ(x) ((int) x.size())

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 100010, SQ=320;

int n, m, q, u, v, x, y, t, a, b, ans;
vector<pii> good[MAXN];
int dp[MAXN];
vector<int> G[MAXN];
unordered_map<int, int> mp;

void merg(int a, int b){
	vector<pii> tmp;
	int sz=min(SQ+1, SZ(good[a])+SZ(good[b])-2);
	for (int i=0, j=0; i+j<sz;){
		pii pp={good[b][j].first+1, good[b][j].second};
		if (good[a][i]>pp) tmp.pb(good[a][i++]);
		else tmp.pb(pp), j++;
	}
	good[a].clear();
	for (pii p:tmp) good[a].pb(p);
}

void bigquery(){
	while (y--){
		cin>>x;
		dp[x]=-inf;
	}
	for (int i=1; i<=v; i++) for (int j:G[i]) dp[i]=max(dp[i], dp[j]+1);
	if (dp[v]<0) dp[v]=-1;
	cout<<dp[v]<<'\n';
	memset(dp, 0, sizeof(dp));
}

int smallquery(){
	set<int> st;
	while (y--){
		cin>>x;
		st.insert(x);
	}
	for (pii p:good[v]){
		if (st.count(p.second)) continue ;
		if (p.first<0) kill(-1);
		kill(p.first);
	}
	cout<<"-1\n";
}

int badquery(){
	while (y--) cin>>x;
	cout<<"-1\n";
}

void query(){
	cin>>v>>y;
	if (y>=SQ-10) bigquery();
	else if (y > (int)good[v].size()+5) badquery();
	else smallquery();
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m>>q;
	while (m--){
		cin>>u>>v;
		G[v].pb(u);
	}
	for (int i=1; i<=n; i++){
		good[i].pb({0, i});
		good[i].pb({-inf, 0});
		for (int j:G[i]) merg(i, j);
	}
	
	while (q--) query();
	
	return 0;
}
/*
5 6 3
1 2
2 4
3 4
1 3
3 5
4 5
4 1 1
5 2 2 3
2 3 1 4 5
*/

Compilation message

bitaro.cpp: In function 'int badquery()':
bitaro.cpp:70:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
bitaro.cpp: In function 'int smallquery()':
bitaro.cpp:65:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 8 ms 5504 KB Output is correct
6 Correct 8 ms 5504 KB Output is correct
7 Correct 7 ms 5504 KB Output is correct
8 Correct 7 ms 5504 KB Output is correct
9 Correct 7 ms 5504 KB Output is correct
10 Correct 7 ms 5504 KB Output is correct
11 Correct 7 ms 5632 KB Output is correct
12 Correct 9 ms 5504 KB Output is correct
13 Correct 10 ms 5504 KB Output is correct
14 Correct 9 ms 5504 KB Output is correct
15 Correct 8 ms 5504 KB Output is correct
16 Correct 10 ms 5504 KB Output is correct
17 Correct 8 ms 5504 KB Output is correct
18 Correct 8 ms 5504 KB Output is correct
19 Correct 8 ms 5504 KB Output is correct
20 Correct 64 ms 6620 KB Output is correct
21 Correct 68 ms 8124 KB Output is correct
22 Correct 63 ms 8184 KB Output is correct
23 Correct 69 ms 8252 KB Output is correct
24 Correct 181 ms 13860 KB Output is correct
25 Correct 196 ms 13916 KB Output is correct
26 Correct 241 ms 13944 KB Output is correct
27 Correct 168 ms 14456 KB Output is correct
28 Correct 188 ms 14352 KB Output is correct
29 Correct 173 ms 14284 KB Output is correct
30 Correct 167 ms 14328 KB Output is correct
31 Correct 168 ms 14516 KB Output is correct
32 Correct 153 ms 14456 KB Output is correct
33 Correct 167 ms 13916 KB Output is correct
34 Correct 141 ms 13928 KB Output is correct
35 Correct 150 ms 13944 KB Output is correct
36 Correct 179 ms 14072 KB Output is correct
37 Correct 139 ms 13944 KB Output is correct
38 Correct 181 ms 14044 KB Output is correct

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 8 ms 5504 KB Output is correct
6 Correct 8 ms 5504 KB Output is correct
7 Correct 7 ms 5504 KB Output is correct
8 Correct 7 ms 5504 KB Output is correct
9 Correct 7 ms 5504 KB Output is correct
10 Correct 7 ms 5504 KB Output is correct
11 Correct 7 ms 5632 KB Output is correct
12 Correct 9 ms 5504 KB Output is correct
13 Correct 10 ms 5504 KB Output is correct
14 Correct 9 ms 5504 KB Output is correct
15 Correct 8 ms 5504 KB Output is correct
16 Correct 10 ms 5504 KB Output is correct
17 Correct 8 ms 5504 KB Output is correct
18 Correct 8 ms 5504 KB Output is correct
19 Correct 8 ms 5504 KB Output is correct
20 Correct 64 ms 6620 KB Output is correct
21 Correct 68 ms 8124 KB Output is correct
22 Correct 63 ms 8184 KB Output is correct
23 Correct 69 ms 8252 KB Output is correct
24 Correct 181 ms 13860 KB Output is correct
25 Correct 196 ms 13916 KB Output is correct
26 Correct 241 ms 13944 KB Output is correct
27 Correct 168 ms 14456 KB Output is correct
28 Correct 188 ms 14352 KB Output is correct
29 Correct 173 ms 14284 KB Output is correct
30 Correct 167 ms 14328 KB Output is correct
31 Correct 168 ms 14516 KB Output is correct
32 Correct 153 ms 14456 KB Output is correct
33 Correct 167 ms 13916 KB Output is correct
34 Correct 141 ms 13928 KB Output is correct
35 Correct 150 ms 13944 KB Output is correct
36 Correct 179 ms 14072 KB Output is correct
37 Correct 139 ms 13944 KB Output is correct
38 Correct 181 ms 14044 KB Output is correct
39 Incorrect 274 ms 14936 KB Output isn't correct
40 Halted 0 ms 0 KB -