QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#252276 | #6692. Building Company | shiroi | WA | 0ms | 31396kb | C++14 | 1.6kb | 2023-11-15 17:33:40 | 2023-11-15 17:33:40 |
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];
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(int t)
{
while(!req[t].empty() && req[t].back().first<=wcnt[t])
{
int proj=req[t].back().second;
--mcnt[proj]; req[t].pop_back();
if(mcnt[proj]==0) q.push(proj);
}
}
inline void toposort()
{
for(int i=1; i<=tot; ++i) checktype(i);
for(int i=1; i<=n; ++i)
if(mcnt[i]==0) q.push(i);
while(!q.empty())
{
int 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(int i=1; i<=g; ++i)
{
int t=read(),u=read();
if(!mp[t]) mp[t]=++tot;
wcnt[mp[t]]=u;
}
n=read();
for(int i=1; i<=n; ++i)
{
mcnt[i]=read();
for(int j=1; j<=mcnt[i]; ++j)
{
int t=read(),u=read();
if(!mp[t]) mp[t]=++tot;
req[mp[t]].push_back(make_pair(u,i));
}
rwcnt[i]=read();
for(int j=1; j<=rwcnt[i]; ++j)
{
int t=read(),u=read();
if(!mp[t]) mp[t]=++tot;
rwd[i].push_back(make_pair(mp[t],u));
}
}
for(int i=1; i<=tot; ++i)
sort(req[i].begin(), req[i].end(), cmp);
toposort();
printf("%lld\n", ans);
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 31396kb
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:
6
result:
wrong answer 1st numbers differ - expected: '4', found: '6'