QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#136376#82. Improve SPAMRedex89WA 1ms3532kbC++232.2kb2023-08-08 07:32:442023-08-08 07:32:48

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:32:48]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3532kb
  • [2023-08-08 07:32:44]
  • 提交

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;
}

詳細信息

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'