답안 #62550 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62550	2018-07-29T05:23:51 Z	gusfring	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	1967 ms	110968 KB

bitaro

#include <bits/stdc++.h>
using namespace std;
 
#define pii pair<int, int>
#define fi first
#define se second
 
const int mxN=1e5, bs=80;
int n, m, q, dp2[mxN], c[mxN];
vector<int> adj[mxN];
vector<pii> dp1[mxN];
priority_queue<pii, vector<pii>, greater<pii>> pq;
bool a[mxN];
 
int main() {
	scanf("%d %d %d", &n, &m, &q);
	while(m--) {
		int u, v;
		scanf("%d %d", &u, &v);
      	--u, --v;
		adj[v].push_back(u);
	}
	for(int i=0; i<n; ++i) {
		pq.push({0, i});
		for(int v : adj[i]) {
			for(pii p : dp1[v]) {
				pq.push({p.fi+1, p.se});
				if(pq.size()>bs)
					pq.pop();
			}
		}
		while(!pq.empty()) {
			dp1[i].push_back(pq.top());
			pq.pop();
		}
	}
	while(q--) {
		int t, y, ans=-1;
		scanf("%d %d", &t, &y);
        --t;
		for(int i=0; i<y; ++i) {
			scanf("%d", &c[i]);
          	--c[i];
			a[c[i]]=1;
		}
		if(y>bs) {
			memset(dp2, -1, 4*(t+1));
			for(int i=0; i<=t; ++i) {
				dp2[i]=a[i]?-n:0;
				for(int v : adj[i])
					dp2[i]=max(dp2[v]+1, dp2[i]);
			}
			ans=max(dp2[t], ans);
		} else {
			for(int i=dp1[t].size()-1; i>=0; --i) {
				if(a[dp1[t][i].se])
					continue;
				ans=dp1[t][i].fi;
				break;
			}
		}
		for(int i=0; i<y; ++i)
			a[c[i]]=0;
		printf("%d\n", ans);
	}
  return 0;
}

Compilation message

bitaro.cpp: In function 'int main()':
bitaro.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &t, &y);
   ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:42:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &c[i]);
    ~~~~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4984 KB	Output is correct
2	Correct	7 ms	5116 KB	Output is correct
3	Correct	7 ms	5116 KB	Output is correct
4	Correct	7 ms	5116 KB	Output is correct
5	Correct	18 ms	5944 KB	Output is correct
6	Correct	15 ms	5944 KB	Output is correct
7	Correct	17 ms	6020 KB	Output is correct
8	Correct	17 ms	6296 KB	Output is correct
9	Correct	16 ms	6296 KB	Output is correct
10	Correct	16 ms	6296 KB	Output is correct
11	Correct	17 ms	6316 KB	Output is correct
12	Correct	17 ms	6316 KB	Output is correct
13	Correct	17 ms	6316 KB	Output is correct
14	Correct	15 ms	6316 KB	Output is correct
15	Correct	14 ms	6316 KB	Output is correct
16	Correct	15 ms	6316 KB	Output is correct
17	Correct	16 ms	6316 KB	Output is correct
18	Correct	16 ms	6316 KB	Output is correct
19	Correct	16 ms	6316 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4984 KB	Output is correct
2	Correct	7 ms	5116 KB	Output is correct
3	Correct	7 ms	5116 KB	Output is correct
4	Correct	7 ms	5116 KB	Output is correct
5	Correct	18 ms	5944 KB	Output is correct
6	Correct	15 ms	5944 KB	Output is correct
7	Correct	17 ms	6020 KB	Output is correct
8	Correct	17 ms	6296 KB	Output is correct
9	Correct	16 ms	6296 KB	Output is correct
10	Correct	16 ms	6296 KB	Output is correct
11	Correct	17 ms	6316 KB	Output is correct
12	Correct	17 ms	6316 KB	Output is correct
13	Correct	17 ms	6316 KB	Output is correct
14	Correct	15 ms	6316 KB	Output is correct
15	Correct	14 ms	6316 KB	Output is correct
16	Correct	15 ms	6316 KB	Output is correct
17	Correct	16 ms	6316 KB	Output is correct
18	Correct	16 ms	6316 KB	Output is correct
19	Correct	16 ms	6316 KB	Output is correct
20	Correct	794 ms	7520 KB	Output is correct
21	Correct	768 ms	7520 KB	Output is correct
22	Correct	785 ms	7540 KB	Output is correct
23	Correct	778 ms	7540 KB	Output is correct
24	Correct	1351 ms	89908 KB	Output is correct
25	Correct	1346 ms	89908 KB	Output is correct
26	Correct	1286 ms	89908 KB	Output is correct
27	Correct	1089 ms	110792 KB	Output is correct
28	Correct	1081 ms	110968 KB	Output is correct
29	Correct	1071 ms	110968 KB	Output is correct
30	Correct	1064 ms	110968 KB	Output is correct
31	Correct	1282 ms	110968 KB	Output is correct
32	Correct	1070 ms	110968 KB	Output is correct
33	Correct	888 ms	110968 KB	Output is correct
34	Correct	888 ms	110968 KB	Output is correct
35	Correct	894 ms	110968 KB	Output is correct
36	Correct	944 ms	110968 KB	Output is correct
37	Correct	1256 ms	110968 KB	Output is correct
38	Correct	1084 ms	110968 KB	Output is correct

Subtask #3
0 / 86.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	4984 KB	Output is correct
2	Correct	7 ms	5116 KB	Output is correct
3	Correct	7 ms	5116 KB	Output is correct
4	Correct	7 ms	5116 KB	Output is correct
5	Correct	18 ms	5944 KB	Output is correct
6	Correct	15 ms	5944 KB	Output is correct
7	Correct	17 ms	6020 KB	Output is correct
8	Correct	17 ms	6296 KB	Output is correct
9	Correct	16 ms	6296 KB	Output is correct
10	Correct	16 ms	6296 KB	Output is correct
11	Correct	17 ms	6316 KB	Output is correct
12	Correct	17 ms	6316 KB	Output is correct
13	Correct	17 ms	6316 KB	Output is correct
14	Correct	15 ms	6316 KB	Output is correct
15	Correct	14 ms	6316 KB	Output is correct
16	Correct	15 ms	6316 KB	Output is correct
17	Correct	16 ms	6316 KB	Output is correct
18	Correct	16 ms	6316 KB	Output is correct
19	Correct	16 ms	6316 KB	Output is correct
20	Correct	794 ms	7520 KB	Output is correct
21	Correct	768 ms	7520 KB	Output is correct
22	Correct	785 ms	7540 KB	Output is correct
23	Correct	778 ms	7540 KB	Output is correct
24	Correct	1351 ms	89908 KB	Output is correct
25	Correct	1346 ms	89908 KB	Output is correct
26	Correct	1286 ms	89908 KB	Output is correct
27	Correct	1089 ms	110792 KB	Output is correct
28	Correct	1081 ms	110968 KB	Output is correct
29	Correct	1071 ms	110968 KB	Output is correct
30	Correct	1064 ms	110968 KB	Output is correct
31	Correct	1282 ms	110968 KB	Output is correct
32	Correct	1070 ms	110968 KB	Output is correct
33	Correct	888 ms	110968 KB	Output is correct
34	Correct	888 ms	110968 KB	Output is correct
35	Correct	894 ms	110968 KB	Output is correct
36	Correct	944 ms	110968 KB	Output is correct
37	Correct	1256 ms	110968 KB	Output is correct
38	Correct	1084 ms	110968 KB	Output is correct
39	Correct	1439 ms	110968 KB	Output is correct
40	Correct	1291 ms	110968 KB	Output is correct
41	Correct	1967 ms	110968 KB	Output is correct
42	Correct	1400 ms	110968 KB	Output is correct
43	Correct	1310 ms	110968 KB	Output is correct
44	Incorrect	831 ms	110968 KB	Output isn't correct
45	Halted	0 ms	0 KB	-

답안 #62550

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