QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#206449 | #7558. Abstract | ucup-team191# | WA | 37ms | 14304kb | C++14 | 1.7kb | 2023-10-07 20:35:09 | 2023-10-07 20:35:09 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 1e4 + 50;
const int buk = 40;
struct big_num{
vector < ll > zn;
void ocisti(){
ll vis = 0;
for(ll &x : zn) {
x += vis;
vis = x >> buk;
x &= (1LL << buk) - 1;
}
if(vis) zn.PB(vis);
}
void mul(ll y) {
for(ll &x : zn) x *= y;
ocisti();
}
void operator+=(const big_num &rhs) {
while((int)zn.size() < (int)rhs.zn.size())
zn.PB(0);
for(int i = 0;i < (int)rhs.zn.size();i++)
zn[i] += rhs.zn[i];
ocisti();
}
};
int n, m, x, in[N], dis[N], A[N];
big_num dp[N];
queue < int > Q;
vector < int > v[N];
int main(){
scanf("%d%d", &n, &m);
for(int i = 1;i <= n;i++) scanf("%d", A + i);
for(int i = 0;i < m;i++) {
int a, b; scanf("%d%d", &a, &b);
v[b].PB(a); in[a]++;
}
for(x=1;in[x];x++);
Q.push(x);
memset(dis, -1, sizeof(dis));
int mx_dis = 0;
dp[x].zn.PB(1);
for(;!Q.empty();Q.pop()) {
int cur = Q.front();
dp[cur].mul(2);
if(A[cur]) mx_dis = max(mx_dis, dis[cur]);
for(int nxt : v[cur]) {
dp[nxt] += dp[cur];
in[nxt]--;
dis[nxt] = max(dis[nxt], dis[cur] + 1);
if(in[nxt] == 0) {
Q.push(nxt);
}
}
}
big_num sve;
for(int i = 1;i <= n;i++) {
dp[i].mul(A[i]);
sve += dp[i];
}
while((int)sve.zn.size() > 0 && sve.zn.back() == 0) sve.zn.pop_back();
if(!(int)sve.zn.size()) {
printf("0\n");
return 0;
}
int kol = (int)sve.zn.size() * buk - buk;
if((int)sve.zn.size()) {
while(sve.zn.back()) {
kol++; sve.zn.back() >>= 1;
}
}
printf("%d\n", kol - 1);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3536kb
input:
3 2 1 1 1 1 2 2 3
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
6 8 1 1 4 5 1 4 1 4 1 5 2 3 2 5 3 4 4 5 4 6 5 6
output:
8
result:
ok 1 number(s): "8"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
5 6 7 2 3 6 6 1 2 1 4 2 3 3 4 3 5 4 5
output:
9
result:
ok 1 number(s): "9"
Test #4:
score: -100
Wrong Answer
time: 37ms
memory: 14304kb
input:
7286 80481 637288250 628935175 588324396 766398783 663989874 865498593 695497968 630237220 19939888 448367842 412696777 111291257 304805809 585852799 58270069 391993802 606944382 827515045 389862501 643981354 160381074 324288921 257053597 980043955 417281046 870855665 360154617 60327683 966755927 55...
output:
7342
result:
wrong answer 1st numbers differ - expected: '7344', found: '7342'