oj.uz

Submission #845439

# Submission time Handle Problem Language Result Execution time Memory
845439 2023-09-06T13:37:55 Z vjudge1 Trener (COCI20_trener) C++17
55 / 110
 2000 ms 158576 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long
#define pri pair<int,int>
#define prl pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pair<int,int>>
#define vpl vector<pair<ll,ll>>
#define re return 0
#define sqrt sqrtl

struct node {
    string val;
    vector<int> adj; //asagi
    ll ds = 0;
};

int insides(string s1, string s2) {
    if (s1[0]!=s2[0] && s1[1]!=s2[0]) return 0;
    int flag = 1;
    for (int i = 1;i<s1.size();i++) {
        if (s1[i]!=s2[i-1]) {flag=0;break;}
    }
    if (flag) return 1;
    flag=1;
    for (int i = 1;i<s1.size();i++) {
        if (s1[i-1]!=s2[i-1]) {flag=0;break;}
    }
    if (flag) return 1;
    return 0;
}

int32_t main() {
    int n,k;cin>>n>>k;
    vector<node> nodes(n*k);

    for (int i = 0;i<n;i++) {
        for (int j = 0;j<k;j++) {
            string s1;cin>>s1;nodes[i*k+j].val=s1;
        }
    }
    for (int i = n-1;i>-1;i--){
        for (int j = 0;j<k;j++) {
            if (i==n-1) {nodes[i*k+j].ds=1;continue;}
            nodes[i*k+j].ds=0;
            for (int x = 0;x<k;x++) {
                if (nodes[(i+1)*k+x].ds==0) continue;
                int st = insides(nodes[(i+1)*k+x].val,nodes[i*k+j].val);
                if (st) {
                    nodes[(i+1)*k+x].adj.push_back(i*k+j);
                    nodes[i*k+j].ds+=nodes[(i+1)*k+x].ds;
                    nodes[i*k+j].ds%=MOD;
                }
            }
        }
    }


    ll t = 0;
    for (int i = 0;i<k;i++){
        t+=nodes[i].ds;
        t%=MOD;
    } cout<<t%MOD<<endl; 

    /* for (int  i = 0;i<n*k;i++) {
        cout<<nodes[i].val<<" "<<nodes[i].ds<<" "<<nodes[i].adj.size()<<endl;
    } */
    return 0;
}

Compilation message

trener.cpp: In function 'int insides(std::string, std::string)':
trener.cpp:24:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i = 1;i<s1.size();i++) {
      |                    ~^~~~~~~~~~
trener.cpp:29:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 1;i<s1.size();i++) {
      |                    ~^~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 856 KB Output is correct
2 Correct 6 ms 856 KB Output is correct
3 Correct 6 ms 856 KB Output is correct
4 Correct 29 ms 3412 KB Output is correct
5 Correct 10 ms 856 KB Output is correct
6 Correct 12 ms 1368 KB Output is correct
7 Correct 29 ms 3408 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 856 KB Output is correct
6 Correct 6 ms 856 KB Output is correct
7 Correct 6 ms 856 KB Output is correct
8 Correct 29 ms 3412 KB Output is correct
9 Correct 10 ms 856 KB Output is correct
10 Correct 12 ms 1368 KB Output is correct
11 Correct 29 ms 3408 KB Output is correct
12 Correct 874 ms 8360 KB Output is correct
13 Correct 897 ms 8272 KB Output is correct
14 Correct 892 ms 8420 KB Output is correct
15 Correct 960 ms 8632 KB Output is correct
16 Execution timed out 2041 ms 158576 KB Time limit exceeded
17 Halted 0 ms 0 KB -