Submission #145705

#	Time	Username	Problem	Language	Result	Execution time	Memory
145705		abacaba	Shymbulak (IZhO14_shymbulak)	C++14	0 / 100	1554 ms	8568 KiB

shymbulak

#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)
	// 	printf("%d\n", n);
	// 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(!cycle[i] && !cycle[j])
						ans += 1;
					else if(cnt_cycle & 1)
						ans += 1;
					else
						ans += 2;
				}
			}
		}
		printf("%lld\n", ans);
	// }
	return 0;
}

Compilation message (stderr)

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:120:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
shymbulak.cpp:123: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: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50