oj.uz

Submission #746292

# Submission time Handle Problem Language Result Execution time Memory
746292 2023-05-22T08:01:11 Z bgnbvnbv Necklace (Subtask 1-3) (BOI19_necklace1) C++14
45 / 85
 1500 ms 16972 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=3e4;
const ll inf=1e18;
const ll mod=1e9+7;
struct TrieNode {
    int nxt[26], link;
};
vector<TrieNode> Trie;
vector<int> adj[maxN];


int  numNode, nTree, numQuery;
vector<ll>pos;
int val[maxN];
void insertString(const string &str,bool t) {
    int pt(0);
    if(t) pos.pb(0);
    ll ct=0;
    for (char ch : str) {
        ct++;
        int c(ch - 'a');
        if(!Trie[pt].nxt[c]) {
            Trie[pt].nxt[c] = Trie.size();
            Trie.emplace_back();
        }
        pt = Trie[pt].nxt[c];
        if(t==1) pos.pb(pt);
        else val[pt]=ct;
    }
}
queue<int> qu;
void buildAutomaton(void) {
    while(!qu.empty()) qu.pop();
    qu.push(0);
    while(qu.size()) {
        int v(qu.front()), u(Trie[v].link);
        qu.pop();

        for (int c = 0; c < 26; ++c) {
            if(Trie[v].nxt[c]) {
                Trie[Trie[v].nxt[c]].link = (v) ? Trie[u].nxt[c] : 0;
                qu.push(Trie[v].nxt[c]);
            } else {
                Trie[v].nxt[c] = Trie[u].nxt[c];
            }
        }
    }
}
void preDfs(int u,int p) {
    for (int it = 0; it < int(adj[u].size()); ++it) {
        int v(adj[u][it]);
        val[v]=max(val[v],val[u]);
        preDfs(v,u);
    }
}
void buildTree(void) {
    nTree = Trie.size();
    for (int i = 1; i < nTree; ++i)
        adj[Trie[i].link].push_back(i);

    preDfs(0,0);
}
ll n;
void cl()
{
    for(int i=0;i<Trie.size();i++) adj[i].clear(),val[i]=0;
    Trie.clear();
    pos.clear();
    Trie.emplace_back();
}
string s,t;
ll cnt[maxN];
ll ans=0,id1=0,id2=0;
ll cal(bool tt)
{
    string a;
    for(int i=0;i<=n;i++)
    {
        cl();
        a.clear();
        for(int j=i;j<n;j++)
        {
            a.pb(s[j]);
        }
        insertString(a,0);
        insertString(t,1);
        buildAutomaton();
        buildTree();
        for(int j=0;j<=t.size();j++)
        {
            cnt[j]=0;
        }
        for(int j=0;j<=t.size();j++)
        {
            cnt[j]+=val[pos[j]];
        }
        cl();
        a.clear();
        for(int j=i-1;j>=0;j--)
        {
            a.pb(s[j]);
        }
        reverse(t.begin(),t.end());
        pos.clear();
        insertString(a,0);
        insertString(t,1);
        buildAutomaton();
        buildTree();
        for(int j=0;j<=t.size();j++)
        {
            ll x=cnt[j]+val[pos[t.size()-j]];
            if(ans<x)
            {
                ans=x;
                id1=i-val[pos[t.size()-j]];
                if(tt)
                {
                    id1=id1+x-1;
                    id1=s.size()-id1-1;
                }
                id2=j-cnt[j];
            }
        }
        reverse(t.begin(),t.end());
    }
    return ans;
}
ll m;
void solve()
{
    cin >> s >> t;
    n=s.size();
    m=t.size();
    cal(0);
    reverse(s.begin(),s.end());
    cal(1);
    cout << ans<<'\n';
    cout << id1<<' '<<id2;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

necklace.cpp: In function 'void cl()':
necklace.cpp:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<TrieNode>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i=0;i<Trie.size();i++) adj[i].clear(),val[i]=0;
      |                 ~^~~~~~~~~~~~
necklace.cpp: In function 'll cal(bool)':
necklace.cpp:97:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for(int j=0;j<=t.size();j++)
      |                     ~^~~~~~~~~~
necklace.cpp:101:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for(int j=0;j<=t.size();j++)
      |                     ~^~~~~~~~~~
necklace.cpp:117:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for(int j=0;j<=t.size();j++)
      |                     ~^~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 980 KB Output is correct
2 Correct 9 ms 1096 KB Output is correct
3 Correct 7 ms 1044 KB Output is correct
4 Correct 8 ms 980 KB Output is correct
5 Correct 9 ms 980 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 980 KB Output is correct
2 Correct 9 ms 1096 KB Output is correct
3 Correct 7 ms 1044 KB Output is correct
4 Correct 8 ms 980 KB Output is correct
5 Correct 9 ms 980 KB Output is correct
6 Correct 130 ms 1488 KB Output is correct
7 Correct 130 ms 1408 KB Output is correct
8 Correct 105 ms 1248 KB Output is correct
9 Correct 113 ms 1440 KB Output is correct
10 Correct 123 ms 1356 KB Output is correct
11 Correct 118 ms 1236 KB Output is correct
12 Correct 124 ms 1268 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 980 KB Output is correct
2 Correct 9 ms 1096 KB Output is correct
3 Correct 7 ms 1044 KB Output is correct
4 Correct 8 ms 980 KB Output is correct
5 Correct 9 ms 980 KB Output is correct
6 Correct 130 ms 1488 KB Output is correct
7 Correct 130 ms 1408 KB Output is correct
8 Correct 105 ms 1248 KB Output is correct
9 Correct 113 ms 1440 KB Output is correct
10 Correct 123 ms 1356 KB Output is correct
11 Correct 118 ms 1236 KB Output is correct
12 Correct 124 ms 1268 KB Output is correct
13 Execution timed out 1578 ms 16972 KB Time limit exceeded
14 Halted 0 ms 0 KB -