oj.uz

답안 #91150

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
91150 2018-12-26T11:51:48 Z Just_Solve_The_Problem 관광지 (IZhO14_shymbulak) C++11
100 / 100
 796 ms 21996 KB 
#include <stdio.h>
#include <vector>
#include <utility>
#include <memory.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>

using namespace std;

#define ok puts("ok");
#define ll long long

const int N = (int)2e5 + 7;

vector < int > gr[N];
int n;
int used[N];
ll ans = 0;

int diam;
vector < int > node;
int deg[N];
int sz[N], isdel[N];
map < int, ll > mp1, mp2;

void precalc(int v, int pr) {
	sz[v] = 1;
	for (int to : gr[v]) {
		if (to == pr || used[to] == 2 || isdel[to]) continue;
		precalc(to, v);
		sz[v] += sz[to];
	}
}

int findcentroid(int v) {
	int cur = v;
	int pr = v;
	bool run = 1;
	while (run) {
		run = 0;
		for (int to : gr[cur]) {
			if (to == pr || (used[to] == 2) || isdel[to]) continue;
			if (sz[to] * 2 >= sz[v]) {
				run = 1;
				pr = cur;
				cur = to;
				break;
			}
		}
	}
	return cur;
}

int cnt[N][20];

void calc(int v, int pr, int val, int d, int dep) {
	cnt[d][dep] += val;
	for (int to : gr[v]) {
		if (to == pr || used[to] == 2 || isdel[to]) continue;
		calc(to, v, val, d + 1, dep);
	}
} 

ll res;

void calc1(int v, int pr, int d, int dep) {
	res += cnt[diam - d][dep];
	for (int to : gr[v]) {
		if (to == pr || used[to] == 2 || isdel[to]) continue;
		calc1(to, v, d + 1, dep);
	}
}

void decompose(int v, int dep) {
	precalc(v, v);
	int cen = findcentroid(v);
	isdel[cen] = 1;
	calc(cen, cen, 1, 0, dep);
	res = 0;
	res += cnt[diam][dep];
	for (int to : gr[cen]) {
		if (isdel[to] || used[to] == 2) continue;
		calc(to, cen, -1, 1, dep);
		calc1(to, cen, 1, dep);
		calc(to, cen, 1, 1, dep);
	}
	res /= 2;
	ans += res;
	calc(cen, cen, -1, 0, dep);
	for (int to : gr[cen]) {
		if (isdel[to] || used[to] == 2) continue;
		decompose(to, dep + 1);
	}
}

pair < int, int > mxh[N];

void dfs(int v, int pr) {
	bool asd = 0;
	for (int to : gr[v]) {
		if (to == pr || used[to] == 2) continue;
		dfs(to, v);
		asd = 1;
		if (mxh[to].first == mxh[v].first) {
			mxh[v].second += mxh[to].second;
		} else if (mxh[to].first > mxh[v].first) {
			mxh[v] = mxh[to];
		}
	}
	if (!asd) {
		mxh[v] = {0, 1};
	} else
		mxh[v].first++;
}

int us[N];

void dfs1(int v, int pr) {
	node.push_back(v);
	us[v] = 1;
	for (int to : gr[v]) {
		if (us[to] || used[to] != 2) continue;
		dfs1(to, v);
	}
}

int dd[N];
pair < int, int > tamer;

void dfs3(int v, int pr) {
	if (dd[v] > tamer.first) {
		tamer.first = dd[v];
		tamer.second = v;
	}
	for (int to : gr[v]) {
		if (to == pr || used[to] == 2) continue;
		dd[to] = dd[v] + 1;
		dfs3(to, v);
	}
}

main() {
	//freopen("shymbulak.in", "r", stdin);
	//freopen("shymbulak.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		gr[u].push_back(v);
		gr[v].push_back(u);
		deg[u]++;
		deg[v]++;
	}
	for (int i = 1; i <= n; i++) {
		if (gr[i].size() == 1) {
			node.push_back(i);
		}
	}
	memset(used, 0, sizeof used);
	for (int i = 0; i < n; i++) {
		if (i == node.size()) {
			break;
		}
		int v = node[i];
		used[v] = 1;
		for (int to : gr[v]) {
			if (!used[to]) {
				deg[to]--;
				if (deg[to] <= 1) {
					node.push_back(to);
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!used[i]) {
			used[i] = 2;
		}
	}
	while (!node.empty()) node.pop_back();
	for (int i = 1; i <= n; i++) {
		if (used[i] == 2) {
			dfs1(i, i);
			break;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (used[i] == 2) {
			dfs(i, i);
		}
	}
	////
	int h1, cur;
	multiset < pair < int, int > > S, s1;
	h1 = node.size() / 2;
	for (int i = 0; i < h1; i++) {
		S.insert({mxh[node[i]].first - i, node[i]});
	}
	for (int i = h1; i < node.size(); i++) {
		pair < int, int > v = *S.rbegin();
		diam = max(diam, mxh[node[i]].first + i + v.first);
		int lst = i - h1;
		S.erase(S.find({mxh[node[lst]].first - lst, node[lst]}));
		S.insert({mxh[node[i]].first - i, node[i]});
	}
	for (int i = node.size() - h1; i < node.size(); i++) {
		s1.insert({(int)node.size() - i + mxh[node[i]].first, node[i]});
	}
	for (int i = 0; i < h1; i++) {
		pair < int, int > v = *s1.rbegin();
		diam = max(diam, mxh[node[i]].first + i + v.first);
		int lst = i - h1 + (int)node.size();
		s1.erase(s1.find({(int)node.size() - lst + mxh[node[lst]].first, node[lst]}));
		s1.insert({mxh[node[i]].first - i, node[i]});
	}
	// finding tree diameter
	for (int i = 1; i <= n; i++) {
		if (used[i] == 2) {
			tamer.first = -1;
			used[i] = 1;
			dd[i] = 0;
			dfs3(i, i);
			//cout << i << ' ' << tamer.first << ' ' << tamer.second << endl;
			tamer.first = -1;
			dd[tamer.second] = 0;
			dfs3(tamer.second, tamer.second);
			//cout << i << ' ' << tamer.first << ' ' << tamer.second << endl;
			diam = max(diam, tamer.first);
			used[i] = 2;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (used[i] == 2) {
			used[i] = 1;
			decompose(i, 0);
			used[i] = 2;
		}
	}
	h1 = node.size() / 2;
	if (node.size() & 1 ^ 1) h1--;
	for (int i = 0; i < h1; i++) {
		mp1[-i + mxh[node[i]].first] += mxh[node[i]].second;
	}
	cur = h1;
	res = 0;
	while (cur < (int)node.size()) {
		res += mp1[diam - mxh[node[cur]].first - cur] * 1LL * mxh[node[cur]].second;
		int lst = cur - h1;
		mp1[-lst + mxh[node[lst]].first] -= mxh[node[lst]].second;
		mp1[-cur + mxh[node[cur]].first] += mxh[node[cur]].second;
		cur++;
	}
	for (int i = (int)node.size() - h1; i < node.size(); i++) {
		mp2[(int)node.size() - i + mxh[node[i]].first] += mxh[node[i]].second;
	}
	cur = 0;
	while (cur < h1) {
		res += mp2[diam - mxh[node[cur]].first - cur] * 1LL * mxh[node[cur]].second;
		int lst = cur - h1 + (int)node.size();
		mp2[(int)node.size() - lst + mxh[node[lst]].first] -= mxh[node[lst]].second;
		mp2[-cur + mxh[node[cur]].first] += mxh[node[cur]].second;
		cur++;
	}
	// assert(res & 1 ^ 1);
	ans += res;
	res = 0;
	if ((int)node.size() & 1 ^ 1) {
		h1 = node.size() / 2;
		for (int i = 0; i < node.size(); i++) {
			int lst = i - h1;
			if (lst < 0) lst += (int)node.size();
			if (diam - h1 == mxh[node[i]].first + mxh[node[lst]].first) {
				res += mxh[node[i]].second * 1LL * mxh[node[lst]].second;
			}
		}
		ans += res;
	}
	cout << ans;
}

Compilation message

shymbulak.cpp:144:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:163:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i == node.size()) {
       ~~^~~~~~~~~~~~~~
shymbulak.cpp:201:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = h1; i < node.size(); i++) {
                   ~~^~~~~~~~~~~~~
shymbulak.cpp:208:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = node.size() - h1; i < node.size(); i++) {
                                 ~~^~~~~~~~~~~~~
shymbulak.cpp:242:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  if (node.size() & 1 ^ 1) h1--;
      ~~~~~~~~~~~~^~~
shymbulak.cpp:255:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = (int)node.size() - h1; i < node.size(); i++) {
                                      ~~^~~~~~~~~~~~~
shymbulak.cpp:269:23: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  if ((int)node.size() & 1 ^ 1) {
      ~~~~~~~~~~~~~~~~~^~~
shymbulak.cpp:271:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < node.size(); i++) {
                   ~~^~~~~~~~~~~~~
shymbulak.cpp:147:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
shymbulak.cpp:150: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.0 / 30.0

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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 6224 KB Output is correct
2 Correct 6 ms 6224 KB Output is correct
3 Correct 6 ms 6224 KB Output is correct
4 Correct 12 ms 6224 KB Output is correct
5 Correct 9 ms 6352 KB Output is correct
6 Correct 8 ms 6368 KB Output is correct
7 Correct 12 ms 6368 KB Output is correct
8 Correct 11 ms 6408 KB Output is correct
9 Correct 10 ms 6544 KB Output is correct
10 Correct 11 ms 6572 KB Output is correct

Subtask #3
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 290 ms 11868 KB Output is correct
2 Correct 197 ms 12392 KB Output is correct
3 Correct 98 ms 21996 KB Output is correct
4 Correct 89 ms 21996 KB Output is correct
5 Correct 105 ms 21996 KB Output is correct
6 Correct 796 ms 21996 KB Output is correct
7 Correct 350 ms 21996 KB Output is correct
8 Correct 199 ms 21996 KB Output is correct
9 Correct 232 ms 21996 KB Output is correct
10 Correct 144 ms 21996 KB Output is correct
11 Correct 247 ms 21996 KB Output is correct
12 Correct 291 ms 21996 KB Output is correct