답안 #91187 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
91187	2018-12-26T13:31:29 Z	daniel_02	관광지 (IZhO14_shymbulak)	C++17	100 / 100	884 ms	44552 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 = 3e5 + 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	8 ms	7672 KB	Output is correct
2	Correct	8 ms	7808 KB	Output is correct
3	Correct	8 ms	7808 KB	Output is correct
4	Correct	9 ms	7904 KB	Output is correct
5	Correct	8 ms	7904 KB	Output is correct
6	Correct	8 ms	7952 KB	Output is correct
7	Correct	8 ms	7952 KB	Output is correct
8	Correct	8 ms	7952 KB	Output is correct
9	Correct	7 ms	7960 KB	Output is correct
10	Correct	8 ms	7960 KB	Output is correct
11	Correct	8 ms	7960 KB	Output is correct
12	Correct	7 ms	7996 KB	Output is correct
13	Correct	7 ms	7996 KB	Output is correct
14	Correct	7 ms	8064 KB	Output is correct
15	Correct	8 ms	8064 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	8192 KB	Output is correct
2	Correct	9 ms	8192 KB	Output is correct
3	Correct	9 ms	8388 KB	Output is correct
4	Correct	9 ms	8388 KB	Output is correct
5	Correct	13 ms	8904 KB	Output is correct
6	Correct	15 ms	8932 KB	Output is correct
7	Correct	14 ms	8980 KB	Output is correct
8	Correct	14 ms	9104 KB	Output is correct
9	Correct	13 ms	9104 KB	Output is correct
10	Correct	13 ms	9116 KB	Output is correct

Subtask #3
50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	293 ms	25032 KB	Output is correct
2	Correct	255 ms	26708 KB	Output is correct
3	Correct	137 ms	34292 KB	Output is correct
4	Correct	107 ms	34292 KB	Output is correct
5	Correct	112 ms	34292 KB	Output is correct
6	Correct	647 ms	40200 KB	Output is correct
7	Correct	362 ms	40200 KB	Output is correct
8	Correct	256 ms	43144 KB	Output is correct
9	Correct	244 ms	43480 KB	Output is correct
10	Correct	209 ms	44552 KB	Output is correct
11	Correct	835 ms	44552 KB	Output is correct
12	Correct	884 ms	44552 KB	Output is correct

답안 #91187

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