oj.uz

Submission #777439

# Submission time Handle Problem Language Result Execution time Memory
777439 2023-07-09T09:06:42 Z ElyesChaabouni Lampice (COCI19_lampice) C++14
42 / 110
 5000 ms 5844 KB 
#include<bits/stdc++.h>
using namespace std;

void init(){
    #ifndef ONLINE_JUDGE
 
freopen("input.txt", "r", stdin);
 
freopen("output.txt", "w", stdout);
 
#endif // ONLINE_JUDGE
}

const int mx = 5e4+5;

int n;
string s;
vector<int> graph[mx];

bool vis[mx];

int ans = 1, cur = 1;

void solve(int node1, int node2, int p1, int p2){
    ans = max(ans, cur);
    for(int adj1 : graph[node1]){
        if(adj1 == p1)continue;
        for(int adj2 : graph[node2]){
            if(adj2 == p2 || adj1 == adj2 || s[adj1] != s[adj2])continue;
            cur += 2;
            solve(adj1, adj2, node1, node2);
            cur -= 2;
        }
    }
}

int bfs(){
    for(int i = 1; i <= n;i++){
        vis[i] = 0;
    }
    queue<int> q;
    q.push(1);
    int last = 1;
    while(!q.empty()){
        int node = q.front();
        q.pop();
        if(vis[node])continue;
        last = node;
        vis[node] = 1;
        for(int adj : graph[node]){
            q.push(adj);
        }
    }
    return last;
}

int bfs1(int x){
    for(int i = 1; i <= n;i++){
        vis[i] = 0;
    }
    queue<pair<int, int>> q;
    q.push({x, 1});
    int l = 0;
    while(!q.empty()){
        int node = q.front().first;
        int layer = q.front().second;
        q.pop();
        if(vis[node])continue;
        l = max(l, layer);
        vis[node] = 1;
        for(int adj : graph[node]){
            q.push({adj, layer+1});
        }
    }
    return l;
}

void runcase(){
    cin >> n;
    cin >> s;
    s = "Y" + s;
    int x = 1;
    bool test = 1;
    for(int i = 1; i <= n;i++){
        if(s[i] != s[x])test = 0;
    }
    ans = 1, cur = 1;
    for(int i = 1; i <= n;i++){
        graph[i].clear();
    }
    for(int i = 0; i < n-1;i++){
        int a, b;cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    if(test){
        int x = bfs();
        int l = bfs1(x);
        cout << l << endl;
        return;   
    }
    for(int i = 1; i <= n;i++){
        solve(i, i, i, i);
    }
    cur = 2;
    for(int i = 1; i <= n;i++){
        for(int adj : graph[i]){
            if(s[i] == s[adj]){
                solve(i, adj, adj, i);
            }
        }
    }
    cout << ans << endl;
}

int main(){
    //init();
    int t=1;
    while(t--){
        runcase();
    }
}

Compilation message

lampice.cpp: In function 'void init()':
lampice.cpp:7:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | freopen("input.txt", "r", stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:9:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | freopen("output.txt", "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct
3 Correct 2 ms 1492 KB Output is correct
4 Correct 4 ms 1492 KB Output is correct
5 Correct 1 ms 1364 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3396 KB Output is correct
2 Correct 26 ms 4220 KB Output is correct
3 Correct 29 ms 5596 KB Output is correct
4 Correct 30 ms 5844 KB Output is correct
5 Correct 28 ms 5192 KB Output is correct
6 Correct 25 ms 3640 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3668 KB Output is correct
2 Correct 28 ms 3752 KB Output is correct
3 Correct 33 ms 3732 KB Output is correct
4 Execution timed out 5058 ms 4396 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct
3 Correct 2 ms 1492 KB Output is correct
4 Correct 4 ms 1492 KB Output is correct
5 Correct 1 ms 1364 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Correct 23 ms 3396 KB Output is correct
9 Correct 26 ms 4220 KB Output is correct
10 Correct 29 ms 5596 KB Output is correct
11 Correct 30 ms 5844 KB Output is correct
12 Correct 28 ms 5192 KB Output is correct
13 Correct 25 ms 3640 KB Output is correct
14 Correct 29 ms 3668 KB Output is correct
15 Correct 28 ms 3752 KB Output is correct
16 Correct 33 ms 3732 KB Output is correct
17 Execution timed out 5058 ms 4396 KB Time limit exceeded
18 Halted 0 ms 0 KB -