oj.uz

Submission #392511

# Submission time Handle Problem Language Result Execution time Memory
392511 2021-04-21T09:27:28 Z patrikpavic2 Shymbulak (IZhO14_shymbulak) C++17
100 / 100
 150 ms 24388 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;
	char c; scanf(" %c", &c);
	if(bio[x]){
		cik.PB(x);
		while(S.top() != x){
			cik.PB(S.top()); S.pop();
		}
		return;			
	}
	S.push(x); bio[x] = 1;
	for(int y : v[x]){
		if(y != lst)
			dfs(y, x);
		if((int)cik.size() != 0) return;			
	}
	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 'void dfs(int, int)':
shymbulak.cpp:50:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |  char c; scanf(" %c", &c);
      |          ~~~~~^~~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
shymbulak.cpp:76:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |   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 13132 KB Output is correct
5 Correct 9 ms 13132 KB Output is correct
6 Correct 10 ms 13188 KB Output is correct
7 Correct 8 ms 13200 KB Output is correct
8 Correct 9 ms 13204 KB Output is correct
9 Correct 8 ms 13132 KB Output is correct
10 Correct 8 ms 13132 KB Output is correct
11 Correct 8 ms 13132 KB Output is correct
12 Correct 8 ms 13204 KB Output is correct
13 Correct 8 ms 13200 KB Output is correct
14 Correct 8 ms 13132 KB Output is correct
15 Correct 8 ms 13132 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 13260 KB Output is correct
2 Correct 8 ms 13260 KB Output is correct
3 Correct 9 ms 13260 KB Output is correct
4 Correct 9 ms 13208 KB Output is correct
5 Correct 11 ms 13336 KB Output is correct
6 Correct 11 ms 13388 KB Output is correct
7 Correct 11 ms 13388 KB Output is correct
8 Correct 12 ms 13388 KB Output is correct
9 Correct 10 ms 13388 KB Output is correct
10 Correct 10 ms 13388 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 16452 KB Output is correct
2 Correct 77 ms 18032 KB Output is correct
3 Correct 94 ms 23488 KB Output is correct
4 Correct 47 ms 18244 KB Output is correct
5 Correct 49 ms 18300 KB Output is correct
6 Correct 150 ms 21800 KB Output is correct
7 Correct 138 ms 20292 KB Output is correct
8 Correct 89 ms 23372 KB Output is correct
9 Correct 92 ms 22956 KB Output is correct
10 Correct 89 ms 24388 KB Output is correct
11 Correct 140 ms 22912 KB Output is correct
12 Correct 134 ms 23424 KB Output is correct