oj.uz

Submission #95150

# Submission time Handle Problem Language Result Execution time Memory
95150 2019-01-27T16:10:45 Z szawinis Bitaro’s Party (JOI18_bitaro) C++17
100 / 100
 1518 ms 260564 KB 
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <bits/stdc++.h>
using namespace std;
#define long long long
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int MAGIC = 320, N = 1e5+1;

class Bitaro {
	int n, m, q, indeg[N];
	vector<int> adj[N];
	pair<int,int> dp[N][MAGIC], dp2[N];
	bool blocked[N], mark[N];

	void naive() {
		fill(dp2, dp2+n+1, make_pair(-INF, -1));
		for(int u = 1; u <= n; u++) {
			if(!blocked[u]) dp2[u] = {0, u};
			for(int v: adj[u]) if(dp2[v].first + 1 > dp2[u].first) {
				dp2[u] = {dp2[v].first + 1, dp2[v].second};
			}
		}
	}

	void preprocess() {
		for(int i = 1; i <= n; i++) for(int j = 0; j < MAGIC; j++) dp[i][j] = {-INF, -1};
		for(int u = 1; u <= n; u++) {
			dp[u][0] = {0, u};
			for(int v: adj[u]) {
				pair<int,int> tmp[2*MAGIC], tmp2[MAGIC];
				int i = 0, j = 0, idx = 0;
				while(idx < 2*MAGIC) {
					if(j == MAGIC || dp[u][i].first > dp[v][j].first + 1) tmp[idx++] = dp[u][i++];
					else {
						tmp[idx++] = make_pair(dp[v][j].first + 1, dp[v][j].second);
						++j;
					}
				}
				idx = 0;
				for(int i = 0; i < 2*MAGIC; i++) {
					if(tmp[i].second != -1 && mark[tmp[i].second]) continue;
					if(tmp[i].second != -1) mark[tmp[i].second] = true;
					if(idx < MAGIC) tmp2[idx++] = tmp[i];
				}
				for(int i = 0; i < 2*MAGIC; i++) mark[tmp[i].second] = false;
				copy(tmp2, tmp2+MAGIC, dp[u]);
			}
//			cout << "dp[u] " << u << endl;
//			for(int i = 0; i < MAGIC; i++) cout << dp[u][i].first << ' ' << dp[u][i].second << endl;
//			cout << endl;
		}
	}

public:
	void solve(istream &cin, ostream &cout) {
		cin >> n >> m >> q;
		for(int i = 0, s, e; i < m; i++) {
			cin >> s >> e;
			adj[e].push_back(s);
//			++indeg[e];
		}
		preprocess();
		for(int i = 0, T, Y; i < q; i++) {
			cin >> T >> Y;
			vector<int> ls(Y);
			for(int j = 0, v; j < Y; j++) {
				cin >> ls[j];
				blocked[ls[j]] = true;
			}
			if(Y >= MAGIC) {
				naive();
				cout << (dp2[T].first < 0 ? -1 : dp2[T].first) << '\n';
			} else {
				bool found = false;
				for(int i = 0; i < MAGIC; i++) if(dp[T][i].second != -1 && !blocked[dp[T][i].second]) {
					cout << dp[T][i].first << '\n';
					found = true;
					break;
				}
				if(!found) cout << -1 << '\n';
			}
			for(int v: ls) blocked[v] = false;
		}
	}
};

class Solver {
public:
	void solve(std::istream& in, std::ostream& out) {
	    Bitaro *obj = new Bitaro();
		obj->solve(in, out);
		delete obj;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	Solver solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

Compilation message

bitaro.cpp: In member function 'void Bitaro::solve(std::istream&, std::ostream&)':
bitaro.cpp:73:19: warning: unused variable 'v' [-Wunused-variable]
    for(int j = 0, v; j < Y; j++) {
                   ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 254584 KB Output is correct
2 Correct 271 ms 254584 KB Output is correct
3 Correct 268 ms 254812 KB Output is correct
4 Correct 216 ms 254584 KB Output is correct
5 Correct 222 ms 254712 KB Output is correct
6 Correct 224 ms 254712 KB Output is correct
7 Correct 221 ms 254576 KB Output is correct
8 Correct 220 ms 254584 KB Output is correct
9 Correct 259 ms 254636 KB Output is correct
10 Correct 241 ms 254764 KB Output is correct
11 Correct 275 ms 254612 KB Output is correct
12 Correct 272 ms 254584 KB Output is correct
13 Correct 274 ms 254712 KB Output is correct
14 Correct 274 ms 254652 KB Output is correct
15 Correct 273 ms 254584 KB Output is correct
16 Correct 275 ms 254796 KB Output is correct
17 Correct 275 ms 254712 KB Output is correct
18 Correct 272 ms 254712 KB Output is correct
19 Correct 275 ms 254712 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 254584 KB Output is correct
2 Correct 271 ms 254584 KB Output is correct
3 Correct 268 ms 254812 KB Output is correct
4 Correct 216 ms 254584 KB Output is correct
5 Correct 222 ms 254712 KB Output is correct
6 Correct 224 ms 254712 KB Output is correct
7 Correct 221 ms 254576 KB Output is correct
8 Correct 220 ms 254584 KB Output is correct
9 Correct 259 ms 254636 KB Output is correct
10 Correct 241 ms 254764 KB Output is correct
11 Correct 275 ms 254612 KB Output is correct
12 Correct 272 ms 254584 KB Output is correct
13 Correct 274 ms 254712 KB Output is correct
14 Correct 274 ms 254652 KB Output is correct
15 Correct 273 ms 254584 KB Output is correct
16 Correct 275 ms 254796 KB Output is correct
17 Correct 275 ms 254712 KB Output is correct
18 Correct 272 ms 254712 KB Output is correct
19 Correct 275 ms 254712 KB Output is correct
20 Correct 1037 ms 256860 KB Output is correct
21 Correct 878 ms 256760 KB Output is correct
22 Correct 1029 ms 256888 KB Output is correct
23 Correct 1083 ms 256760 KB Output is correct
24 Correct 1210 ms 258680 KB Output is correct
25 Correct 1223 ms 258772 KB Output is correct
26 Correct 1157 ms 258664 KB Output is correct
27 Correct 861 ms 259028 KB Output is correct
28 Correct 861 ms 259192 KB Output is correct
29 Correct 886 ms 259216 KB Output is correct
30 Correct 888 ms 259164 KB Output is correct
31 Correct 1006 ms 259320 KB Output is correct
32 Correct 855 ms 259192 KB Output is correct
33 Correct 992 ms 258636 KB Output is correct
34 Correct 943 ms 258168 KB Output is correct
35 Correct 871 ms 257528 KB Output is correct
36 Correct 886 ms 257656 KB Output is correct
37 Correct 1022 ms 257640 KB Output is correct
38 Correct 1008 ms 257528 KB Output is correct

Subtask #3
86.0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 254584 KB Output is correct
2 Correct 271 ms 254584 KB Output is correct
3 Correct 268 ms 254812 KB Output is correct
4 Correct 216 ms 254584 KB Output is correct
5 Correct 222 ms 254712 KB Output is correct
6 Correct 224 ms 254712 KB Output is correct
7 Correct 221 ms 254576 KB Output is correct
8 Correct 220 ms 254584 KB Output is correct
9 Correct 259 ms 254636 KB Output is correct
10 Correct 241 ms 254764 KB Output is correct
11 Correct 275 ms 254612 KB Output is correct
12 Correct 272 ms 254584 KB Output is correct
13 Correct 274 ms 254712 KB Output is correct
14 Correct 274 ms 254652 KB Output is correct
15 Correct 273 ms 254584 KB Output is correct
16 Correct 275 ms 254796 KB Output is correct
17 Correct 275 ms 254712 KB Output is correct
18 Correct 272 ms 254712 KB Output is correct
19 Correct 275 ms 254712 KB Output is correct
20 Correct 1037 ms 256860 KB Output is correct
21 Correct 878 ms 256760 KB Output is correct
22 Correct 1029 ms 256888 KB Output is correct
23 Correct 1083 ms 256760 KB Output is correct
24 Correct 1210 ms 258680 KB Output is correct
25 Correct 1223 ms 258772 KB Output is correct
26 Correct 1157 ms 258664 KB Output is correct
27 Correct 861 ms 259028 KB Output is correct
28 Correct 861 ms 259192 KB Output is correct
29 Correct 886 ms 259216 KB Output is correct
30 Correct 888 ms 259164 KB Output is correct
31 Correct 1006 ms 259320 KB Output is correct
32 Correct 855 ms 259192 KB Output is correct
33 Correct 992 ms 258636 KB Output is correct
34 Correct 943 ms 258168 KB Output is correct
35 Correct 871 ms 257528 KB Output is correct
36 Correct 886 ms 257656 KB Output is correct
37 Correct 1022 ms 257640 KB Output is correct
38 Correct 1008 ms 257528 KB Output is correct
39 Correct 1262 ms 257784 KB Output is correct
40 Correct 1236 ms 257416 KB Output is correct
41 Correct 1168 ms 257528 KB Output is correct
42 Correct 1348 ms 257548 KB Output is correct
43 Correct 1105 ms 257400 KB Output is correct
44 Correct 1006 ms 256104 KB Output is correct
45 Correct 1016 ms 255992 KB Output is correct
46 Correct 1080 ms 257632 KB Output is correct
47 Correct 1059 ms 257400 KB Output is correct
48 Correct 1000 ms 257400 KB Output is correct
49 Correct 1040 ms 260252 KB Output is correct
50 Correct 991 ms 259988 KB Output is correct
51 Correct 929 ms 258296 KB Output is correct
52 Correct 839 ms 257528 KB Output is correct
53 Correct 973 ms 259880 KB Output is correct
54 Correct 1126 ms 259704 KB Output is correct
55 Correct 995 ms 259380 KB Output is correct
56 Correct 1121 ms 259396 KB Output is correct
57 Correct 1057 ms 258296 KB Output is correct
58 Correct 1123 ms 258128 KB Output is correct
59 Correct 1010 ms 257672 KB Output is correct
60 Correct 975 ms 257656 KB Output is correct
61 Correct 1091 ms 259788 KB Output is correct
62 Correct 1271 ms 259516 KB Output is correct
63 Correct 1353 ms 259400 KB Output is correct
64 Correct 1133 ms 259832 KB Output is correct
65 Correct 1444 ms 259436 KB Output is correct
66 Correct 1518 ms 259480 KB Output is correct
67 Correct 906 ms 259980 KB Output is correct
68 Correct 899 ms 259396 KB Output is correct
69 Correct 992 ms 259348 KB Output is correct
70 Correct 911 ms 259832 KB Output is correct
71 Correct 1055 ms 259448 KB Output is correct
72 Correct 1091 ms 259448 KB Output is correct
73 Correct 1004 ms 259900 KB Output is correct
74 Correct 1115 ms 259448 KB Output is correct
75 Correct 1104 ms 259576 KB Output is correct
76 Correct 918 ms 260564 KB Output is correct
77 Correct 944 ms 259956 KB Output is correct
78 Correct 1000 ms 259960 KB Output is correct
79 Correct 903 ms 258296 KB Output is correct
80 Correct 919 ms 257668 KB Output is correct
81 Correct 852 ms 257248 KB Output is correct
82 Correct 1057 ms 260344 KB Output is correct
83 Correct 1026 ms 260364 KB Output is correct
84 Correct 938 ms 259960 KB Output is correct
85 Correct 999 ms 260088 KB Output is correct
86 Correct 963 ms 259960 KB Output is correct
87 Correct 1167 ms 260020 KB Output is correct
88 Correct 1008 ms 258296 KB Output is correct
89 Correct 968 ms 258424 KB Output is correct
90 Correct 945 ms 257700 KB Output is correct
91 Correct 974 ms 257656 KB Output is correct
92 Correct 928 ms 257400 KB Output is correct
93 Correct 966 ms 257400 KB Output is correct
94 Correct 933 ms 260144 KB Output is correct
95 Correct 1138 ms 259972 KB Output is correct
96 Correct 974 ms 259572 KB Output is correct
97 Correct 1083 ms 259552 KB Output is correct
98 Correct 1043 ms 259704 KB Output is correct
99 Correct 1119 ms 259704 KB Output is correct
100 Correct 1166 ms 258336 KB Output is correct
101 Correct 1106 ms 258424 KB Output is correct
102 Correct 1103 ms 257660 KB Output is correct
103 Correct 1080 ms 257716 KB Output is correct
104 Correct 1049 ms 257288 KB Output is correct
105 Correct 1012 ms 257400 KB Output is correct
106 Correct 965 ms 260112 KB Output is correct
107 Correct 1076 ms 259916 KB Output is correct
108 Correct 906 ms 259704 KB Output is correct
109 Correct 1034 ms 259704 KB Output is correct
110 Correct 952 ms 259704 KB Output is correct
111 Correct 1016 ms 259832 KB Output is correct
112 Correct 984 ms 258552 KB Output is correct
113 Correct 1055 ms 258552 KB Output is correct
114 Correct 978 ms 257656 KB Output is correct
115 Correct 983 ms 257636 KB Output is correct
116 Correct 1026 ms 257400 KB Output is correct
117 Correct 1010 ms 257400 KB Output is correct
118 Correct 1000 ms 260188 KB Output is correct
119 Correct 1018 ms 259832 KB Output is correct
120 Correct 1035 ms 259832 KB Output is correct
121 Correct 933 ms 260216 KB Output is correct
122 Correct 1045 ms 259832 KB Output is correct
123 Correct 964 ms 259812 KB Output is correct
124 Correct 918 ms 260216 KB Output is correct
125 Correct 1018 ms 259960 KB Output is correct
126 Correct 1141 ms 259828 KB Output is correct