QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#136376 | #82. Improve SPAM | Redex89 | WA | 1ms | 3532kb | C++23 | 2.2kb | 2023-08-08 07:32:44 | 2023-08-08 07:32:48 |
Judging History
answer
#include <bits/stdc++.h>
//Pura gente del coach moy
using namespace std;
#define ENDL '\n'
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int) x.size()
#define FOR(x, b) for(int x = 0; x <b; x++)
#define FORE(x, a, b) for(int x = a; x <= b; x++)
#define FORR(x, a, b) for(int x = a; x >= b; x--)
#define deb(x) cerr << #x << " = " << x << '\n';
#define deb2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << '\n';
#define _ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
const ll MOD = 1e9+7, INF = 1e18;
vi adj[2100], ts;
bool visited[2100];
ll inDeg[2100];
ll ideal = 0, paths = 0;
int x, k, n, l;
set<int> ideales;
void toposort(int u) {
visited[u] = 1;
for (auto v : adj[u])
if (!visited[v])
toposort(v);
ts.push_back(u);
}
int memo[2100];
int dp(int u){
if(memo[u] != -1){
return memo[u];
}
int ans = 0;
for(int v : adj[u]){
if(v < l){
ans = (ans % MOD + dp(v)) % MOD;
}else{
ans = (ans % MOD + 1 % MOD) % MOD;
}
}
return memo[u] = ans;
}
void dfs(int u){
visited[u] = true;
for(int v: adj[u]){
{
if(v < l){
dfs(v);
}else
ideales.insert(v);
}
}
}
int main(){_
cin >> n >> l;
FOR(i, l){
cin >> k;
FOR(j, k){
cin >> x;
x--;
adj[i].push_back(x);
}
}
FOR(u, n){
if(!visited[u])
toposort(u);
}
reverse(all(ts));
inDeg[0] = 1;
for(auto u : ts){
for(auto v : adj[u]){
inDeg[v] = (inDeg[v] + inDeg[u]) % MOD;
}
}
// ll ans1 = 0;
// FORE(i, l, n - 1){
// if(inDeg[i] > 0){
// ideales.insert(i);
// }
// }
memset(memo, -1, sizeof memo);
memset(visited, false, sizeof visited);
cout << dp(0) << " " << sz(ideales) << ENDL;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3532kb
input:
5 3 2 2 3 2 4 5 2 4 2
output:
5 0
result:
wrong answer 1st lines differ - expected: '5 2', found: '5 0'