oj.uz

Submission #392505

# Submission time Handle Problem Language Result Execution time Memory
392505 2021-04-21T09:11:29 Z patrikpavic2 Shymbulak (IZhO14_shymbulak) C++17
50 / 100
 58 ms 22848 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair < int, ll > pil;

const int N = 2e5 + 500;
const int OFF = (1 << 18);

pil add(pil A, pil B){
	return {max(A.X, B.X), A.Y * (A.X >= B.X) + B.Y * (B.X >= A.X)};
}

pil mul(pil A, pil B){
	return {A.X + B.X, A.Y * B.Y};
}

int un[N], n;
vector < int > v[N];
vector < int > cik;
pil sol = {0, 0};

pil T[2 * OFF], ja[N];

pil f(int x, int lst){
	pil dep = {0, 1};
	for(int y : v[x]){
		if(y == lst || un[y]) continue;
		pil nxt = f(y, x);
		sol = add(sol, mul(dep, nxt));
		dep = add(dep, nxt);
	}
	dep.X++;
	return dep;
}

int bio[N];
stack < int > S;

void dfs(int x, int lst){
	if((int)cik.size() != 0) return;
	if(bio[x]){
		cik.PB(x);
		while(S.top() != x)
			cik.PB(S.top()), S.pop();
		return;			
	}
	bio[x] = 1;
	S.push(x);
	for(int y : v[x])
		if(y != lst)
			dfs(y, x);
	S.pop();
}

pil query(int i, int a, int b, int lo, int hi){
	if(lo <= a && b <= hi) return T[i];
	if(a > hi || b < lo) return {-N, 0};
	return add(query(2 * i, a, (a + b) / 2, lo, hi), query(2 * i + 1, (a + b) / 2 + 1, b, lo, hi));
}

int main(){
	scanf("%d", &n);
	for(int i = 0;i < n;i++){
		int x, y; scanf("%d%d", &x, &y);
		v[x].PB(y), v[y].PB(x);
	}
	dfs(1, 1);
	for(int x : cik) un[x] = 1;
	for(int i = 0;i < OFF;i++)
		T[OFF + i].X = -N;
	for(int i = 0;i < (int)cik.size();i++){
		ja[i] = f(cik[i], cik[i]); ja[i].X--;
		T[OFF + i] = {ja[i].X - i, ja[i].Y};
	}
	for(int i = OFF - 1; i ; i--){
		T[i] = add(T[2 * i], T[2 * i + 1]);
	}
	int kol = (int)cik.size() / 2, m = (int)cik.size();
	for(int i = 0;i < m;i++){
		pil L = query(1, 0, OFF - 1, max(0, i - kol), i - 1); L.X += i;
		pil RR = query(1, 0, OFF - 1, min(m - 1, i + kol - !(m&1)) + 1, m - 1); RR.X += m + i;
		sol = add(sol, mul(add(L, RR), ja[i]));
	}
	printf("%lld\n", sol.Y);
	return 0;
}

Compilation message

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
shymbulak.cpp:73:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |   int x, y; scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13132 KB Output is correct
2 Correct 8 ms 13132 KB Output is correct
3 Correct 8 ms 13132 KB Output is correct
4 Correct 8 ms 13208 KB Output is correct
5 Correct 8 ms 13160 KB Output is correct
6 Correct 7 ms 13132 KB Output is correct
7 Correct 8 ms 13136 KB Output is correct
8 Correct 8 ms 13132 KB Output is correct
9 Correct 8 ms 13132 KB Output is correct
10 Correct 8 ms 13228 KB Output is correct
11 Correct 9 ms 13260 KB Output is correct
12 Correct 8 ms 13204 KB Output is correct
13 Correct 8 ms 13132 KB Output is correct
14 Correct 9 ms 13132 KB Output is correct
15 Correct 9 ms 13208 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13260 KB Output is correct
2 Correct 8 ms 13224 KB Output is correct
3 Correct 9 ms 13176 KB Output is correct
4 Correct 8 ms 13132 KB Output is correct
5 Correct 10 ms 13388 KB Output is correct
6 Correct 9 ms 13388 KB Output is correct
7 Correct 10 ms 13308 KB Output is correct
8 Correct 10 ms 13388 KB Output is correct
9 Correct 10 ms 13388 KB Output is correct
10 Correct 10 ms 13344 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 16460 KB Output is correct
2 Correct 58 ms 16964 KB Output is correct
3 Runtime error 50 ms 22848 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -