oj.uz

Submission #971118

# Submission time Handle Problem Language Result Execution time Memory
971118 2024-04-28T02:15:28 Z THXuan Topical (NOI23_topical) C++14
40 / 100
 1000 ms 106004 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define INF 1e9
using namespace std;
typedef long long ll;

vector<pair<ll, ll>>x[1000005];

void solve()
{
	ll n, k; cin >> n >> k;
	vector<vector<ll>>v(n + 1, vector<ll>(k + 1));
	vector<vector<ll>>a(n + 1, vector<ll>(k + 1));
	int root = -1;
	for (int i = 0; i < n; i++) {
		bool flag = true;
		for (int j = 0; j < k; j++) {
			cin >> v[i][j];
			if (v[i][j] > 0)flag = false;
			x[j].push_back({ v[i][j], i });
		}
		if (flag) root = i;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < k; j++) {
			cin >> a[i][j];
		}
	}
	if (root == -1) { cout << 0 << "\n"; return; }
	for (int i = 0; i < k; i++) sort(x[i].begin(), x[i].end());
	queue<ll>q;
	q.push(root);
	ll ans = 0;
	vector<bool>visited(n, false);
	vector<ll>p(k);
	while (q.size()) {
		int node = q.front(); q.pop();
		if (visited[node])continue;
		visited[node] = true;
		++ans;
		map<ll, ll>seen;
		for (int i = 0; i < k; i++) {
			p[i] += a[node][i];
			int now = 0;
			while (now < x[i].size() && x[i][now].first <= p[i]) {
				seen[x[i][now].second]++;
				++now;
			}
		}
		for (auto u : seen) {
			if (u.second == k && !visited[u.first])q.push(u.first);
		}
	}
	cout << ans << "\n";
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;// cin>>t;
	while (t--) solve();
	return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |    while (now < x[i].size() && x[i][now].first <= p[i]) {
      |           ~~~~^~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23896 KB Output is correct
2 Correct 6 ms 23900 KB Output is correct
3 Correct 10 ms 24440 KB Output is correct
4 Correct 203 ms 106004 KB Output is correct
5 Correct 180 ms 105924 KB Output is correct
6 Correct 191 ms 106004 KB Output is correct
7 Correct 135 ms 92360 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 23900 KB Output is correct
2 Correct 6 ms 23912 KB Output is correct
3 Correct 5 ms 23900 KB Output is correct
4 Correct 8 ms 23900 KB Output is correct
5 Correct 6 ms 23896 KB Output is correct
6 Correct 6 ms 24052 KB Output is correct
7 Correct 13 ms 24524 KB Output is correct
8 Correct 23 ms 24412 KB Output is correct
9 Correct 10 ms 24412 KB Output is correct
10 Correct 22 ms 24412 KB Output is correct
11 Correct 16 ms 24412 KB Output is correct
12 Correct 13 ms 24280 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23928 KB Output is correct
2 Correct 7 ms 23916 KB Output is correct
3 Execution timed out 1071 ms 35744 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23896 KB Output is correct
2 Correct 6 ms 23900 KB Output is correct
3 Correct 10 ms 24440 KB Output is correct
4 Correct 203 ms 106004 KB Output is correct
5 Correct 180 ms 105924 KB Output is correct
6 Correct 191 ms 106004 KB Output is correct
7 Correct 135 ms 92360 KB Output is correct
8 Correct 7 ms 23900 KB Output is correct
9 Correct 6 ms 23912 KB Output is correct
10 Correct 5 ms 23900 KB Output is correct
11 Correct 8 ms 23900 KB Output is correct
12 Correct 6 ms 23896 KB Output is correct
13 Correct 6 ms 24052 KB Output is correct
14 Correct 13 ms 24524 KB Output is correct
15 Correct 23 ms 24412 KB Output is correct
16 Correct 10 ms 24412 KB Output is correct
17 Correct 22 ms 24412 KB Output is correct
18 Correct 16 ms 24412 KB Output is correct
19 Correct 13 ms 24280 KB Output is correct
20 Correct 6 ms 23928 KB Output is correct
21 Correct 7 ms 23916 KB Output is correct
22 Execution timed out 1071 ms 35744 KB Time limit exceeded
23 Halted 0 ms 0 KB -