제출 #68592

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68592		ekrem	관광지 (IZhO14_shymbulak)	C++98	50 / 100	1574 ms	34172 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);
}
 
void yap(int sonmx, int xx){
	if(sonmx == cvp)
		kac += xx;
	if(sonmx > cvp){
		cvp = sonmx;
		kac = xx;
	}
}
 
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 g[node][i];
			}
			int amk;
			amk = dfs(g[node][i], node);
			if(amk){
				b.pb(node);
				if(amk == node)
					return 0;
				else
					return amk;
			}
		}
	return 0;
}
 
ii bul(int node, int par){
	int mx = 0, say = 1, son = -1, top = 0, mx2 = 0;
	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){
			top += c[i].nd;
			mx2 = c[i].st;
		}
	}
	if(son != -1){
		mx = c[0].st, say = pre[son];
		int sonmx = mx;
		int xx = say;
		yap(sonmx, xx);
	}
	if(son > 0){
		int sonmx = c[0].st + c[0].st;
		int xx = 0;
		for(int i = 1; i <= son; i++)
			xx += pre[i - 1]*c[i].nd;
		yap(sonmx, xx);
	}
	if(son == 0){
		int sonmx = c[0].st + mx2;
		int xx = (c[0].nd)*top;
		yap(sonmx, 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++)cout << b[i] << " ";cout << endl;
	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 = uz(i, j).st + c[i].st + c[j].st;
			int xx = uz(i, j).nd*c[i].nd*c[j].nd;
			yap(sonmx, xx);
		}
	printf("%d\n", kac);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

shymbulak.cpp: In function 'int dfs(int, int)':
shymbulak.cpp:35: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:58:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
shymbulak.cpp:66: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:113: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:114:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < b.size(); i++)
                 ~~^~~~~~~~~~
shymbulak.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
shymbulak.cpp:105: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: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 50