Submission #777439

#	Time	Username	Problem	Language	Result	Execution time	Memory
777439		ElyesChaabouni	Lampice (COCI19_lampice)	C++14	42 / 110	5058 ms	5844 KiB

lampice

#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 (stderr)

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 / 17
• Subtask 2: 25 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37