QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#696373 | #6692. Building Company | 0x3fffffff | RE | 0ms | 3560kb | C++20 | 2.6kb | 2024-10-31 22:18:25 | 2024-10-31 22:18:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int g;cin >> g;
unordered_map<int, int>mp;
vector<int>t(g + 1), u(g + 1);
for (int i = 1;i <= g;i++) {
cin >> t[i] >> u[i];
mp[t[i]] = u[i];
}
int n;cin >> n;
vector<vector<int>>a(n + 1), b(n + 1), c(n + 1), d(n + 1);
vector<int>m(n + 1), k(n + 1);
for (int i = 1;i <= n;i++) {
cin >> m[i];
a[i].resize(m[i] + 1);
b[i].resize(m[i] + 1);
for (int j = 1;j <= m[i];j++) {
cin >> a[i][j] >> b[i][j];
}
cin >> k[i];
c[i].resize(k[i] + 1);
d[i].resize(k[i] + 1);
for (int j = 1;j <= k[i];j++) {
cin >> c[i][j] >> d[i][j];
}
}
map<int, multiset<pair<int, int>>>s;
vector<int>cnt(n + 1);
auto dfs = [&](auto&& ff, int u)->void {
while (!s[u].empty() and (*s[u].begin()).first <= mp[u]) {
auto it = s[u].begin();
int id = (*it).second;
cnt[id]--;
if (!cnt[id]) {
for (int t = 1;t <= k[id];t++) {
mp[c[id][t]] += d[id][t];
ff(ff, c[id][t]);
}
}
s[u].erase(it);
}
return;
};
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m[i];j++) {
if (mp[a[i][j]] < b[i][j]) {
cnt[i]++;
s[a[i][j]].emplace(b[i][j], i);
}
}
if (!cnt[i]) {
for (int j = 1;j <= k[i];j++) {
mp[c[i][j]] += d[i][j];
dfs(dfs, c[i][j]);
// while (!s[c[i][j]].empty() and (*s[c[i][j]].begin()).first <= mp[c[i][j]]) {
// auto it = s[c[i][j]].begin();
// int id = (*it).second;
// cnt[id]--;
// if (!cnt[id]) {
// for (int t = 1;t <= k[id];t++) {
// mp[c[id][t]] += d[id][t];
// }
// }
// s[c[i][j]].erase(it);
// }
}
}
}
int ans = 0;
for (int i = 1;i <= n;i++) {
if (!cnt[i])ans++;
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tt = 1;
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
// cin >> tt;
while (tt--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3560kb
input:
2 2 1 1 2 5 1 3 1 0 2 1 1 2 1 2 3 2 2 1 3 1 5 2 3 3 4 1 2 5 3 2 1 1 1 3 4 1 1 3 0 1 3 2
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: -100
Runtime Error
input:
3 610031727 590328742 816793299 18485566 654221125 47823436 10 3 610031727 224714165 816793299 491951703 654221125 593479446 1 610031727 538596643 1 610031727 551036304 3 816793299 262985484 610031727 52580932 654221125 424397787 1 654221125 889197190 3 654221125 126924193 610031727 963399336 816793...