oj.uz

Submission #393543

# Submission time Handle Problem Language Result Execution time Memory
393543 2021-04-23T22:10:41 Z asbsfds Shymbulak (IZhO14_shymbulak) C++14
100 / 100
 162 ms 48408 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 38796 KB Output is correct
2 Correct 21 ms 38804 KB Output is correct
3 Correct 23 ms 38776 KB Output is correct
4 Correct 20 ms 38732 KB Output is correct
5 Correct 24 ms 38732 KB Output is correct
6 Correct 21 ms 38800 KB Output is correct
7 Correct 22 ms 38732 KB Output is correct
8 Correct 21 ms 38728 KB Output is correct
9 Correct 21 ms 38732 KB Output is correct
10 Correct 21 ms 38800 KB Output is correct
11 Correct 21 ms 38736 KB Output is correct
12 Correct 21 ms 38784 KB Output is correct
13 Correct 21 ms 38752 KB Output is correct
14 Correct 22 ms 38800 KB Output is correct
15 Correct 22 ms 38900 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 38884 KB Output is correct
2 Correct 21 ms 38732 KB Output is correct
3 Correct 23 ms 39000 KB Output is correct
4 Correct 22 ms 38732 KB Output is correct
5 Correct 23 ms 38988 KB Output is correct
6 Correct 23 ms 38964 KB Output is correct
7 Correct 24 ms 38940 KB Output is correct
8 Correct 23 ms 38988 KB Output is correct
9 Correct 23 ms 38988 KB Output is correct
10 Correct 24 ms 39028 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 42860 KB Output is correct
2 Correct 82 ms 43216 KB Output is correct
3 Correct 92 ms 47260 KB Output is correct
4 Correct 62 ms 43076 KB Output is correct
5 Correct 66 ms 43108 KB Output is correct
6 Correct 162 ms 46572 KB Output is correct
7 Correct 116 ms 45216 KB Output is correct
8 Correct 111 ms 47680 KB Output is correct
9 Correct 112 ms 47724 KB Output is correct
10 Correct 102 ms 48408 KB Output is correct
11 Correct 112 ms 47808 KB Output is correct
12 Correct 115 ms 48168 KB Output is correct