답안 #87751 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
87751	2018-12-02T09:27:11 Z	JustInCase	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1989 ms	413224 KB

bitaro

/**
Solution:
	Idea: We can precompute for each node the sqrt(n) furthest nodes with a simple dp. Then for each query
if the number of forbidden nodes is less than sqrt(n) then for sure the answer will be among the precomputed
otherwise we can simply solve it with a brutefore since the queries of this type will be less than sqrt(n).
*/
#include <bits/stdc++.h>

const int32_t MAX_N = 1e5;
const int32_t BUCKET_SIZE = 300;
const int32_t INF = 2e9;

std::bitset< MAX_N + 5 > isInVector;
std::bitset< MAX_N + 5 > isForbidden;

std::vector< std::pair< int32_t, int32_t > > Merge(const std::vector< std::pair< int32_t, int32_t> > &v1, 
		const std::vector< std::pair< int32_t, int32_t > > &v2) {
	std::vector< std::pair< int32_t, int32_t > > ans;

	int32_t ind1 = 0, ind2 = 0;
	while((ind1 < v1.size() || ind2 < v2.size()) && ans.size() < BUCKET_SIZE) {
		if(ind1 < v1.size()) {
			if(ind2 < v2.size()) {
				if(v1[ind1].first >= v2[ind2].first + 1) {
					if(!isInVector[v1[ind1].second]) {
						isInVector[v1[ind1].second] = true;
						ans.push_back(v1[ind1]);
					}
					ind1++;
				}
				else {
					if(!isInVector[v2[ind2].second]) {
						isInVector[v2[ind2].second] = true;
						ans.push_back({ v2[ind2].first + 1, v2[ind2].second });
					}
					ind2++;
				}
			}
			else {
				if(!isInVector[v1[ind1].second]) {
					isInVector[v1[ind1].second] = true;
					ans.push_back(v1[ind1]);
				}
				ind1++;
			}
		}
		else {
			if(!isInVector[v2[ind2].second]) {
				isInVector[v2[ind2].second] = true;
				ans.push_back({ v2[ind2].first + 1, v2[ind2].second });
			}
			ind2++;
		}
	}

	for(auto &x : ans) {
		isInVector[x.second] = false;
	}

	return ans;
}

class Graph {
private:
	struct Node {
		int32_t id;
		std::vector< std::pair< int32_t, int32_t > > dp;
		std::vector< Node* > v;
	};

	int32_t cntNodes;
	Node nodes[MAX_N + 5];
	
public:
	void Init(int32_t _cntNodes) {
		cntNodes = _cntNodes;

		for(int32_t i = 1; i <= cntNodes; i++) {
			nodes[i].id = i;
		}
	}

	void AddEdge(int32_t from, int32_t to) {
		nodes[from].v.push_back(&nodes[to]);
	}

	void Precompute() {
		for(int32_t i = 1; i <= cntNodes; i++) {
			std::vector< std::pair< int32_t, int32_t > > dists;
			
			nodes[i].dp.push_back({ 0, i });
			for(auto &x : nodes[i].v) {
				nodes[i].dp = Merge(nodes[i].dp, x->dp);
			}
		}
	}

	int32_t SolveSmallK(int32_t t) {
		for(auto &x : nodes[t].dp) {
			if(!isForbidden[x.second]) {
				return x.first;
			}
		}

		return -1;
	}

	int32_t SolveBigK(int32_t t) {
		std::vector< int32_t > dp(t + 1, 0);

		for(int32_t i = 1; i <= t; i++) {
			if(isForbidden[i]) {
				dp[i] = -INF;
			}
			else {
				dp[i] = 0;
			}

			for(auto &x : nodes[i].v) {
				dp[i] = std::max(dp[i], dp[x->id] + 1);
			}
		}

		return std::max(dp[t], -1);
	}	
};

Graph g;

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int32_t n, m, q;
	std::cin >> n >> m >> q;

	g.Init(n);
	
	for(int32_t i = 0; i < m; i++) {
		int32_t u, v;
		std::cin >> u >> v;

		g.AddEdge(v, u);
	}
	
	g.Precompute();

	for(int32_t i = 0; i < q; i++) {
		int32_t t, k;
		std::cin >> t >> k;
	
		std::vector< int32_t > c(k);
		for(int32_t j = 0; j < k; j++) {
			std::cin >> c[j];

			isForbidden[c[j]] = true;
		}

		if(k >= BUCKET_SIZE) {
			std::cout << g.SolveBigK(t) << '\n';
		}
		else {
			std::cout << g.SolveSmallK(t) << '\n';
		}

		for(int32_t j = 0; j < k; j++) {
			isForbidden[c[j]] = false;
		}
	}
}

Compilation message

bitaro.cpp: In function 'std::vector<std::pair<int, int> > Merge(const std::vector<std::pair<int, int> >&, const std::vector<std::pair<int, int> >&)':
bitaro.cpp:21:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while((ind1 < v1.size() || ind2 < v2.size()) && ans.size() < BUCKET_SIZE) {
         ~~~~~^~~~~~~~~~~
bitaro.cpp:21:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while((ind1 < v1.size() || ind2 < v2.size()) && ans.size() < BUCKET_SIZE) {
                             ~~~~~^~~~~~~~~~~
bitaro.cpp:22:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ind1 < v1.size()) {
      ~~~~~^~~~~~~~~~~
bitaro.cpp:23:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ind2 < v2.size()) {
       ~~~~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5752 KB	Output is correct
2	Correct	7 ms	5876 KB	Output is correct
3	Correct	7 ms	5876 KB	Output is correct
4	Correct	8 ms	5912 KB	Output is correct
5	Correct	14 ms	6484 KB	Output is correct
6	Correct	13 ms	6560 KB	Output is correct
7	Correct	11 ms	6708 KB	Output is correct
8	Correct	23 ms	9372 KB	Output is correct
9	Correct	23 ms	9440 KB	Output is correct
10	Correct	23 ms	9440 KB	Output is correct
11	Correct	22 ms	9440 KB	Output is correct
12	Correct	16 ms	9440 KB	Output is correct
13	Correct	22 ms	9440 KB	Output is correct
14	Correct	20 ms	9440 KB	Output is correct
15	Correct	13 ms	9440 KB	Output is correct
16	Correct	20 ms	9440 KB	Output is correct
17	Correct	19 ms	9440 KB	Output is correct
18	Correct	15 ms	9440 KB	Output is correct
19	Correct	19 ms	9440 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5752 KB	Output is correct
2	Correct	7 ms	5876 KB	Output is correct
3	Correct	7 ms	5876 KB	Output is correct
4	Correct	8 ms	5912 KB	Output is correct
5	Correct	14 ms	6484 KB	Output is correct
6	Correct	13 ms	6560 KB	Output is correct
7	Correct	11 ms	6708 KB	Output is correct
8	Correct	23 ms	9372 KB	Output is correct
9	Correct	23 ms	9440 KB	Output is correct
10	Correct	23 ms	9440 KB	Output is correct
11	Correct	22 ms	9440 KB	Output is correct
12	Correct	16 ms	9440 KB	Output is correct
13	Correct	22 ms	9440 KB	Output is correct
14	Correct	20 ms	9440 KB	Output is correct
15	Correct	13 ms	9440 KB	Output is correct
16	Correct	20 ms	9440 KB	Output is correct
17	Correct	19 ms	9440 KB	Output is correct
18	Correct	15 ms	9440 KB	Output is correct
19	Correct	19 ms	9440 KB	Output is correct
20	Correct	847 ms	11696 KB	Output is correct
21	Correct	777 ms	11696 KB	Output is correct
22	Correct	854 ms	11744 KB	Output is correct
23	Correct	903 ms	11744 KB	Output is correct
24	Correct	1483 ms	253520 KB	Output is correct
25	Correct	1605 ms	265036 KB	Output is correct
26	Correct	1364 ms	265036 KB	Output is correct
27	Correct	1507 ms	412440 KB	Output is correct
28	Correct	1517 ms	412484 KB	Output is correct
29	Correct	1534 ms	412640 KB	Output is correct
30	Correct	1548 ms	412640 KB	Output is correct
31	Correct	1501 ms	412640 KB	Output is correct
32	Correct	1447 ms	412640 KB	Output is correct
33	Correct	1180 ms	412640 KB	Output is correct
34	Correct	1052 ms	412640 KB	Output is correct
35	Correct	1162 ms	412640 KB	Output is correct
36	Correct	1381 ms	412640 KB	Output is correct
37	Correct	1385 ms	412640 KB	Output is correct
38	Correct	1485 ms	412640 KB	Output is correct

Subtask #3
86.0 / 86.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5752 KB	Output is correct
2	Correct	7 ms	5876 KB	Output is correct
3	Correct	7 ms	5876 KB	Output is correct
4	Correct	8 ms	5912 KB	Output is correct
5	Correct	14 ms	6484 KB	Output is correct
6	Correct	13 ms	6560 KB	Output is correct
7	Correct	11 ms	6708 KB	Output is correct
8	Correct	23 ms	9372 KB	Output is correct
9	Correct	23 ms	9440 KB	Output is correct
10	Correct	23 ms	9440 KB	Output is correct
11	Correct	22 ms	9440 KB	Output is correct
12	Correct	16 ms	9440 KB	Output is correct
13	Correct	22 ms	9440 KB	Output is correct
14	Correct	20 ms	9440 KB	Output is correct
15	Correct	13 ms	9440 KB	Output is correct
16	Correct	20 ms	9440 KB	Output is correct
17	Correct	19 ms	9440 KB	Output is correct
18	Correct	15 ms	9440 KB	Output is correct
19	Correct	19 ms	9440 KB	Output is correct
20	Correct	847 ms	11696 KB	Output is correct
21	Correct	777 ms	11696 KB	Output is correct
22	Correct	854 ms	11744 KB	Output is correct
23	Correct	903 ms	11744 KB	Output is correct
24	Correct	1483 ms	253520 KB	Output is correct
25	Correct	1605 ms	265036 KB	Output is correct
26	Correct	1364 ms	265036 KB	Output is correct
27	Correct	1507 ms	412440 KB	Output is correct
28	Correct	1517 ms	412484 KB	Output is correct
29	Correct	1534 ms	412640 KB	Output is correct
30	Correct	1548 ms	412640 KB	Output is correct
31	Correct	1501 ms	412640 KB	Output is correct
32	Correct	1447 ms	412640 KB	Output is correct
33	Correct	1180 ms	412640 KB	Output is correct
34	Correct	1052 ms	412640 KB	Output is correct
35	Correct	1162 ms	412640 KB	Output is correct
36	Correct	1381 ms	412640 KB	Output is correct
37	Correct	1385 ms	412640 KB	Output is correct
38	Correct	1485 ms	412640 KB	Output is correct
39	Correct	1809 ms	412640 KB	Output is correct
40	Correct	1807 ms	412640 KB	Output is correct
41	Correct	1842 ms	412640 KB	Output is correct
42	Correct	1676 ms	412640 KB	Output is correct
43	Correct	1587 ms	412640 KB	Output is correct
44	Correct	897 ms	412640 KB	Output is correct
45	Correct	852 ms	412640 KB	Output is correct
46	Correct	881 ms	412640 KB	Output is correct
47	Correct	869 ms	412640 KB	Output is correct
48	Correct	868 ms	412640 KB	Output is correct
49	Correct	1989 ms	412640 KB	Output is correct
50	Correct	1888 ms	412640 KB	Output is correct
51	Correct	839 ms	412640 KB	Output is correct
52	Correct	819 ms	412640 KB	Output is correct
53	Correct	1790 ms	412640 KB	Output is correct
54	Correct	1666 ms	412640 KB	Output is correct
55	Correct	1688 ms	412640 KB	Output is correct
56	Correct	1650 ms	412640 KB	Output is correct
57	Correct	889 ms	412640 KB	Output is correct
58	Correct	914 ms	412640 KB	Output is correct
59	Correct	856 ms	412640 KB	Output is correct
60	Correct	856 ms	412640 KB	Output is correct
61	Correct	1712 ms	412640 KB	Output is correct
62	Correct	1647 ms	412640 KB	Output is correct
63	Correct	1552 ms	412640 KB	Output is correct
64	Correct	1918 ms	412892 KB	Output is correct
65	Correct	1877 ms	412892 KB	Output is correct
66	Correct	1932 ms	412892 KB	Output is correct
67	Correct	1908 ms	412892 KB	Output is correct
68	Correct	1733 ms	412892 KB	Output is correct
69	Correct	1633 ms	412892 KB	Output is correct
70	Correct	1638 ms	412964 KB	Output is correct
71	Correct	1488 ms	412964 KB	Output is correct
72	Correct	1341 ms	412964 KB	Output is correct
73	Correct	1534 ms	413076 KB	Output is correct
74	Correct	1449 ms	413076 KB	Output is correct
75	Correct	1445 ms	413076 KB	Output is correct
76	Correct	1857 ms	413224 KB	Output is correct
77	Correct	1819 ms	413224 KB	Output is correct
78	Correct	1661 ms	413224 KB	Output is correct
79	Correct	844 ms	413224 KB	Output is correct
80	Correct	845 ms	413224 KB	Output is correct
81	Correct	777 ms	413224 KB	Output is correct
82	Correct	1838 ms	413224 KB	Output is correct
83	Correct	1852 ms	413224 KB	Output is correct
84	Correct	1756 ms	413224 KB	Output is correct
85	Correct	1817 ms	413224 KB	Output is correct
86	Correct	1489 ms	413224 KB	Output is correct
87	Correct	1631 ms	413224 KB	Output is correct
88	Correct	905 ms	413224 KB	Output is correct
89	Correct	891 ms	413224 KB	Output is correct
90	Correct	826 ms	413224 KB	Output is correct
91	Correct	865 ms	413224 KB	Output is correct
92	Correct	848 ms	413224 KB	Output is correct
93	Correct	842 ms	413224 KB	Output is correct
94	Correct	1412 ms	413224 KB	Output is correct
95	Correct	1204 ms	413224 KB	Output is correct
96	Correct	1379 ms	413224 KB	Output is correct
97	Correct	1267 ms	413224 KB	Output is correct
98	Correct	1212 ms	413224 KB	Output is correct
99	Correct	1058 ms	413224 KB	Output is correct
100	Correct	902 ms	413224 KB	Output is correct
101	Correct	894 ms	413224 KB	Output is correct
102	Correct	866 ms	413224 KB	Output is correct
103	Correct	898 ms	413224 KB	Output is correct
104	Correct	877 ms	413224 KB	Output is correct
105	Correct	886 ms	413224 KB	Output is correct
106	Correct	1683 ms	413224 KB	Output is correct
107	Correct	1645 ms	413224 KB	Output is correct
108	Correct	1594 ms	413224 KB	Output is correct
109	Correct	1509 ms	413224 KB	Output is correct
110	Correct	1389 ms	413224 KB	Output is correct
111	Correct	1397 ms	413224 KB	Output is correct
112	Correct	881 ms	413224 KB	Output is correct
113	Correct	902 ms	413224 KB	Output is correct
114	Correct	840 ms	413224 KB	Output is correct
115	Correct	889 ms	413224 KB	Output is correct
116	Correct	830 ms	413224 KB	Output is correct
117	Correct	868 ms	413224 KB	Output is correct
118	Correct	1886 ms	413224 KB	Output is correct
119	Correct	1588 ms	413224 KB	Output is correct
120	Correct	1640 ms	413224 KB	Output is correct
121	Correct	1826 ms	413224 KB	Output is correct
122	Correct	1635 ms	413224 KB	Output is correct
123	Correct	1501 ms	413224 KB	Output is correct
124	Correct	1772 ms	413224 KB	Output is correct
125	Correct	1715 ms	413224 KB	Output is correct
126	Correct	1577 ms	413224 KB	Output is correct

답안 #87751

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 7.0 / 7.0

Subtask #3 86.0 / 86.0

Subtask #1
7.0 / 7.0

Subtask #2
7.0 / 7.0

Subtask #3
86.0 / 86.0