oj.uz

답안 #91130

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
91130 2018-12-26T10:36:34 Z Just_Solve_The_Problem 관광지 (IZhO14_shymbulak) C++11
30 / 100
 1500 ms 14232 KB 
#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;
	for (int i = 1; i <= n; i++) {
		bfs(i);
		for (int j = 1; j <= n; j++) {
			mx = max(mx, used[j]);
		}
	}
	diam = 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

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:115:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i == node.size()) {
       ~~^~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 9720 KB Output is correct
2 Correct 9 ms 9720 KB Output is correct
3 Correct 10 ms 9756 KB Output is correct
4 Correct 9 ms 9832 KB Output is correct
5 Correct 11 ms 9896 KB Output is correct
6 Correct 13 ms 9896 KB Output is correct
7 Correct 12 ms 9896 KB Output is correct
8 Correct 13 ms 9904 KB Output is correct
9 Correct 13 ms 9924 KB Output is correct
10 Correct 12 ms 9928 KB Output is correct
11 Correct 13 ms 9932 KB Output is correct
12 Correct 12 ms 9936 KB Output is correct
13 Correct 34 ms 10000 KB Output is correct
14 Correct 92 ms 10192 KB Output is correct
15 Correct 88 ms 10192 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 10192 KB Output is correct
2 Correct 141 ms 10192 KB Output is correct
3 Correct 180 ms 10192 KB Output is correct
4 Correct 185 ms 10192 KB Output is correct
5 Execution timed out 1532 ms 10464 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1573 ms 14232 KB Time limit exceeded
2 Halted 0 ms 0 KB -