oj.uz

Submission #445106

# Submission time Handle Problem Language Result Execution time Memory
445106 2021-07-16T13:01:26 Z Abrar_Al_Samit Trener (COCI20_trener) C++17
55 / 110
 2000 ms 10572 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;


#define debug(x) cerr << '[' << (#x) << "] = " << x << '\n';

template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update> ;

const int maxn = 1e5 + 5;
const int Mod = 1e9 + 7;
vector<int>g[maxn];
vector<int>toposort(vector<int>& in) {
    vector<int>ret;
    queue<int>q;
    for(int i=0; i<in.size(); ++i) if(in[i]==0) q.push(i);
    while(!q.empty()) {
        int cur = q.front(); q.pop();
        ret.push_back(cur);
        for(auto it : g[cur]) if(--in[it]==0) q.push(it);
    }
    return ret;
}
void PlayGround() {
    int n, k; cin >> n >> k;
    vector<vector<string>>buck(n, vector<string>(k));
    for(int i=0; i<n; ++i) {
        for(auto& it : buck[i]) 
            cin >> it;
    }
    auto substring = [=] (string& s, string& t) {
        if(s.substr(0, t.size())==t || s.substr(1, t.size())==t)
            return true;
        return false;
    };
    vector<int>in(n*k);
    for(int i=0; i<n-1; ++i) {
        for(int j=0; j<k; ++j) {
            for(int l=0; l<k; ++l) {
                if(substring(buck[i+1][l], buck[i][j])) {
                    in[(i+1)*k + l]++;
                    g[i*k + j].push_back((i+1)*k+l);
                }
            }
        }
    }
    vector<int>dp(n*k);
    for(int i=0; i<k; ++i) dp[i] = 1;
    vector<int>sorted = toposort(in);
    int ans = 0;
    for(auto it : sorted) {
        for(auto it2 : g[it]) 
            dp[it2] = (dp[it2] + dp[it]) % Mod;
    }
    for(int i=(n-1)*k; i<n*k; ++i)
        ans = (ans + dp[i]) % Mod;
    cout << ans << '\n';

    #ifndef ONLINE_JUDGE
        cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    #endif
} 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  //  #ifndef ONLINE_JUDGE
   //     freopen("input.txt", "r", stdin);
   // #endif
    PlayGround();

    return 0;
}

Compilation message

trener.cpp: In function 'std::vector<int> toposort(std::vector<int>&)':
trener.cpp:19:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i=0; i<in.size(); ++i) if(in[i]==0) q.push(i);
      |                  ~^~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2660 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3324 KB Output is correct
2 Correct 41 ms 3216 KB Output is correct
3 Correct 40 ms 3304 KB Output is correct
4 Correct 34 ms 5704 KB Output is correct
5 Correct 40 ms 3332 KB Output is correct
6 Correct 40 ms 3424 KB Output is correct
7 Correct 36 ms 5740 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2660 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 40 ms 3324 KB Output is correct
6 Correct 41 ms 3216 KB Output is correct
7 Correct 40 ms 3304 KB Output is correct
8 Correct 34 ms 5704 KB Output is correct
9 Correct 40 ms 3332 KB Output is correct
10 Correct 40 ms 3424 KB Output is correct
11 Correct 36 ms 5740 KB Output is correct
12 Execution timed out 2072 ms 10572 KB Time limit exceeded
13 Halted 0 ms 0 KB -