oj.uz

Submission #107351

# Submission time Handle Problem Language Result Execution time Memory
107351 2019-04-23T12:20:07 Z alishahali1382 Bitaro’s Party (JOI18_bitaro) C++14
7 / 100
 2000 ms 11000 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];
map<int, int> mp;

void merg(int a, int b){
	vector<pii> tmp;
	for (pii p:good[a]) mp[p.second]=p.first;
	for (pii p:good[b]) mp[p.second]=max(p.first+1, mp[p.second]);
	good[a].clear();
	for (pii p:mp) good[a].pb({p.second, p.first});
	sort(all(good[a]));
	reverse(all(good[a]));
	if (good[a].size()>SQ) good[a].resize(SQ);
}

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 > (int)good[v].size()) badquery();
	else */if (y>=SQ-10) bigquery();
	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:69:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
bitaro.cpp: In function 'int smallquery()':
bitaro.cpp:64: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 7 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 107 ms 9976 KB Output is correct
6 Correct 118 ms 10232 KB Output is correct
7 Correct 113 ms 9976 KB Output is correct
8 Correct 107 ms 10872 KB Output is correct
9 Correct 111 ms 10936 KB Output is correct
10 Correct 106 ms 10840 KB Output is correct
11 Correct 119 ms 10872 KB Output is correct
12 Correct 116 ms 10816 KB Output is correct
13 Correct 127 ms 11000 KB Output is correct
14 Correct 152 ms 10208 KB Output is correct
15 Correct 168 ms 9976 KB Output is correct
16 Correct 140 ms 10252 KB Output is correct
17 Correct 114 ms 10232 KB Output is correct
18 Correct 138 ms 10076 KB Output is correct
19 Correct 129 ms 10232 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 107 ms 9976 KB Output is correct
6 Correct 118 ms 10232 KB Output is correct
7 Correct 113 ms 9976 KB Output is correct
8 Correct 107 ms 10872 KB Output is correct
9 Correct 111 ms 10936 KB Output is correct
10 Correct 106 ms 10840 KB Output is correct
11 Correct 119 ms 10872 KB Output is correct
12 Correct 116 ms 10816 KB Output is correct
13 Correct 127 ms 11000 KB Output is correct
14 Correct 152 ms 10208 KB Output is correct
15 Correct 168 ms 9976 KB Output is correct
16 Correct 140 ms 10252 KB Output is correct
17 Correct 114 ms 10232 KB Output is correct
18 Correct 138 ms 10076 KB Output is correct
19 Correct 129 ms 10232 KB Output is correct
20 Execution timed out 2021 ms 9228 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 107 ms 9976 KB Output is correct
6 Correct 118 ms 10232 KB Output is correct
7 Correct 113 ms 9976 KB Output is correct
8 Correct 107 ms 10872 KB Output is correct
9 Correct 111 ms 10936 KB Output is correct
10 Correct 106 ms 10840 KB Output is correct
11 Correct 119 ms 10872 KB Output is correct
12 Correct 116 ms 10816 KB Output is correct
13 Correct 127 ms 11000 KB Output is correct
14 Correct 152 ms 10208 KB Output is correct
15 Correct 168 ms 9976 KB Output is correct
16 Correct 140 ms 10252 KB Output is correct
17 Correct 114 ms 10232 KB Output is correct
18 Correct 138 ms 10076 KB Output is correct
19 Correct 129 ms 10232 KB Output is correct
20 Execution timed out 2021 ms 9228 KB Time limit exceeded
21 Halted 0 ms 0 KB -