# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
971119 | THXuan | Topical (NOI23_topical) | C++14 | 1065 ms | 146476 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
vector<ll>seen(n);
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 (int i = 0; i < n; i++) {
if (seen[i] == k && !visited[i])q.push(i);
}
}
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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |