QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#136375#82. Improve SPAMRedex89WA 1ms3556kbC++232.0kb2023-08-08 07:31:372023-08-08 07:31:38

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-08 07:31:38]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3556kb
  • [2023-08-08 07:31:37]
  • 提交

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;
 
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;
}
 
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){
            ideal = (ideal + 1) % MOD;
            ans1 = (ans1 + inDeg[i]) % MOD;
        }
    }
 
    memset(memo, -1, sizeof memo);
 
    cout << dp(0) << " " << ideal +1 % MOD << ENDL;
 
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5 3
2 2 3
2 4 5
2 4 2

output:

5 3

result:

wrong answer 1st lines differ - expected: '5 2', found: '5 3'