Submission #68549

#	Time	Username	Problem	Language	Result	Execution time	Memory
68549		ekrem	Shymbulak (IZhO14_shymbulak)	C++98	0 / 100	124 ms	30804 KiB

shymbulak

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 1000005
using namespace std;

typedef pair < int , int > ii;
typedef pair < int , ii > iii;

int n, m, cvp, kac = 1, u[N];
vector < int > g[N], b;
ii c[N];

ii uz(int i, int j){
	int uz1 = j - i;
	int uz2 = m - uz1;
	if(uz1 != uz2)
		return mp( min(uz1, uz2) , 1);
	return mp(uz1, 2);
}

int dfs(int node, int par){
	u[node] = 1;
	for(int i = 0; i < g[node].size(); i++)
		if(g[node][i] != par) {
			if(u[ g[node][i] ]){
				b.pb(node);
				return 1;
			}
			if(dfs(g[node][i], node)){
				b.pb(node);
				return 1;
			}
		}
	return 0;
}

ii bul(int node, int par){
	int mx = 0, say = 1, son = -1, son2 = -1;
	vector < ii > c;
	vector < int > pre;
	for(int i = 0; i < g[node].size(); i++)
		if(g[node][i] != par and !u[g[node][i]]){
			ii don = bul(g[node][i], node);
			c.pb(mp(don.st + 1, don.nd));
			pre.pb(0);
		}
	sort(c.begin(), c.end());
	reverse(c.begin(), c.end());
	for(int i = 0; i < c.size(); i++){
		if(c[i].st == c[0].st){
			pre[i] = ((i == 0)?0:pre[i-1]) + c[i].nd;
			son = i;
		}else if(c[i].st == c[son + 1].st){
			pre[i] = ((i == son + 1)?0:pre[i-1]) + c[i].nd;
			son2 = i;
		}
	}
	int sonmx = 0, xx = 1;
	if(son != -1){
		mx = c[0].st, say = pre[son];
		sonmx = mx;
		xx = say;
	}
	if(son > 0){
		sonmx = c[0].st + c[0].st;
		xx = 0;
		for(int i = 1; i <= son; i++)
			xx += pre[i - 1]*c[i].nd;

	}
	if(son == 0 and son2 > 0){
		sonmx = c[0].st + c[son2].st;
		xx = (c[0].nd)*pre[son2];
	}
	if(sonmx == cvp)
		kac += xx;
	if(sonmx > cvp){
		cvp = sonmx;
		kac = xx;
	}
	// cout << node << " -> " << mx << " , " << say << endl;
	return mp(mx, say);
}


int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d",&n);
	for(int i = 1; i <= n; i++){
		int u, v;
		scanf("%d %d",&u ,&v);
		g[u].pb(v);
		g[v].pb(u);
	}
	b.pb(0);
	dfs(1, 1);
	memset(u, 0, sizeof u);
	for(int i = 1; i < b.size(); i++)u[b[i]] = 1;
	for(int i = 1; i < b.size(); i++)
		c[++m] = bul(b[i], -1);
	for(int i = 1; i <= m; i++)
		for(int j = i + 1; j <= m; j++){
			int sonmx, xx;
			sonmx = uz(i, j).st + c[i].st + c[j].st;
			xx = uz(i, j).nd*c[i].nd*c[j].nd;
			if(sonmx == cvp)
				kac += xx;
			if(sonmx > cvp){
				cvp = sonmx;
				kac = xx;
			}
		}
	printf("%d\n", kac);
	return 0;
}

Compilation message (stderr)

shymbulak.cpp: In function 'int dfs(int, int)':
shymbulak.cpp:26:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
shymbulak.cpp: In function 'ii bul(int, int)':
shymbulak.cpp:44:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
shymbulak.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < c.size(); i++){
                 ~~^~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:102:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < b.size(); i++)u[b[i]] = 1;
                 ~~^~~~~~~~~~
shymbulak.cpp:103:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < b.size(); i++)
                 ~~^~~~~~~~~~
shymbulak.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
shymbulak.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&u ,&v);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50