QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#252284 | #6692. Building Company | shiroi | WA | 3ms | 35008kb | C++14 | 1.7kb | 2023-11-15 17:39:15 | 2023-11-15 17:39:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1,c=getchar();
while(c<48) c=='-'&&(f=-1),c=getchar();
while(c>47) x=x*10+c-'0',c=getchar();
return x*f;
}
typedef long long ll;
typedef pair<ll,ll> pll;
const int MAXN = 500005;
std::vector<pll> req[MAXN],rwd[MAXN];
ll wcnt[MAXN],mcnt[MAXN],rwcnt[MAXN],top[MAXN];
std::unordered_map<int,int> mp;
queue<ll> q;
ll n,g,ans,tot;
inline bool cmp(pll a,pll b)
{
return a.first!=b.first ? a.first > b.first : a.second>b.second;
}
inline void checktype(ll t)
{
while(top[t] && req[t][top[t]].first<=wcnt[t])
{
ll proj=req[t][top[t]].second;
--mcnt[proj]; req[t].pop_back(); --top[t];
if(mcnt[proj]==0) q.push(proj);
}
}
inline void toposort()
{
for(ll i=1; i<=tot; ++i) checktype(i);
for(ll i=1; i<=n; ++i)
if(mcnt[i]==0) q.push(i);
while(!q.empty())
{
ll x=q.front(); q.pop(); ++ans;
for(auto t : rwd[x])
{
wcnt[t.first]+=t.second;
checktype(t.first);
}
}
}
int main(int argc, char const *argv[])
{
g=read();
for(ll i=1; i<=g; ++i)
{
ll t=read(),u=read();
if(!mp[t]) mp[t]=++tot;
wcnt[mp[t]]=u;
}
n=read();
for(ll i=1; i<=n; ++i)
{
mcnt[i]=read();
for(ll j=1; j<=mcnt[i]; ++j)
{
ll t=read(),u=read();
if(!mp[t]) mp[t]=++tot;
req[mp[t]].push_back(make_pair(u,i));
}
rwcnt[i]=read();
for(ll j=1; j<=rwcnt[i]; ++j)
{
ll t=read(),u=read();
if(!mp[t]) mp[t]=++tot;
rwd[i].push_back(make_pair(mp[t],u));
}
}
for(ll i=1; i<=tot; ++i)
{
sort(req[i].begin(), req[i].end(), cmp);
top[i]=req[i].size()-1;
}
toposort();
printf("%lld\n", ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 34968kb
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: 3ms
memory: 35008kb
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:
9
result:
wrong answer 1st numbers differ - expected: '10', found: '9'