QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#412181#6692. Building CompanyxiaoleWA 1ms3496kbC++232.0kb2024-05-16 10:05:292024-05-16 10:05:30

Judging History

你现在查看的是最新测评结果

  • [2024-05-16 10:05:30]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3496kb
  • [2024-05-16 10:05:29]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'