oj.uz

답안 #95929

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
95929 2019-02-04T12:36:39 Z alishahali1382 Bitaro’s Party (JOI18_bitaro) C++14
14 / 100
 1523 ms 412932 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;

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;
	for (int i=0, j=0; i+j<SQ && i+j<good[a].size()+good[b].size()-1;){
		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 ;
		kill(p.first);
	}
	cout<<"-1\n";
}

void query(){
	cin>>v>>y;
	if (y>=SQ) 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 'void merg(int, int)':
bitaro.cpp:30:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0, j=0; i+j<SQ && i+j<good[a].size()+good[b].size()-1;){
                               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'int smallquery()':
bitaro.cpp:61:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 4984 KB Output is correct
3 Correct 5 ms 5112 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 14 ms 7928 KB Output is correct
6 Correct 13 ms 7676 KB Output is correct
7 Correct 13 ms 7544 KB Output is correct
8 Correct 19 ms 9464 KB Output is correct
9 Correct 17 ms 9464 KB Output is correct
10 Correct 18 ms 9464 KB Output is correct
11 Correct 17 ms 9336 KB Output is correct
12 Correct 15 ms 8284 KB Output is correct
13 Correct 18 ms 9336 KB Output is correct
14 Correct 14 ms 7468 KB Output is correct
15 Correct 10 ms 6520 KB Output is correct
16 Correct 14 ms 7416 KB Output is correct
17 Correct 18 ms 8412 KB Output is correct
18 Correct 14 ms 7288 KB Output is correct
19 Correct 17 ms 8440 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 4984 KB Output is correct
3 Correct 5 ms 5112 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 14 ms 7928 KB Output is correct
6 Correct 13 ms 7676 KB Output is correct
7 Correct 13 ms 7544 KB Output is correct
8 Correct 19 ms 9464 KB Output is correct
9 Correct 17 ms 9464 KB Output is correct
10 Correct 18 ms 9464 KB Output is correct
11 Correct 17 ms 9336 KB Output is correct
12 Correct 15 ms 8284 KB Output is correct
13 Correct 18 ms 9336 KB Output is correct
14 Correct 14 ms 7468 KB Output is correct
15 Correct 10 ms 6520 KB Output is correct
16 Correct 14 ms 7416 KB Output is correct
17 Correct 18 ms 8412 KB Output is correct
18 Correct 14 ms 7288 KB Output is correct
19 Correct 17 ms 8440 KB Output is correct
20 Correct 604 ms 12040 KB Output is correct
21 Correct 588 ms 12040 KB Output is correct
22 Correct 600 ms 12152 KB Output is correct
23 Correct 604 ms 12152 KB Output is correct
24 Correct 1329 ms 323964 KB Output is correct
25 Correct 1296 ms 323588 KB Output is correct
26 Correct 1437 ms 323928 KB Output is correct
27 Correct 1425 ms 412920 KB Output is correct
28 Correct 1431 ms 412872 KB Output is correct
29 Correct 1399 ms 412932 KB Output is correct
30 Correct 1406 ms 412748 KB Output is correct
31 Correct 1472 ms 402812 KB Output is correct
32 Correct 1316 ms 412460 KB Output is correct
33 Correct 1032 ms 254364 KB Output is correct
34 Correct 899 ms 208120 KB Output is correct
35 Correct 1060 ms 252428 KB Output is correct
36 Correct 1297 ms 335960 KB Output is correct
37 Correct 1193 ms 308600 KB Output is correct
38 Correct 1258 ms 336376 KB Output is correct

Subtask #3
0 / 86.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4984 KB Output is correct
2 Correct 5 ms 4984 KB Output is correct
3 Correct 5 ms 5112 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 14 ms 7928 KB Output is correct
6 Correct 13 ms 7676 KB Output is correct
7 Correct 13 ms 7544 KB Output is correct
8 Correct 19 ms 9464 KB Output is correct
9 Correct 17 ms 9464 KB Output is correct
10 Correct 18 ms 9464 KB Output is correct
11 Correct 17 ms 9336 KB Output is correct
12 Correct 15 ms 8284 KB Output is correct
13 Correct 18 ms 9336 KB Output is correct
14 Correct 14 ms 7468 KB Output is correct
15 Correct 10 ms 6520 KB Output is correct
16 Correct 14 ms 7416 KB Output is correct
17 Correct 18 ms 8412 KB Output is correct
18 Correct 14 ms 7288 KB Output is correct
19 Correct 17 ms 8440 KB Output is correct
20 Correct 604 ms 12040 KB Output is correct
21 Correct 588 ms 12040 KB Output is correct
22 Correct 600 ms 12152 KB Output is correct
23 Correct 604 ms 12152 KB Output is correct
24 Correct 1329 ms 323964 KB Output is correct
25 Correct 1296 ms 323588 KB Output is correct
26 Correct 1437 ms 323928 KB Output is correct
27 Correct 1425 ms 412920 KB Output is correct
28 Correct 1431 ms 412872 KB Output is correct
29 Correct 1399 ms 412932 KB Output is correct
30 Correct 1406 ms 412748 KB Output is correct
31 Correct 1472 ms 402812 KB Output is correct
32 Correct 1316 ms 412460 KB Output is correct
33 Correct 1032 ms 254364 KB Output is correct
34 Correct 899 ms 208120 KB Output is correct
35 Correct 1060 ms 252428 KB Output is correct
36 Correct 1297 ms 335960 KB Output is correct
37 Correct 1193 ms 308600 KB Output is correct
38 Correct 1258 ms 336376 KB Output is correct
39 Correct 1414 ms 318064 KB Output is correct
40 Correct 1369 ms 321544 KB Output is correct
41 Correct 1523 ms 321336 KB Output is correct
42 Correct 1503 ms 322360 KB Output is correct
43 Correct 1380 ms 320972 KB Output is correct
44 Incorrect 636 ms 12416 KB Output isn't correct
45 Halted 0 ms 0 KB -