Submission #1120355

---

Source Code Expand

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<set>
#include<string>
#include<map>

using namespace std;

#define x first
#define y second
#define NMAX 100005
#define MOD 1000000007

vector<int> tree[NMAX];
int n, viz[NMAX], viz2[NMAX], marked[NMAX], dp[NMAX];

int getCentroid(int node, int sizeTree){
    viz[node] = sizeTree;
    dp[node] = 1;
    int lim = tree[node].size(), ok = 1, ans = 0;
    for(int i = 0; i < lim; i++){
        int vec = tree[node][i];
        if(marked[vec]){
            tree[node][i] = tree[node][lim - 1];
            tree[node].pop_back();
            i--;
            lim--;
            continue;
        }
        if(viz[vec] != sizeTree){
            int poss = getCentroid(vec, sizeTree);
            if(poss)
                ans = poss;
            if(dp[vec] > sizeTree / 2)
                ok = 0;
            dp[node] += dp[vec];
        }
    }
    if(ok && sizeTree - dp[node] <= sizeTree / 2)
        return node;
    return ans;
}

void dfsUpd(int node, int sizeTree){
    viz2[node] = sizeTree;
    dp[node] = 1;
    int lim = tree[node].size();
    for(int i = 0; i < lim; i++){
        int vec = tree[node][i];
        if(viz2[vec] != sizeTree){
            dfsUpd(vec, sizeTree);
            dp[node] += dp[vec];
        }
    }
  // printf("am curatat %d %d\n", node, dp[node]);
}

int uninity(int root, int sizeTree){
    //printf("Arbore %d %d\n", root, sizeTree);
    int center = getCentroid(root, sizeTree);
    //printf("Centru in %d\n", center);
    dfsUpd(center, sizeTree);
    int lim = tree[center].size();
    int answer = 0;
    marked[center] = 1;
    for(int i = 0; i < lim; i++){
        answer = max(answer, uninity(tree[center][i], dp[tree[center][i]]));
    }
    //printf("uninity de %d %d este %d\n", root, sizeTree, answer + 1);
    return answer + 1;
}

int main (){
    int a, b;
    
    scanf("%d",&n);
    for(int i = 1; i < n; i++){
        scanf("%d%d",&a,&b);
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    printf("%d\n", uninity(1, n) - 1);
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:78:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
./Main.cpp:80:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
                            ^

Judge Result