답안 #95935 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95935	2019-02-04T12:50:47 Z	alishahali1382	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	1491 ms	411040 KB

bitaro

#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];

void merg(int a, int b){
	vector<pii> tmp;
	int sz=min(SQ+1, SZ(good[a])+SZ(good[b]));
	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";
}

void query(){
	cin>>v>>y;
	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);
	}
	//for (int i=1; i<=n; i++) good[i].pop_back();
	while (q--) query();
	
	return 0;
}

Compilation message

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

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5112 KB	Output is correct
2	Correct	6 ms	5112 KB	Output is correct
3	Correct	5 ms	4984 KB	Output is correct
4	Correct	6 ms	4984 KB	Output is correct
5	Correct	17 ms	8188 KB	Output is correct
6	Correct	16 ms	8056 KB	Output is correct
7	Correct	15 ms	8056 KB	Output is correct
8	Correct	17 ms	9464 KB	Output is correct
9	Correct	19 ms	9464 KB	Output is correct
10	Correct	18 ms	9464 KB	Output is correct
11	Correct	18 ms	9336 KB	Output is correct
12	Correct	16 ms	8568 KB	Output is correct
13	Correct	17 ms	9336 KB	Output is correct
14	Correct	14 ms	7544 KB	Output is correct
15	Correct	13 ms	6776 KB	Output is correct
16	Correct	15 ms	7600 KB	Output is correct
17	Correct	17 ms	8568 KB	Output is correct
18	Correct	14 ms	7416 KB	Output is correct
19	Correct	17 ms	8568 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5112 KB	Output is correct
2	Correct	6 ms	5112 KB	Output is correct
3	Correct	5 ms	4984 KB	Output is correct
4	Correct	6 ms	4984 KB	Output is correct
5	Correct	17 ms	8188 KB	Output is correct
6	Correct	16 ms	8056 KB	Output is correct
7	Correct	15 ms	8056 KB	Output is correct
8	Correct	17 ms	9464 KB	Output is correct
9	Correct	19 ms	9464 KB	Output is correct
10	Correct	18 ms	9464 KB	Output is correct
11	Correct	18 ms	9336 KB	Output is correct
12	Correct	16 ms	8568 KB	Output is correct
13	Correct	17 ms	9336 KB	Output is correct
14	Correct	14 ms	7544 KB	Output is correct
15	Correct	13 ms	6776 KB	Output is correct
16	Correct	15 ms	7600 KB	Output is correct
17	Correct	17 ms	8568 KB	Output is correct
18	Correct	14 ms	7416 KB	Output is correct
19	Correct	17 ms	8568 KB	Output is correct
20	Correct	542 ms	10852 KB	Output is correct
21	Correct	534 ms	10664 KB	Output is correct
22	Correct	540 ms	10864 KB	Output is correct
23	Correct	537 ms	10616 KB	Output is correct
24	Correct	1348 ms	325352 KB	Output is correct
25	Correct	1491 ms	324848 KB	Output is correct
26	Correct	1390 ms	325484 KB	Output is correct
27	Correct	1375 ms	411000 KB	Output is correct
28	Correct	1337 ms	411000 KB	Output is correct
29	Correct	1365 ms	411040 KB	Output is correct
30	Correct	1361 ms	410936 KB	Output is correct
31	Correct	1324 ms	403396 KB	Output is correct
32	Correct	1253 ms	411000 KB	Output is correct
33	Correct	965 ms	254824 KB	Output is correct
34	Correct	891 ms	217592 KB	Output is correct
35	Correct	993 ms	253300 KB	Output is correct
36	Correct	1184 ms	334664 KB	Output is correct
37	Correct	1145 ms	312840 KB	Output is correct
38	Correct	1184 ms	335224 KB	Output is correct

Subtask #3
0 / 86.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5112 KB	Output is correct
2	Correct	6 ms	5112 KB	Output is correct
3	Correct	5 ms	4984 KB	Output is correct
4	Correct	6 ms	4984 KB	Output is correct
5	Correct	17 ms	8188 KB	Output is correct
6	Correct	16 ms	8056 KB	Output is correct
7	Correct	15 ms	8056 KB	Output is correct
8	Correct	17 ms	9464 KB	Output is correct
9	Correct	19 ms	9464 KB	Output is correct
10	Correct	18 ms	9464 KB	Output is correct
11	Correct	18 ms	9336 KB	Output is correct
12	Correct	16 ms	8568 KB	Output is correct
13	Correct	17 ms	9336 KB	Output is correct
14	Correct	14 ms	7544 KB	Output is correct
15	Correct	13 ms	6776 KB	Output is correct
16	Correct	15 ms	7600 KB	Output is correct
17	Correct	17 ms	8568 KB	Output is correct
18	Correct	14 ms	7416 KB	Output is correct
19	Correct	17 ms	8568 KB	Output is correct
20	Correct	542 ms	10852 KB	Output is correct
21	Correct	534 ms	10664 KB	Output is correct
22	Correct	540 ms	10864 KB	Output is correct
23	Correct	537 ms	10616 KB	Output is correct
24	Correct	1348 ms	325352 KB	Output is correct
25	Correct	1491 ms	324848 KB	Output is correct
26	Correct	1390 ms	325484 KB	Output is correct
27	Correct	1375 ms	411000 KB	Output is correct
28	Correct	1337 ms	411000 KB	Output is correct
29	Correct	1365 ms	411040 KB	Output is correct
30	Correct	1361 ms	410936 KB	Output is correct
31	Correct	1324 ms	403396 KB	Output is correct
32	Correct	1253 ms	411000 KB	Output is correct
33	Correct	965 ms	254824 KB	Output is correct
34	Correct	891 ms	217592 KB	Output is correct
35	Correct	993 ms	253300 KB	Output is correct
36	Correct	1184 ms	334664 KB	Output is correct
37	Correct	1145 ms	312840 KB	Output is correct
38	Correct	1184 ms	335224 KB	Output is correct
39	Correct	1384 ms	322076 KB	Output is correct
40	Correct	1405 ms	322680 KB	Output is correct
41	Correct	1384 ms	323192 KB	Output is correct
42	Correct	1390 ms	325368 KB	Output is correct
43	Correct	1230 ms	323164 KB	Output is correct
44	Incorrect	574 ms	10744 KB	Output isn't correct
45	Halted	0 ms	0 KB	-

답안 #95935

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 7.0 / 7.0

Subtask #3 0 / 86.0

Subtask #1
7.0 / 7.0

Subtask #2
7.0 / 7.0

Subtask #3
0 / 86.0