답안 #91181 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
91181	2018-12-26T13:10:15 Z	daniel_02	관광지 (IZhO14_shymbulak)	C++17	100 / 100	1143 ms	41300 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;
map<int, ll>mp1;
map<int, ll>mp2;
map<ll, ll>cnt;
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);
		}
		//cout << v << " " << mx1 << " <-> " << mxx << " " << eq << " " << eq1 << " " << col << endl;
	}
	mxx++; mx1++;
	if (mxx != mx1)
	{
		col = eq * eq1;
	}
	//cout << v << " " << mxx << " " << mx1 << " " << eq << " " << eq1 << " " << col << endl;
	mx = max(mxx + mx1, mx);
	cnt[mxx + mx1] += col;
	//cout << v << " " << mxx + mx1 << " " << cnt[mxx + mx1] << " " << mx << endl; 
	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]);
		//cout << v << " " << id << " " << len << " " << mp1[len - id - c[id]] * 1LL * qt[id] << endl;
		if (st2.size())
		{
			len = (*st2.begin()) - id + c[id];
			mx = max(mx, len);
			cnt[len] += (mp2[len + id - c[id]] * 1LL * qt[id]);
		//cout << v << " " << id << " " << len << " " << mp2[len + id - c[id]] * 1LL * qt[id] << endl;
		}
		//cout << endl;
	}
	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);
			//cout << " <<<- " << c[id - prev] + cycn + id - prev << " " << qt[id - prev] << endl;
			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]);
		//cout << " ->>> " << cycn + (id - prev + 1) + c[id - prev + 1] << " " << qt[id - prev + 1] << endl;
		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 << mx << endl;
	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
*/
/*
12
5 11
5 4
4 3
3 6
11 7
11 10
4 9
11 12
4 1
5 8
11 2
6 2
*/

Compilation message

shymbulak.cpp: In function 'void dfs(int, int)':
shymbulak.cpp:30: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:54: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:104: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:149: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:156:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:165: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	5 ms	5240 KB	Output is correct
2	Correct	5 ms	5368 KB	Output is correct
3	Correct	5 ms	5448 KB	Output is correct
4	Correct	5 ms	5448 KB	Output is correct
5	Correct	5 ms	5448 KB	Output is correct
6	Correct	5 ms	5452 KB	Output is correct
7	Correct	5 ms	5468 KB	Output is correct
8	Correct	5 ms	5472 KB	Output is correct
9	Correct	5 ms	5480 KB	Output is correct
10	Correct	5 ms	5480 KB	Output is correct
11	Correct	5 ms	5484 KB	Output is correct
12	Correct	5 ms	5504 KB	Output is correct
13	Correct	5 ms	5504 KB	Output is correct
14	Correct	5 ms	5632 KB	Output is correct
15	Correct	6 ms	5632 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5760 KB	Output is correct
2	Correct	7 ms	5760 KB	Output is correct
3	Correct	7 ms	5776 KB	Output is correct
4	Correct	7 ms	5776 KB	Output is correct
5	Correct	10 ms	6296 KB	Output is correct
6	Correct	12 ms	6472 KB	Output is correct
7	Correct	11 ms	6520 KB	Output is correct
8	Correct	11 ms	6560 KB	Output is correct
9	Correct	9 ms	6580 KB	Output is correct
10	Correct	11 ms	6656 KB	Output is correct

Subtask #3
50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	214 ms	21796 KB	Output is correct
2	Correct	251 ms	23084 KB	Output is correct
3	Correct	179 ms	34660 KB	Output is correct
4	Correct	103 ms	34660 KB	Output is correct
5	Correct	115 ms	34660 KB	Output is correct
6	Correct	554 ms	36436 KB	Output is correct
7	Correct	466 ms	36436 KB	Output is correct
8	Correct	249 ms	39508 KB	Output is correct
9	Correct	292 ms	39860 KB	Output is correct
10	Correct	256 ms	41300 KB	Output is correct
11	Correct	1041 ms	41300 KB	Output is correct
12	Correct	1143 ms	41300 KB	Output is correct

답안 #91181

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