Submission #4130106

---

Source Code Expand

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

int N;
VI G[100011];
VI X[100011];

int par[100011];
VI ord;
int U[100011];

void MAIN() {
    scanf("%d", &N);
    REP (i, N-1) {
	int x, y;
	scanf("%d%d", &x, &y);
	x--; y--;
	G[x].push_back(y);
	G[y].push_back(x);
    }

    ord.reserve(N);
    ord.push_back(0);
    REP (i_, N) {
	int v = ord[i_];
	EACH (e, G[v]) if (*e != par[v]) {
	    par[*e] = v;
	    ord.push_back(*e);
	}
    }

    VI buf; buf.reserve(N+2);
    
    REP (i_, N) {
	int v = ord[N-1-i_];
	int ma = -1;
	EACH (e, G[v]) if (*e != par[v]) {
	    amax(ma, X[*e].back());
	}

	if (ma == -1) {
	    U[v] = 0;
	    X[v].push_back(0);
	} else {
	    buf.resize(ma+2);
	    fill(buf.begin(), buf.end(), 0);
	    EACH (e, G[v]) if (*e != par[v]) {
		EACH (f, X[*e]) buf[*f]++;
	    }
	    int at_least = 0;
	    REP (i, ma+2) if (buf[i] >= 2) at_least = i+1;
	    REP (i, ma+2) {
		if (i < at_least || buf[i]) {
		    buf[i] = 0;
		} else {
		    U[v] = i;
		    buf[i] = 1;
		    break;
		}
	    }
	    REP (i, ma+2) if (buf[i]) X[v].push_back(i);
	}
    }

    int ma = *max_element(U, U+N);
    //rprintf("%d", U, U+N);
    printf("%d\n", ma);
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void MAIN()’:
./Main.cpp:32:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
                    ^
./Main.cpp:35:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &x, &y);
                       ^

Judge Result