Submission #223423

#	Time	Username	Problem	Language	Result	Execution time	Memory
223423		dwsc	Lampice (COCI19_lampice)	C++14	0 / 110	2123 ms	524292 KiB

lampice

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
string act;
vector<int> adj[50010];
map<string,int> m;
map<string,int> m1,m2;
void dfs(int u,int pa,string s){
    m[s]++;
    //cout << s << "hi\n";
    //cout << s << "hi\n";
    for (int v: adj[u]){
        if (v == pa) continue;
        dfs(v,u,s+act[v]);
    }
}
void dfs1(int u,int pa,string s){
    m1[s]++;
    //cout << s << "hi\n";
    //cout << s << "hi\n";
    for (int v: adj[u]){
        if (v == pa) continue;
        dfs1(v,u,s+act[v]);
    }
}
void dfs2(int u,int pa,string s){
    m2[s]++;
    //cout << s << "hi\n";
    //cout << s << "hi\n";
    for (int v: adj[u]){
        if (v == pa) continue;
        dfs2(v,u,s+act[v]);
    }
}
int main(){
    int n;
    cin >> n;
    cin >> act;
    //cout << act << "read\n";
    ii edge[n-1];
    for (int i = 0; i < n-1; i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
        edge[i] = ii(a,b);
    }

    int ans = 0;
    for (int i = 0; i < n; i++){
        m.clear();
        //cout << act[i] << "\n";
        string s = "";
        s += act[i];
        dfs(i,-1,s);
        for (auto it = m.begin(); it != m.end(); ++it){
           //cout<< it->first << " " << it->second << "\n";
            if (it->second >= 2) ans = max(ans,2*(int)((it->first).length())-1);
        }
       // cout << "hi\n";
    }
    for (int i = 0; i < n-1; i++){
        int a = edge[i].first,b = edge[i].second;
        string s1 = "",s2 = "";
        s1 += act[a],s2+= act[b];
        m1.clear();
        m2.clear();
        dfs1(a,b,s1);
        dfs2(b,a,s2);
        for (auto it = m1.begin(); it != m1.end(); ++it){
           //cout<< it->first << " " << it->second << "\n";
            if (m2[it->first]) ans = max(ans,2*(int)((it->first).length()));
        }
    }
    cout << ans;
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37