Submission #393543

#	Time	Username	Problem	Language	Result	Execution time	Memory
393543		asbsfds	Shymbulak (IZhO14_shymbulak)	C++14	100 / 100	162 ms	48408 KiB

shymbulak

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 2e5+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;

int n;
vector< int > graph[maxn];
vector< int > cik;
bool bio[maxn];
int dis[maxn];
pair<int, llint> tour[treesiz];
pair<int, llint> p[maxn];
pair<int, llint> sol = make_pair(0, 0);

pair<int, llint> add(pair<int, llint> a, pair<int, llint> b) {
	if (a.X < b.X) swap(a, b);
	
	int x = a.X;
	llint y = a.Y;
	if (a.X == b.X) y += b.Y;
	return make_pair(x, y);
}

pair<int, llint> con(pair<int, llint> a, pair<int, llint> b) {
	return make_pair(a.X + b.X, a.Y * b.Y);
}

void update(int x, pair<int, llint> val) {
	x += off;
	tour[x] = add(tour[x], val);
	
	x /= 2;
	while (x > 0) tour[x] = add(tour[x * 2], tour[x * 2 + 1]), x /= 2;
}

pair<int, llint> query(int a, int b, int l, int r, int node) {
	if (l > b || r < a) return make_pair(-inf, 0);
	if (l >= a && r <= b) return tour[node];
	
	int mid = (l + r) / 2;
	return add(query(a, b, l, mid, node * 2), query(a, b, mid + 1, r, node * 2 + 1));
}

int dfs(int x, int parr) {
	int out = inf;
	if (dis[x] == -1) dis[x] = 1;
	for (int i = 0; i < graph[x].size(); i++) {
		int tren = graph[x][i];
		if (tren == parr) continue;
		
		if (dis[tren] != -1) out = min(out, dis[tren]);
		else {
			dis[tren] = 1 + dis[x];
			out = min(out, dfs(tren, x));
		}
	}
	if (out <= dis[x]) cik.push_back(x);
	return out;
}

pair<int, llint> f(int x, int parr) {
	pair<int, llint> out = make_pair(0, 1);
	for (int i = 0; i < graph[x].size(); i++) {
		int tren = graph[x][i];
		if (tren == parr || bio[tren]) continue;
		
		pair<int, llint> tr = f(tren, x);
		sol = add(sol, con(out, tr));
		out = add(out, tr);
	}
	out.X++;
	return out;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	
	memset(dis, -1, sizeof dis);
	dfs(1, -1);
	
	memset(bio, false, sizeof bio);
	for (int i = 0; i < cik.size(); i++) {
		bio[cik[i]] = true;
	}
	//for (int i = 0; i < cik.size(); i++) printf("%d ", cik[i]); printf("\n");
	
	for (int i = 0; i < treesiz; i++) tour[i] = make_pair(-inf, 0);
	
	int siz = cik.size();
	for (int i = 0; i < siz; i++) {
		p[i] = f(cik[i], -1); p[i].X--;
		update(i, make_pair(p[i].X - i, p[i].Y));
	}
	
	int hf = cik.size() / 2;
	for (int i = 0; i < siz; i++) {
		pair<int, llint> a = query(max(0, i - hf), i - 1, 0, off - 1, 1); 
		a.first += i;
		
		pair<int, llint> b = query(min(siz - 1, i + hf - ((siz % 2) == 0)) + 1, siz - 1, 0, off - 1, 1);
		b.first += siz + i;
		sol = add(sol, con(p[i], add(a, b)));
		
		//printf("debug: %d %lld %d %lld\n", add(a, b).X, add(a, b).Y, p[i].X, p[i].Y);
		//printf("%d (%d %lld) (%d %lld)\n", i, a.X, a.Y, b.X, b.Y);
	}
	//printf("length: %d\n", sol.first);
	printf("%lld\n", sol.second);
	return 0;
}

Compilation message (stderr)

shymbulak.cpp: In function 'int dfs(int, int)':
shymbulak.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for (int i = 0; i < graph[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
shymbulak.cpp: In function 'std::pair<int, long long int> f(int, int)':
shymbulak.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for (int i = 0; i < graph[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:98:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |  for (int i = 0; i < cik.size(); i++) {
      |                  ~~^~~~~~~~~~~~
shymbulak.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
shymbulak.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   89 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

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