Submission #91126

#	Time	Username	Problem	Language	Result	Execution time	Memory
91126		Just_Solve_The_Problem	Shymbulak (IZhO14_shymbulak)	C++11	0 / 100	1576 ms	15800 KiB

shymbulak

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define int long long

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

vector < int > gr[N];
int n;
int used[N], deg[N];
ll ans = 0;
int diam;
int dist[N], us[N], id[N];
vector < int > node;

void bfs(int v) {
	memset(used, 0, sizeof used);
	queue < int > q;
	q.push(v);
	used[v] = 1;
	while (!q.empty()) {
		v = q.front();
		q.pop();
		for (int to : gr[v]) {
			if (used[to] == 0) {
				used[to] = used[v] + 1;
				q.push(to);
			}
		}
	}
}

void bfs1(int v) {
	memset(dist, 0, sizeof dist);
	queue < int > q;
	q.push(v);
	dist[v] = 1;
	int asd = v;
	int res = 0;
	int mx = 0;
	while (!q.empty()) {
		v = q.front();
		q.pop();
		for (int to : gr[v]) {
			if (dist[to] == 0) {
				dist[to] = dist[v] + 1;
				mx = max(mx, dist[to]);
				q.push(to);
			} else if (dist[v] + 1 == dist[to]) {
				res = id[to];
			}
		}
	}
	if (mx - 1 == diam) {
		int val = 0;
		for (int i = 1; i <= n; i++) {
			if (mx == dist[i]) val++;
		}
		ans += val;
		if (res) {
			val = 0;
			for (int i = 1; i <= n; i++) {
				if (id[i] == res && dist[i] == mx) val++;
			} 
			ans += val;
		}
	}
}

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);
	}
}

void dfs2(int v, int pr) {
	for (int to : gr[v]) {
		if (to == pr || used[to] == 2) continue;
		id[to] = id[v];
		dfs2(to, v);
	}
}

main() {
	iota(id, id + N, 0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int u, v;
		cin >> u >> v;
		gr[u].push_back(v);
		gr[v].push_back(u);
		deg[u]++;
		deg[v]++;
	}
	int mx = 0;
	bfs(1);
	for (int i = 1; i <= n; i++) {
		if (used[i] > used[mx]) mx = i;
	} 
	bfs(mx);
	mx = 0;
	for (int i = 1; i <= n; i++) {
		if (used[i] > used[mx]) {
			mx = i;
		}
	}
	diam = used[mx] - 1;
	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) {
			dfs2(i, i);
		}
	}
	for (int i = 1; i <= n; i++) {
		bfs1(i);
	}
	cout << ans / 2;
}

Compilation message (stderr)

shymbulak.cpp: In function 'void bfs1(long long int)':
shymbulak.cpp:40:6: warning: unused variable 'asd' [-Wunused-variable]
  int asd = v;
      ^~~
shymbulak.cpp: At global scope:
shymbulak.cpp:89:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:120:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i == node.size()) {
       ~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50