QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#387530#3729. 有向无环图ucup-team1251WA 1ms7792kbC++171.1kb2024-04-12 16:27:332024-04-12 16:27:33

Judging History

This is the latest submission verdict.

  • [2024-04-12 16:27:33]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 7792kb
  • [2024-04-12 16:27:33]
  • Submitted

answer

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<math.h>
#include<set>
#include<bitset>
#include<deque>
#include<unordered_map>
#include<algorithm>
#define int long long
using namespace std;
typedef pair<int,int>PII;
const int N=1e5+10,M=5e2+10;
const int mod=1e9+7;
int n,m;
vector<int>v[N];
int sum[N],ru[N];
int ans;

struct le{
	int a,b;
}ll[N];

signed main(){
	ios::sync_with_stdio(false);
	cin.tie();
	cout.tie();
	while(cin>>n>>m){
		for(int i=1;i<=n;i++){
			cin>>ll[i].a>>ll[i].b;
			sum[i]=ll[i].a;
			ru[i]=0;
			v[i].clear();
		}
		for(int i=1;i<=m;i++){
			int x,y;
			cin>>x>>y;
			v[x].push_back(y);
			ru[y]++;
		}
		queue<int>q;
		for(int i=1;i<=n;i++){
			if(ru[i]==0) q.push(i);
		}
		ans=0;
		while(!q.empty()){
			int no=q.front();
			q.pop();
			int pp=v[no].size();
			for(int i=0;i<pp;i++){
				int oo=v[no][i];
				ans=(ans+sum[no]*ll[oo].b%mod)%mod;
				sum[oo]=(sum[no]+ll[oo].a)%mod;
				ru[oo]--;
				if(ru[oo]==0) q.push(oo);
			}
		}
//		for(int i=1;i<=n;i++) cout<<sum[i]<<endl;
		cout<<ans<<endl;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 7792kb

input:

100 1000
319004917 684910821
907666796 361501921
990110346 495921276
951755324 22154474
277941981 203276467
905615968 591029035
471506063 837795091
234419550 64665515
765300844 909483732
703958148 563691443
58282301 229501700
780981783 452543212
501031483 72941519
351050915 172139575
820012246 85422...

output:

357706997

result:

wrong answer 1st numbers differ - expected: '34927818', found: '357706997'