oj.uz

Submission #845560

# Submission time Handle Problem Language Result Execution time Memory
845560 2023-09-06T14:08:41 Z vjudge1 Trener (COCI20_trener) C++17
110 / 110
 192 ms 23180 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;
    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;
        }
    }
    map<string,ll> umap;
    for (int i = n-1;i>-1;i--) {
        if (i!=n-1) {
            for (int j = 0;j<k;j++) {
                if (umap[nodes[i*k+j].val]) {
                    int nj = umap[nodes[i*k+j].val];
                    nodes[i*k+j].ds=umap[nodes[i*k+j].val]%MOD;
                }
            }
        }
        if (i>0) {
            for (int j = 0;j<k;j++) {
                if (i==n-1) nodes[i*k+j].ds = 1;

                string ns; ns = nodes[i*k+j].val.substr(1,nodes[i*k+j].val.size()-1);
                string nw; nw = nodes[i*k+j].val.substr(0,nodes[i*k+j].val.size()-1);
                umap[ns]+=nodes[i*k+j].ds;
                if (ns!=nw) umap[nw]+=nodes[i*k+j].ds;

                umap[ns]%=MOD;
                umap[nw]%=MOD;
            }
        }
    }
    int ts = 0;
    for (int i = 0;i<k;i++) {
        ts+=nodes[i].ds;
        ts%=MOD;
    }
    cout<<ts%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:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int i = 1;i<s1.size();i++) {
      |                    ~^~~~~~~~~~
trener.cpp:28:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i = 1;i<s1.size();i++) {
      |                    ~^~~~~~~~~~
trener.cpp: In function 'int32_t main()':
trener.cpp:49:25: warning: unused variable 'nj' [-Wunused-variable]
   49 |                     int nj = umap[nodes[i*k+j].val];
      |                         ^~

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 344 KB Output is correct
3 Correct 0 ms 344 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 9 ms 1880 KB Output is correct
2 Correct 9 ms 1884 KB Output is correct
3 Correct 9 ms 1884 KB Output is correct
4 Correct 4 ms 600 KB Output is correct
5 Correct 8 ms 1624 KB Output is correct
6 Correct 9 ms 1624 KB Output is correct
7 Correct 4 ms 856 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 9 ms 1880 KB Output is correct
6 Correct 9 ms 1884 KB Output is correct
7 Correct 9 ms 1884 KB Output is correct
8 Correct 4 ms 600 KB Output is correct
9 Correct 8 ms 1624 KB Output is correct
10 Correct 9 ms 1624 KB Output is correct
11 Correct 4 ms 856 KB Output is correct
12 Correct 188 ms 23012 KB Output is correct
13 Correct 191 ms 23016 KB Output is correct
14 Correct 192 ms 23180 KB Output is correct
15 Correct 183 ms 22996 KB Output is correct
16 Correct 55 ms 7248 KB Output is correct
17 Correct 159 ms 17832 KB Output is correct
18 Correct 163 ms 17748 KB Output is correct
19 Correct 157 ms 17812 KB Output is correct
20 Correct 155 ms 17704 KB Output is correct
21 Correct 157 ms 17744 KB Output is correct
22 Correct 61 ms 7368 KB Output is correct