oj.uz

Submission #285118

# Submission time Handle Problem Language Result Execution time Memory
285118 2020-08-28T10:28:24 Z Plurm Bitaro’s Party (JOI18_bitaro) C++11
100 / 100
 1677 ms 338284 KB 
#include <bits/stdc++.h>
using namespace std;
const int THRESH = 400;
vector<int> ord;
vector<int> g[100005];
vector<int> rg[100005];
bool found[100005];
void dfs(int u){
	if(found[u]) return;
	found[u] = true;
	for(int v : g[u]){
		dfs(v);
	}
	ord.push_back(u);
}
vector<pair<int,int> > dp[100005]; // | dp[i] | <= THRESH.
bool __used[100005];
vector<pair<int,int> > newVec;
inline void __append(const pair<int,int>& x){
	if(newVec.empty() || !__used[x.second]){
		newVec.push_back(x);
		__used[x.second] = true;
	}
}
inline void merge(vector<pair<int,int> >& dest, vector<pair<int,int> > src){
	newVec.reserve(THRESH);
	for(auto& v : src) v.first++;
	int ptr1 = 0;
	int ptr2 = 0;
	while(ptr1 < dest.size() && ptr2 < src.size() && newVec.size() < THRESH){
		if(dest[ptr1] > src[ptr2]){
			__append(dest[ptr1]);
			ptr1++;
		}else{
			__append(src[ptr2]);
			ptr2++;
		}
	}
	while(newVec.size() < THRESH && ptr1 < dest.size()){
		__append(dest[ptr1]);
		ptr1++;
	}
	while(newVec.size() < THRESH && ptr2 < src.size()){
		__append(src[ptr2]);
		ptr2++;
	}
	for(auto u : newVec) __used[u.second] = false;
	swap(dest, newVec);
	newVec.clear();
}
bool isBusy[100005];
int subdp[100005];
inline int recalculateAnswer(const int& t){
	for(int u : ord){
		subdp[u] = isBusy[u] ? -10000000 : 0;
		for(int v : rg[u]){
			subdp[u] = max(subdp[u], subdp[v]+1);
		}
		if(u == t) return subdp[t] < 0 ? -1 : subdp[t];
	}
}
int main(){
	int n, m, q;
	scanf("%d%d%d",&n,&m,&q);
	for(int i = 0; i < m; i++){
		int s,e;
		scanf("%d%d",&s,&e);
		g[s].push_back(e);
		rg[e].push_back(s);
	}
	for(int i = 1; i <= n; i++) dfs(i);
	reverse(ord.begin(), ord.end());
	for(int u : ord){
		for(int v : rg[u]){
			merge(dp[u], dp[v]);
		}
		merge(dp[u], {make_pair(-1, u)});
	}
	int t, y;
	vector<int> busy;
	for(int qq = 0; qq < q; qq++){
		scanf("%d%d",&t,&y);
		busy.reserve(y);
		for(int i = 0; i < y; i++){
			int c;
			scanf("%d",&c);
			busy.push_back(c);
			isBusy[c] = true;
		}
		int ans = -1;
		if(y < THRESH){
			for(auto p : dp[t]){
				if(isBusy[p.second]) continue;
				ans = p.first;
				break;
			}
		}else{
			ans = recalculateAnswer(t);
		}
		for(int c : busy) isBusy[c] = false;
		busy.clear();
		printf("%d\n",ans);
	}
	return 0;
}

Compilation message

bitaro.cpp: In function 'void merge(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >)':
bitaro.cpp:30:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  while(ptr1 < dest.size() && ptr2 < src.size() && newVec.size() < THRESH){
      |        ~~~~~^~~~~~~~~~~~~
bitaro.cpp:30:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  while(ptr1 < dest.size() && ptr2 < src.size() && newVec.size() < THRESH){
      |                              ~~~~~^~~~~~~~~~~~
bitaro.cpp:39:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  while(newVec.size() < THRESH && ptr1 < dest.size()){
      |                                  ~~~~~^~~~~~~~~~~~~
bitaro.cpp:43:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  while(newVec.size() < THRESH && ptr2 < src.size()){
      |                                  ~~~~~^~~~~~~~~~~~
bitaro.cpp: In function 'int main()':
bitaro.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |  scanf("%d%d%d",&n,&m,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |   scanf("%d%d",&s,&e);
      |   ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |   scanf("%d%d",&t,&y);
      |   ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:86:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |    scanf("%d",&c);
      |    ~~~~~^~~~~~~~~
bitaro.cpp: In function 'int recalculateAnswer(const int&)':
bitaro.cpp:61:1: warning: control reaches end of non-void function [-Wreturn-type]
   61 | }
      | ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 5 ms 7424 KB Output is correct
5 Correct 11 ms 10624 KB Output is correct
6 Correct 10 ms 10624 KB Output is correct
7 Correct 11 ms 10656 KB Output is correct
8 Correct 18 ms 10752 KB Output is correct
9 Correct 18 ms 10752 KB Output is correct
10 Correct 18 ms 10744 KB Output is correct
11 Correct 17 ms 10624 KB Output is correct
12 Correct 12 ms 10752 KB Output is correct
13 Correct 17 ms 10624 KB Output is correct
14 Correct 16 ms 10624 KB Output is correct
15 Correct 14 ms 10624 KB Output is correct
16 Correct 15 ms 10676 KB Output is correct
17 Correct 15 ms 10752 KB Output is correct
18 Correct 12 ms 10624 KB Output is correct
19 Correct 15 ms 10624 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 5 ms 7424 KB Output is correct
5 Correct 11 ms 10624 KB Output is correct
6 Correct 10 ms 10624 KB Output is correct
7 Correct 11 ms 10656 KB Output is correct
8 Correct 18 ms 10752 KB Output is correct
9 Correct 18 ms 10752 KB Output is correct
10 Correct 18 ms 10744 KB Output is correct
11 Correct 17 ms 10624 KB Output is correct
12 Correct 12 ms 10752 KB Output is correct
13 Correct 17 ms 10624 KB Output is correct
14 Correct 16 ms 10624 KB Output is correct
15 Correct 14 ms 10624 KB Output is correct
16 Correct 15 ms 10676 KB Output is correct
17 Correct 15 ms 10752 KB Output is correct
18 Correct 12 ms 10624 KB Output is correct
19 Correct 15 ms 10624 KB Output is correct
20 Correct 966 ms 14504 KB Output is correct
21 Correct 819 ms 14644 KB Output is correct
22 Correct 949 ms 14564 KB Output is correct
23 Correct 1006 ms 14704 KB Output is correct
24 Correct 1280 ms 331284 KB Output is correct
25 Correct 1359 ms 331200 KB Output is correct
26 Correct 1328 ms 331120 KB Output is correct
27 Correct 1513 ms 337012 KB Output is correct
28 Correct 1517 ms 337076 KB Output is correct
29 Correct 1511 ms 337136 KB Output is correct
30 Correct 1548 ms 331576 KB Output is correct
31 Correct 1555 ms 331796 KB Output is correct
32 Correct 1522 ms 331760 KB Output is correct
33 Correct 1188 ms 332912 KB Output is correct
34 Correct 1116 ms 332212 KB Output is correct
35 Correct 1189 ms 332284 KB Output is correct
36 Correct 1370 ms 332396 KB Output is correct
37 Correct 1337 ms 331764 KB Output is correct
38 Correct 1409 ms 332540 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 5 ms 7424 KB Output is correct
5 Correct 11 ms 10624 KB Output is correct
6 Correct 10 ms 10624 KB Output is correct
7 Correct 11 ms 10656 KB Output is correct
8 Correct 18 ms 10752 KB Output is correct
9 Correct 18 ms 10752 KB Output is correct
10 Correct 18 ms 10744 KB Output is correct
11 Correct 17 ms 10624 KB Output is correct
12 Correct 12 ms 10752 KB Output is correct
13 Correct 17 ms 10624 KB Output is correct
14 Correct 16 ms 10624 KB Output is correct
15 Correct 14 ms 10624 KB Output is correct
16 Correct 15 ms 10676 KB Output is correct
17 Correct 15 ms 10752 KB Output is correct
18 Correct 12 ms 10624 KB Output is correct
19 Correct 15 ms 10624 KB Output is correct
20 Correct 966 ms 14504 KB Output is correct
21 Correct 819 ms 14644 KB Output is correct
22 Correct 949 ms 14564 KB Output is correct
23 Correct 1006 ms 14704 KB Output is correct
24 Correct 1280 ms 331284 KB Output is correct
25 Correct 1359 ms 331200 KB Output is correct
26 Correct 1328 ms 331120 KB Output is correct
27 Correct 1513 ms 337012 KB Output is correct
28 Correct 1517 ms 337076 KB Output is correct
29 Correct 1511 ms 337136 KB Output is correct
30 Correct 1548 ms 331576 KB Output is correct
31 Correct 1555 ms 331796 KB Output is correct
32 Correct 1522 ms 331760 KB Output is correct
33 Correct 1188 ms 332912 KB Output is correct
34 Correct 1116 ms 332212 KB Output is correct
35 Correct 1189 ms 332284 KB Output is correct
36 Correct 1370 ms 332396 KB Output is correct
37 Correct 1337 ms 331764 KB Output is correct
38 Correct 1409 ms 332540 KB Output is correct
39 Correct 1357 ms 330524 KB Output is correct
40 Correct 1328 ms 330272 KB Output is correct
41 Correct 1293 ms 329968 KB Output is correct
42 Correct 1525 ms 330608 KB Output is correct
43 Correct 1331 ms 330336 KB Output is correct
44 Correct 1022 ms 15372 KB Output is correct
45 Correct 993 ms 14204 KB Output is correct
46 Correct 960 ms 14200 KB Output is correct
47 Correct 979 ms 14108 KB Output is correct
48 Correct 957 ms 14072 KB Output is correct
49 Correct 1583 ms 336440 KB Output is correct
50 Correct 1534 ms 335728 KB Output is correct
51 Correct 880 ms 15232 KB Output is correct
52 Correct 859 ms 14856 KB Output is correct
53 Correct 1460 ms 332068 KB Output is correct
54 Correct 1430 ms 330832 KB Output is correct
55 Correct 1397 ms 331256 KB Output is correct
56 Correct 1332 ms 330484 KB Output is correct
57 Correct 1014 ms 15192 KB Output is correct
58 Correct 1060 ms 15092 KB Output is correct
59 Correct 954 ms 14808 KB Output is correct
60 Correct 1030 ms 14588 KB Output is correct
61 Correct 1635 ms 336192 KB Output is correct
62 Correct 1597 ms 331888 KB Output is correct
63 Correct 1499 ms 330632 KB Output is correct
64 Correct 1542 ms 335472 KB Output is correct
65 Correct 1414 ms 330992 KB Output is correct
66 Correct 1357 ms 330964 KB Output is correct
67 Correct 1509 ms 336624 KB Output is correct
68 Correct 1395 ms 332272 KB Output is correct
69 Correct 1320 ms 331464 KB Output is correct
70 Correct 1534 ms 337264 KB Output is correct
71 Correct 1405 ms 333104 KB Output is correct
72 Correct 1360 ms 332120 KB Output is correct
73 Correct 1604 ms 337360 KB Output is correct
74 Correct 1463 ms 333068 KB Output is correct
75 Correct 1420 ms 332068 KB Output is correct
76 Correct 1591 ms 338284 KB Output is correct
77 Correct 1518 ms 337016 KB Output is correct
78 Correct 1554 ms 337336 KB Output is correct
79 Correct 924 ms 15992 KB Output is correct
80 Correct 857 ms 14984 KB Output is correct
81 Correct 861 ms 14584 KB Output is correct
82 Correct 1619 ms 332776 KB Output is correct
83 Correct 1677 ms 332584 KB Output is correct
84 Correct 1545 ms 331628 KB Output is correct
85 Correct 1538 ms 331780 KB Output is correct
86 Correct 1553 ms 332272 KB Output is correct
87 Correct 1580 ms 332148 KB Output is correct
88 Correct 1073 ms 15836 KB Output is correct
89 Correct 1056 ms 15960 KB Output is correct
90 Correct 962 ms 14880 KB Output is correct
91 Correct 1031 ms 15168 KB Output is correct
92 Correct 1004 ms 14748 KB Output is correct
93 Correct 953 ms 14712 KB Output is correct
94 Correct 1278 ms 333772 KB Output is correct
95 Correct 1188 ms 332812 KB Output is correct
96 Correct 1228 ms 332656 KB Output is correct
97 Correct 1187 ms 331764 KB Output is correct
98 Correct 1229 ms 333256 KB Output is correct
99 Correct 1150 ms 332176 KB Output is correct
100 Correct 1086 ms 16120 KB Output is correct
101 Correct 1043 ms 16192 KB Output is correct
102 Correct 1025 ms 15100 KB Output is correct
103 Correct 1035 ms 14924 KB Output is correct
104 Correct 1039 ms 14856 KB Output is correct
105 Correct 1022 ms 14588 KB Output is correct
106 Correct 1470 ms 333808 KB Output is correct
107 Correct 1405 ms 333172 KB Output is correct
108 Correct 1410 ms 332792 KB Output is correct
109 Correct 1332 ms 331768 KB Output is correct
110 Correct 1402 ms 333424 KB Output is correct
111 Correct 1342 ms 332352 KB Output is correct
112 Correct 1002 ms 15940 KB Output is correct
113 Correct 1067 ms 15932 KB Output is correct
114 Correct 956 ms 14956 KB Output is correct
115 Correct 994 ms 14920 KB Output is correct
116 Correct 958 ms 14724 KB Output is correct
117 Correct 967 ms 14456 KB Output is correct
118 Correct 1517 ms 336700 KB Output is correct
119 Correct 1396 ms 332452 KB Output is correct
120 Correct 1351 ms 331460 KB Output is correct
121 Correct 1542 ms 336624 KB Output is correct
122 Correct 1421 ms 332484 KB Output is correct
123 Correct 1356 ms 331504 KB Output is correct
124 Correct 1519 ms 336532 KB Output is correct
125 Correct 1381 ms 332276 KB Output is correct
126 Correct 1334 ms 331340 KB Output is correct