QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#412181 | #6692. Building Company | xiaole | WA | 1ms | 3496kb | C++23 | 2.0kb | 2024-05-16 10:05:29 | 2024-05-16 10:05:30 |
Judging History
answer
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;using ll = long long;using PLL = pair<ll,ll>;
const ll MAX = 1e18;const ll MIN = -1e18;const ll INF=0x3f3f3f3f;
const ll Q = 2e5+9;const ll MOD = 1e9 + 7;
struct cmp
{
bool operator()(pair<ll,ll> l,pair<ll,ll> r){
return l.second>r.second;
}
};
unordered_map<ll,priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,cmp>> pq;//每个工种需求的项目号和人数
unordered_map<ll,ll> mp;//一开始的工种和人数
unordered_map<ll,ll> vis;//当前项目还缺的工种
vector<pair<ll,ll>> t[Q];
void solve(){
ll g;cin>>g;
for (ll i = 1; i <= g; i++)
{
ll o,p;cin>>o>>p;
mp[o]+=p;
}
ll n;cin>>n;
for (ll i = 1; i <= n; i++)
{
ll m;cin>>m;
for (ll j = 0; j < m; j++)
{
ll o,p;cin>>o>>p;
if(mp[o]<p){
pq[o].push({i,p-mp[o]});//工种 对应项目和缺失人数
vis[i]++;//项目缺失工种数
}
}
cin>>m;
for (ll j = 0; j < m; j++)
{
ll o,p;cin>>o>>p;
t[i].push_back({o,p});
}
}
ll ans=0;
queue<ll> q;
for (ll i = 1; i <= n; i++)
if(vis[i]==0) q.push(i);//缺失人数为0时 加入
while(q.size()){
ll o=q.front();
q.pop();
for (ll i = 0; i < t[o].size(); i++)
{
ll l=t[o][i].first,r=t[o][i].second;//l是工种 r是人数
mp[l]+=r;
while(pq[l].size() and pq[l].top().second<=mp[l]){
vis[pq[l].top().first]--;
pq[l].pop();
if(vis[pq[l].top().first]==0){
q.push(pq[l].top().first);
q.pop();
}
}
}
}
for (ll i = 1; i <= n; i++)
{
//cout<<vis[i]<<" ";
if(vis[i]==0){
ans++;
}
}
cout<<ans<<"\n";
}
int main(){
ios;ll _=1;//cin>>_;
while (_--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3496kb
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
Wrong Answer
time: 1ms
memory: 3424kb
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...
output:
6
result:
wrong answer 1st numbers differ - expected: '10', found: '6'