oj.uz

Submission #223454

# Submission time Handle Problem Language Result Execution time Memory
223454 2020-04-15T09:30:03 Z dwsc Lampice (COCI19_lampice) C++14
0 / 110
 5000 ms 524292 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
string act;
vector<int> adj[50010];
set<string> bigmap,smallmap;
set<string> m1,m2;
void dfs(int u,int pa,string s){
    smallmap.insert(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.insert(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.insert(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++){
        bigmap.clear();
        for (int j = 0; j < adj[i].size(); j++) {
            smallmap.clear();
            string s = "";
            s += act[adj[i][j]];
            dfs(adj[i][j],i,s);
            for (auto it = smallmap.begin(); it != smallmap.end(); ++it){
                if (bigmap.find(*it) != bigmap.end())  ans = max(ans,2*(int)((*it).length())+1);
                else bigmap.insert(*it);
            }
        }
       // 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.find(*it) != m2.end()) ans = max(ans,2*(int)((*it).length()));
        }
    }
    cout << ans;
}

Compilation message

lampice.cpp: In function 'int main()':
lampice.cpp:54:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < adj[i].size(); j++) {
                         ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 1536 KB Output is correct
2 Correct 521 ms 1784 KB Output is correct
3 Correct 4571 ms 2436 KB Output is correct
4 Execution timed out 5071 ms 2156 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 522 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 1016 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 1536 KB Output is correct
2 Correct 521 ms 1784 KB Output is correct
3 Correct 4571 ms 2436 KB Output is correct
4 Execution timed out 5071 ms 2156 KB Time limit exceeded
5 Halted 0 ms 0 KB -