QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#252284#6692. Building CompanyshiroiWA 3ms35008kbC++141.7kb2023-11-15 17:39:152023-11-15 17:39:15

Judging History

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

  • [2023-11-15 17:39:15]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:35008kb
  • [2023-11-15 17:39:15]
  • 提交

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'