답안 #91188 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
91188	2018-12-26T13:34:49 Z	daniel_02	관광지 (IZhO14_shymbulak)	C++17	100 / 100	1091 ms	39672 KB

shymbulak

#include <bits/stdc++.h>

#define fr first
#define pb push_back
#define sc second
#define ll long long

using namespace std;

const int N = 2e5 + 7;
const int inf = 1e9 + 7;

vector<int>g[N];
int c[N];
set<int, greater<int>>st1;
set<int, greater<int>>st2;
int mp1[N];
int mp2[N];
ll cnt[N];
int qt[N], tin[N], cn, fup[N];
ll mx = -1;
map<pair<int, int>, bool>is_b;
bool us[N];
int ver;
int cycn;

void dfs(int v, int p)
{	
	tin[v] = fup[v] = ++cn;
	us[v] = 1;
	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i];
		if (to == p)continue;
		if (us[to])
		{
			fup[v] = min(fup[v], tin[to]);
		}
		else
		{
			dfs(to, v);
			fup[v] = min(fup[v], fup[to]);
			if (fup[to] > tin[v])
				is_b[{v, to}] = 1, is_b[{to, v}] = 1;
			else
				ver = to;
		}
	}
}
pair<int, int> deep(int v, int p)
{
	ll mxx = -1, mx1 = -1;
	ll eq = 1, eq1 = 1;
	ll col = 0, sm = 0;
	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i];
		if (to == p || !is_b[{v, to}])continue;
		pair<ll, ll> q = deep(to, v);
		if (mxx < q.fr)
		{
			eq1 = eq;
			mx1 = mxx;
			mxx = q.fr;
			eq = q.sc;
			sm = q.sc;
		}
		else
		{
			if (q.fr == mxx){
				eq += q.sc;
				col += (q.sc * sm);
				sm += q.sc;
			}
			if (q.fr == mx1)
				eq1 += q.sc;
			if (q.fr > mx1)
				eq1 = q.sc;
			mx1 = max(mx1, q.fr * 1LL);
		}
	}
	mxx++; mx1++;
	if (mxx != mx1)
	{
		col = eq * eq1;
	}
	mx = max(mxx + mx1, mx);
	cnt[mxx + mx1] += col;
	return {mxx, eq};
}
void dfs1(int v, int p, int id)
{
	us[v] = 1;
	cycn++;
	us[v] = 1;
	int mx = 0;
	int cnt = 0;
	pair<int, int>q = deep(v, p);
	mx = q.fr, cnt = q.sc;
	c[id] = mx;
	qt[id] = cnt;
	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i];
		if (us[to] || is_b[{v, to}])continue;
		dfs1(to, v, id + 1);
	}
}
void dfs2(int v, int p, int id)
{
	us[v] = 1;
	if (id != 0)
	{
		ll len = (*st1.begin()) + id + c[id];
		mx = max(mx, len);
		cnt[len] += (mp1[len - id - c[id]] * 1LL * qt[id]);
		if (st2.size())
		{
			len = (*st2.begin()) - id + c[id];
			mx = max(mx, len);
			cnt[len] += (mp2[len + id - c[id]] * 1LL * qt[id]);
		}
	}
	st1.insert(c[id] - id);
	mp1[c[id] - id] += qt[id];
	int prev = cycn / 2;
	if (id >= prev)
	{
		mp1[c[id - prev] - id + prev] -= qt[id - prev];
		if (mp1[c[id - prev] - id + prev] == 0)
			st1.erase(c[id - prev] - id + prev);
		if (cycn % 2){
			st2.insert(c[id - prev] + cycn + id - prev);
			mp2[c[id - prev] + cycn + id - prev] += qt[id - prev];
		}
	}
	if (cycn % 2 == 0 && id >= prev - 1)
	{
		st2.insert(cycn + (id - prev + 1) + c[id - prev + 1]);
		mp2[cycn + (id - prev + 1) + c[id - prev + 1]] += qt[id - prev + 1];
	}
	for (int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i];
		if (is_b[{v, to}] || us[to])continue;
		dfs2(to, v, id + 1);
	}
}
main()
{
	int n;
	
	cin >> n;
	
	for (int i = 1; i <= n; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		g[a].pb(b);
		g[b].pb(a);
	}
	
	dfs(1, 0);
	memset(us, 0, sizeof(us));
	
	dfs1(ver, 0, 0);
	memset(us, 0, sizeof(us));
	dfs2(ver, 0, 0);
	cout << cnt[mx] << endl;
}
/*
 * Find Bridges
 * Assign c[i]s (length of subtree) and q[i] number of them and cyc -> length of cycle 
 * Dance
*/

Compilation message

shymbulak.cpp: In function 'void dfs(int, int)':
shymbulak.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++)
                  ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'std::pair<int, int> deep(int, int)':
shymbulak.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++)
                  ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void dfs1(int, int, int)':
shymbulak.cpp:102:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++)
                  ~~^~~~~~~~~~~~~
shymbulak.cpp: In function 'void dfs2(int, int, int)':
shymbulak.cpp:142:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < g[v].size(); i++)
                  ~~^~~~~~~~~~~~~
shymbulak.cpp: At global scope:
shymbulak.cpp:149:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:158:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5240 KB	Output is correct
2	Correct	5 ms	5400 KB	Output is correct
3	Correct	6 ms	5400 KB	Output is correct
4	Correct	6 ms	5400 KB	Output is correct
5	Correct	6 ms	5400 KB	Output is correct
6	Correct	5 ms	5400 KB	Output is correct
7	Correct	6 ms	5400 KB	Output is correct
8	Correct	5 ms	5528 KB	Output is correct
9	Correct	5 ms	5528 KB	Output is correct
10	Correct	5 ms	5528 KB	Output is correct
11	Correct	5 ms	5528 KB	Output is correct
12	Correct	5 ms	5528 KB	Output is correct
13	Correct	5 ms	5528 KB	Output is correct
14	Correct	6 ms	5528 KB	Output is correct
15	Correct	6 ms	5588 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5712 KB	Output is correct
2	Correct	7 ms	5712 KB	Output is correct
3	Correct	6 ms	5740 KB	Output is correct
4	Correct	6 ms	5740 KB	Output is correct
5	Correct	10 ms	6252 KB	Output is correct
6	Correct	13 ms	6380 KB	Output is correct
7	Correct	12 ms	6380 KB	Output is correct
8	Correct	11 ms	6380 KB	Output is correct
9	Correct	10 ms	6380 KB	Output is correct
10	Correct	11 ms	6396 KB	Output is correct

Subtask #3
50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	258 ms	21056 KB	Output is correct
2	Correct	260 ms	22140 KB	Output is correct
3	Correct	148 ms	30004 KB	Output is correct
4	Correct	116 ms	30004 KB	Output is correct
5	Correct	120 ms	30004 KB	Output is correct
6	Correct	569 ms	35132 KB	Output is correct
7	Correct	398 ms	35132 KB	Output is correct
8	Correct	249 ms	38268 KB	Output is correct
9	Correct	254 ms	38628 KB	Output is correct
10	Correct	222 ms	39672 KB	Output is correct
11	Correct	823 ms	39672 KB	Output is correct
12	Correct	1091 ms	39672 KB	Output is correct

답안 #91188

Compilation message

Subtask #1 30.0 / 30.0

Subtask #2 20.0 / 20.0

Subtask #3 50.0 / 50.0

Subtask #1
30.0 / 30.0

Subtask #2
20.0 / 20.0

Subtask #3
50.0 / 50.0