QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#387509 | #3729. 有向无环图 | wanyu | WA | 391ms | 9896kb | C++17 | 1.8kb | 2024-04-12 16:09:38 | 2024-04-12 16:09:38 |
Judging History
answer
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <bitset>
#include <cstdio>
#include <string>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#define int long long
#define lowbit(x) x&(-x)
#define pi 3.14159265358
#define lc k<<1;
#define rc k<<1|1
#define ppb push_back
#define mod 1000000007
#define fori(i,l,r) for(int i=l;i<=r;i++)
#define forj(j,l,r) for(int j=l;j<=r;j++)
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
typedef pair <int, int> pll;
const int N = 2e6 + 10;
const int P = 131;
int n, m;
int a[N], b[N];
int sum[N];
vector<vector<int>>g(100010);
int ans;
int d[N];
map<pair<int, int>, int>z, mp;
vector<int>v;
void dfs(int u, int fa, int su) {
for (auto x : g[u]) {
if (x == fa) continue;
if (mp[ {u, x}] == 1) {
su *= z[ {u, x}];
ans = (ans + (su % mod * b[x]) % mod) % mod;
dfs(x, u, su);
} else {
mp[ {u, x}] = 1;
ans = (ans + ((su + a[u]) * (z[ {u, x}]) % mod * b[x]) % mod) % mod;
// cout<<su<<" -- "<<x<<"****\n";
dfs(x, u, (su * (z[ {u, x}]) + a[u]) % mod);
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie();
cout.tie();
while (cin >> n >> m) {
mp.clear();
v.clear();
z.clear();
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
d[i] = 0;
g[i].clear();
}
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
if (z[ {u, v}]) {
z[ {u, v}]++;
continue;
}
d[v]++;
g[u].push_back(v);
z[ {u, v}]++;
}
for (int i = 1; i <= n; i++) {
if (d[i] == 0) {
v.push_back(i);
}
}
ans = 0;
for (auto x : v) {
// cout << x << "*\n";
dfs(x, 0, 0);
// cout << ans << "***\n";
}
cout << ans << "\n";
}
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 391ms
memory: 9896kb
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:
971294044
result:
wrong answer 1st numbers differ - expected: '34927818', found: '971294044'