답안 #145699

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
145699 2019-08-20T19:03:43 Z abacaba 관광지 (IZhO14_shymbulak) C++14
0 / 100
1500 ms 8568 KB
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <deque>
using namespace std;

#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>

const int inf = 2e9;
const int N = 5e3 + 15;
int n, tin[N], fup[N], last, parent[N], d[N], dist[N][N];
vector <int> g[N];
bool used[N], is[N], cycle[N], whole_cycle = true;
int vertex, cnt_cycle;
ll ans;
void find_points(int v, int p = -1) {
	used[v] = true;
	tin[v] = fup[v] = last++;
	int child = 0;
	for(int to : g[v]) {
		if(to != p) {
			if(used[to])
				fup[v] = min(fup[v], tin[to]);
			else {
				find_points(to, v);
				fup[v] = min(fup[v], fup[to]);
				if(fup[to] >= tin[v] && p != -1)
					is[v] = true;
				++child;
			}
		}
	}
	if(child > 1 && p == -1)
		is[v] = true;
}

bool find_cycle(int v, int p = -1) {
	used[v] = true;
	parent[v] = p;
	for(int to : g[v]) {
		if(to != p) {
			if(used[to]) {
				int u = v;
				cycle[u] = true;
				++cnt_cycle;
				while(u != to) {
					++cnt_cycle;
					u = parent[u];
					cycle[u] = true;
				}
				return true;
			}
			else if(find_cycle(to, v))
				return true;
		}
	}
	return false;
}

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

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

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		g[u].pb(v);
		g[v].pb(u);
	}
	for(int i = 1; i <= n; ++i) {
		if(g[i].size() != 2) {
			whole_cycle = false;
			break;
		}
	}
	if(whole_cycle)
		cout << n << endl;
	else {
		find_cycle(1);
		memset(used, 0, sizeof(used));
		find_points(1);
		for(int i = 1; i <= n; ++i)
			if(is[i] && cycle[i]) {
				vertex = i;
				break;
			}
		for(int i = 1; i <= n; ++i)
			bfs_all(i);
		int maxx = 0;
		for(int i = 1; i <= n; ++i)
			for(int j = i + 1; j <= n; ++j)
				maxx = max(dist[i][j], maxx);
		for(int i = 1; i <= n; ++i) {
			for(int j = i + 1; j <= n; ++j) {
				if(dist[i][j] == maxx) {
					if(cnt_cycle & 1 || (!cycle[i] && !cycle[j]))
						ans += 1;
					else
						ans += 2;
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Compilation message

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:119:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
shymbulak.cpp:122:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Incorrect 2 ms 504 KB Output isn't correct
7 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 15 ms 6236 KB Output is correct
3 Incorrect 27 ms 8568 KB Output isn't correct
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1556 ms 6776 KB Time limit exceeded
2 Halted 0 ms 0 KB -