oj.uz

답안 #205087

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
205087 2020-02-27T21:01:05 Z BorisBarca Lampice (COCI19_lampice) C++14
73 / 110
 5000 ms 10104 KB 
/*
$$$$$$$\                      $$\           $$$$$$$\
$$  __$$\                     \__|          $$  __$$\
$$ |  $$ | $$$$$$\   $$$$$$\  $$\  $$$$$$$\ $$ |  $$ | $$$$$$\   $$$$$$\   $$$$$$$\ $$$$$$\
$$$$$$$\ |$$  __$$\ $$  __$$\ $$ |$$  _____|$$$$$$$\ | \____$$\ $$  __$$\ $$  _____|\____$$\
$$  __$$\ $$ /  $$ |$$ |  \__|$$ |\$$$$$$\  $$  __$$\  $$$$$$$ |$$ |  \__|$$ /      $$$$$$$ |
$$ |  $$ |$$ |  $$ |$$ |      $$ | \____$$\ $$ |  $$ |$$  __$$ |$$ |      $$ |     $$  __$$ |
$$$$$$$  |\$$$$$$  |$$ |      $$ |$$$$$$$  |$$$$$$$  |\$$$$$$$ |$$ |      \$$$$$$$\\$$$$$$$ |
\_______/  \______/ \__|      \__|\_______/ \_______/  \_______|\__|       \_______|\_______|
*/
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
 
using namespace std;
 
#define PB push_back
#define MP make_pair
#define INS insert
#define LB lower_bound
#define UB upper_bound
#define pii pair <int,int>
#define pll pair <long long, long long>
#define si pair<string, int>
#define is pair<int, string>
#define X first
#define Y second
#define _ << " " <<
#define sz(x) (int)x.size()
#define all(a) (a).begin(),(a).end()
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORD(i, a, b) for (int i = (a); i > (b); --i)
#define FORR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FORP(i, a, b) for ((i) = (a); (i) < (b); ++i)
#define FORA(i, x) for (auto &i : x)
#define REP(i, n) FOR(i, 0, n)
#define BITS(x) __builtin_popcount(x)
#define MSET memset
#define MCPY memcpy
#define SQ(a) (a) * (a)
#define TRACE(x) cout << #x " = " << (x) << '\n';
#define YES cout << "YES\n"
#define NO cout << "NO\n"
 
typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef vector <pii> vpi;
typedef vector <ll> vll;
typedef vector <pll> vpl;
typedef vector <double> vd;
typedef vector <ld> vld;
typedef vector<si> vsi;
typedef vector<is> vis;
typedef vector<string> vs;
//((float) t)/CLOCKS_PER_SEC
 
const int MOD = 1e9 + 7;
const double PI = acos(-1);
const int INF = 1e9 + 10;
const ll INFL = 1e18 + 10;
const int ABC = 30;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dox[] = {-1, 1, 0, 0, -1, -1, 1, 1};
const int doy[] = {0, 0, -1, 1, -1, 1, -1, 1};
 
inline int sum(int a, int b){
	if (a + b < 0)
		return (a + b + MOD) % MOD;
	return (a + b) % MOD;
}
 
inline void add(int &a, int b){
	a = sum(a, b);
}
 
inline int mul(int a, int b){
	return (ll)a * (ll)b % MOD;
}
 
inline int sub(int a, int b){
	return (a - b + MOD) % MOD;
}
 
inline int fast_pot(ll pot, int n){
	ll ret = 1;
	while (n){
		if (n & 1)
			ret = (ret * pot) % MOD;
			pot = (pot * pot) % MOD;
			n >>= 1;
		}
	return ret;
}
 
inline int divide(int a, int b){
	return mul(a, fast_pot(b, MOD - 2));
}
 
ll lcm(ll a, ll b){
	return abs(a * b) / __gcd(a, b);
}
 
inline double ccw(pii A, pii B, pii C){
	return (A.X * B.Y) - (A.Y * B.X) + (B.X * C.Y) - (B.Y * C.X) + (C.X * A.Y) - (C.Y * A.X);
}
 
inline int CCW(pii A, pii B, pii C){
	double val = ccw(A, B, C);
	double eps = max(max(abs(A.X), abs(A.Y)), max(max(abs(B.X), abs(B.Y)), max(abs(C.X), abs(C.Y)))) / 1e9;
	if (val <= -eps)
		return -1;
	if (val >= eps)
		return 1;
	return 0;
}
 
void to_upper(string &x){
	REP(i, sz(x))
		x[i] = toupper(x[i]);
}
 
void to_lower(string &x){
	REP(i, sz(x))
		x[i] = tolower(x[i]);
}
 
string its(ll x){
	if (x == 0)
		return "0";
	string ret = "";
	while (x > 0){
		ret += (x % 10) + '0';
		x /= 10;
	}
	reverse(all(ret));
	return ret;
}
 
ll sti(string s){
	ll ret = 0;
	REP(i, sz(s)){
		ret *= 10;
		ret += (s[i] - '0');
	}
	return ret;
}
 
const int N = 5e4 + 10;
const int P = 31;
 
int n, up[N], down[N], pot[N], sz[N], centroid, anc[N], cookie = 1;
char s[N];
vi e[N];
int is_centroid[N];
map <pii, int> cnt;
 
void precompute(){
	pot[0] = 1;
	FOR(i, 1, n + 1)
		pot[i] = mul(pot[i - 1], P);
}
 
void dfs(int node, int dad){
	sz[node] = 1;
	FORA(nxt, e[node]){
		if (nxt == dad || is_centroid[nxt] == cookie)
			continue;
		dfs(nxt, node);
		sz[node] += sz[nxt];
	}
}
 
void find_centroid(int node, int dad, int component_size){
	int maxi = component_size - sz[node];
	FORA(nxt, e[node]){
		if (nxt == dad || is_centroid[nxt] == cookie)
			continue;
		maxi = max(maxi, sz[nxt]);
		find_centroid(nxt, node, component_size);
	}
	if (maxi <= component_size / 2)
		centroid = node;
}
 
void calc_hash(int node, int dad, int h_down, int h_up, int dep){
	down[node] = sum(mul(h_down, P), s[node] - 'a' + 1);
	up[node] = sum(h_up, mul(pot[dep], s[node] - 'a' + 1));
 
	FORA(nxt, e[node])
		if (!(is_centroid[nxt] == cookie) && nxt != dad)
			calc_hash(nxt, node, down[node], up[node], dep + 1);
}
 
void add_hash(int node, int dad, int dep, int l){
	if (dep >= l)
		return;
	cnt[{dep, down[node]}]++;
	//cout << "ADD: " << dep _ down[node] << '\n';
	FORA(nxt, e[node])
		if (nxt != dad && !(is_centroid[nxt] == cookie))
			add_hash(nxt, node, dep + 1, l);
}
 
void remove_hash(int node, int dad, int dep, int l){
	if (dep >= l)
		return;
	cnt[{dep, down[node]}]--;
	//cout << "REMOVE: " << dep _ down[node] << '\n';
	FORA(nxt, e[node])
		if (nxt != dad && !(is_centroid[nxt] == cookie))
			remove_hash(nxt, node, dep + 1, l);
}
 
bool solve(int node, int dad, int dep, int lenght){
	anc[dep] = node;

	if (dep >= lenght)
		return 0;

	if (dep == lenght - 1){
		if (up[node] == down[node])
			return 1;
	} else {
		int dep_b = (lenght - (dep + 1));
		if (dep_b <= dep && dep_b >= 0){
			if (dep == dep_b){
				//cout << "Q1" _ node + 1 _ dep_b << '\n';
				if (cnt[{dep_b, down[node]}])
					return 1;
			} else {
				int c = anc[dep - (dep_b + 1)];
				//cout << "Q2" _ node + 1 _ c + 1 _ dep_b << '\n';
				if (down[anc[dep - (dep_b + 1) + 1]] == up[anc[dep - (dep_b + 1) + 1]]){
					int h = sub(down[node], mul(pot[dep_b + 1], down[c]));
					if (cnt[{dep_b, h}])
						return 1;
				}
			}
		}
	}
 
	bool ret = 0;
	FORA(nxt, e[node])
		if (nxt != dad && !(is_centroid[nxt] == cookie))
			ret |= solve(nxt, node, dep + 1, lenght);
	return ret;
}	
 
void optimize(){
	REP(i, n)
		is_centroid[i] = 0;
}

bool decompose(int node, int lenght){
	if (lenght == 1)
		return 1;
	dfs(node, -1);
	if (sz[node] < lenght)
		return 0;
 
	//cout << "-----------\n";
 
	find_centroid(node, -1, sz[node]);
	assert(centroid != -1);
	calc_hash(centroid, -1, 0, 0, 0);
	is_centroid[centroid] = cookie;	
 
	add_hash(centroid, -1, 0, lenght);
	bool ret = 0;
	FORA(nxt, e[centroid]){
		if (is_centroid[nxt] == cookie)
			continue;
		anc[0] = centroid;
		remove_hash(nxt, centroid, 1, lenght);
		//cout << nxt + 1 << '\n';
		ret |= solve(nxt, centroid, 1, lenght);
		add_hash(nxt, centroid, 1, lenght);
	}
	cnt.clear();
 
	FORA(nxt, e[centroid]){
		if (is_centroid[nxt] == cookie)
			continue;
		ret |= decompose(nxt, lenght);
	}
 
	return ret;
}
 
int parni(){
	int lo = 0, hi = (n + 1) / 2;
	while (lo < hi){
		int mid = (lo + hi + 1) / 2;
		//memset(is_centroid, 0, sizeof is_centroid);
		//optimize();
		if (decompose(1, 2 * mid))
			lo = mid;
		else
			hi = mid - 1;
		cookie++;
	}
	return 2 * lo;
}
 
int neparni(){
	int lo = 0, hi = (n + 1) / 2;
	while (lo < hi){
		int mid = (lo + hi + 1) / 2;
		//memset(is_centroid, 0, sizeof is_centroid);
		//optimize();
		if (decompose(1, 2 * mid + 1))
			lo = mid;
		else
			hi = mid - 1;
		cookie++;
	}
	return 2 * lo + 1;
}
 
int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	scanf("%d%s", &n, s);
	REP(i, n - 1){
		int x, y; scanf("%d%d", &x, &y);
		x--, y--;
		e[x].PB(y);
		e[y].PB(x);
	}
 
	precompute();
	cookie = 1;
 
	printf("%d\n", max(parni(), neparni()));
 
	return 0;
}

Compilation message

lampice.cpp:13:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
lampice.cpp:14:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
lampice.cpp: In function 'int fast_pot(ll, int)':
lampice.cpp:92:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if (n & 1)
   ^~
lampice.cpp:94:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    pot = (pot * pot) % MOD;
    ^~~
lampice.cpp: In function 'int main()':
lampice.cpp:330:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%s", &n, s);
  ~~~~~^~~~~~~~~~~~~~~
lampice.cpp:332:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 1528 KB Output is correct
2 Correct 19 ms 1656 KB Output is correct
3 Correct 52 ms 1784 KB Output is correct
4 Correct 63 ms 1656 KB Output is correct
5 Correct 6 ms 1528 KB Output is correct
6 Correct 5 ms 1528 KB Output is correct
7 Correct 5 ms 1528 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1103 ms 9060 KB Output is correct
2 Correct 947 ms 9080 KB Output is correct
3 Correct 908 ms 9220 KB Output is correct
4 Correct 1018 ms 9592 KB Output is correct
5 Correct 1115 ms 10104 KB Output is correct
6 Correct 673 ms 8444 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3084 ms 8232 KB Output is correct
2 Correct 3344 ms 7972 KB Output is correct
3 Correct 3305 ms 7960 KB Output is correct
4 Correct 2138 ms 7160 KB Output is correct
5 Correct 2434 ms 7292 KB Output is correct
6 Correct 2204 ms 6904 KB Output is correct

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 1528 KB Output is correct
2 Correct 19 ms 1656 KB Output is correct
3 Correct 52 ms 1784 KB Output is correct
4 Correct 63 ms 1656 KB Output is correct
5 Correct 6 ms 1528 KB Output is correct
6 Correct 5 ms 1528 KB Output is correct
7 Correct 5 ms 1528 KB Output is correct
8 Correct 1103 ms 9060 KB Output is correct
9 Correct 947 ms 9080 KB Output is correct
10 Correct 908 ms 9220 KB Output is correct
11 Correct 1018 ms 9592 KB Output is correct
12 Correct 1115 ms 10104 KB Output is correct
13 Correct 673 ms 8444 KB Output is correct
14 Correct 3084 ms 8232 KB Output is correct
15 Correct 3344 ms 7972 KB Output is correct
16 Correct 3305 ms 7960 KB Output is correct
17 Correct 2138 ms 7160 KB Output is correct
18 Correct 2434 ms 7292 KB Output is correct
19 Correct 2204 ms 6904 KB Output is correct
20 Correct 3119 ms 5476 KB Output is correct
21 Correct 3708 ms 6412 KB Output is correct
22 Execution timed out 5082 ms 6648 KB Time limit exceeded
23 Halted 0 ms 0 KB -