QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#252276#6692. Building CompanyshiroiWA 0ms31396kbC++141.6kb2023-11-15 17:33:402023-11-15 17:33:40

Judging History

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

  • [2023-11-15 17:33:40]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:31396kb
  • [2023-11-15 17:33:40]
  • 提交

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'