oj.uz

Submission #233162

# Submission time Handle Problem Language Result Execution time Memory
233162 2020-05-19T18:00:28 Z errorgorn Lampice (COCI19_lampice) C++14
17 / 110
 5000 ms 9340 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

struct custom_hash {
    typedef unsigned long long ull;
    const ull FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    static ull splitmix64(ull x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(ll x) const {
        return splitmix64(x + FIXED_RANDOM);
    }
    size_t operator()(const pair<int,int> &i)const{
        return splitmix64((((ll)i.first)^(((ll)i.second)<<32))+FIXED_RANDOM);
    }
};


struct RNG{
    typedef unsigned long long ull;
    ///taken from http://prng.di.unimi.it/xoshiro256plusplus.c
    ull s[4];

    RNG(ull a, ull b, ull c, ull d){
        ///please seed this with something legit
        s[0]=a,s[1]=b,s[2]=c,s[3]=d;

        for (int x=0;x<1024;x++) next(); //give some random
    }

    static inline ull rotl(const ull x, int k){
        return (x << k) | (x >> (64 - k));
    }


    ull next() {
        const ull result = rotl(s[0] + s[3], 23) + s[0];

        const ull t = s[1] << 17;

        s[2] ^= s[0];
        s[3] ^= s[1];
        s[1] ^= s[2];
        s[0] ^= s[3];

        s[2] ^= t;

        s[3] = rotl(s[3], 45);

        return result;
    }
}rng=RNG(423358081,274988025,50131061,866741066);

const int MOD=1000000007;
const ll P=583726327;

long long qexp(long long b,long long p,int m){
    long long res=1;
    while (p){
        if (p&1) res=(res*b)%m;
        b=(b*b)%m;
        p>>=1;
    }
    return res;
}

ll fix(ll i){
	while (i<0) i+=MOD;
	while (MOD<=i) i-=MOD;
	
	return i;
}

ll h[30];
ll powP[50005];
ll invP[50005];

int n;
string s;
vector<int> al[50005];
bool used[50005];
int parent[50005];
int subtree[50005];

void dfs(int i,int j){
    subtree[i]=1;
    for (auto it=al[i].begin();it!=al[i].end();it++){
        if (!used[*it] && *it!=j){
            dfs(*it,i);
            subtree[i]+=subtree[*it];
        }
    }
}
void centroid_decomp(int i,int p,int s){
    s>>=1;
    dfs(i,-1);
    int prev=-1;
    reloop:
    for (auto it=al[i].begin();it!=al[i].end();it++){
        if (!used[*it] && *it!=prev && subtree[*it]>s){
            prev=i;
            i=*it;
            goto reloop;
        }
    }
    ///i is now the centroid
    used[i]=true;
    parent[i]=p;
    int prev_size=s-1;
    for (auto it=al[i].begin();it!=al[i].end();it++){
        if (!used[*it]){
            if (*it!=prev){
                centroid_decomp(*it,i,subtree[*it]);
                s-=subtree[*it];
            }
        }
    }
    if (prev!=-1) centroid_decomp(prev,i,prev_size);
}

bool BANNED[50005]; //parents of node x, dont go here in dfs
int LENGTH; //length of palindrome we need to find
int ROOT;


int depth[50005];
unordered_map<ii,int,custom_hash> exists;
int val[500005];
int rval[500005];

vector<int> stk;

void dfs_mark(int i,int p,int id){ //this is to mark vertices during dfs
	if (BANNED[i]) return;
	
	//val and rval get calculated first
	depth[i]=depth[p]+1;
	val[i]=(val[p]+powP[depth[i]]*h[s[i]-'a'])%MOD;
	rval[i]=(rval[p]*P+h[s[i]-'a'])%MOD;
	
	//cout<<i<<" "<<val[i]<<" "<<rval[i]<<endl;
	ii temp=ii((fix(val[i]-h[s[ROOT]-'a'])*invP[1])%MOD,depth[i]);
	
	//cout<<p<<" "<<i<<endl;
	//cout<<"adding: "<<temp.fi<<" "<<temp.se<<" "<<id<<endl;
	
	if (exists.count(temp) && exists[temp]!=id) exists[temp]=-1;
	else exists[temp]=id;
	
	for (auto &it:al[i]){
		if (it==p) continue;
		
		dfs_mark(it,i,id);	
	}
	
}

bool dfs_test(int i,int p,int id){ //test if palindrome exists
	if (BANNED[i]) return false;
	stk.push_back(i);
	
	if (LENGTH/2<=depth[i] && depth[i]<LENGTH){
		int extra=LENGTH-depth[i]-1;
		int palin=LENGTH-extra*2;
		
		//cout<<i<<" "<<extra<<" "<<palin<<endl;
		//cout<<stk[palin-1]<<endl;
		
		if (val[stk[palin-1]]==rval[stk[palin-1]]){
			ii temp=ii((fix(val[i]-val[stk[palin-1]])*invP[palin])%MOD,extra);
			//cout<<temp.fi<<" "<<temp.se<<" "<<id<<endl;
			if (exists.count(temp) && exists[temp]!=id) return true;
		}
	}
	
	for (auto &it:al[i]){
		if (it==p) continue;
		
		if (dfs_test(it,i,id)) return true;
	}
	
	stk.pop_back();
	return false;	
}

bool can(int i){
	if (i<2) return true;
	
	LENGTH=i;
	
	rep(x,1,n+1){
		exists.clear();
		exists[ii(0,0)]=-1;
		//cout<<"trying: "<<x<<endl;
		
		depth[x]=0;
		val[x]=rval[x]=h[s[x]-'a'];
		
		ROOT=x;
		int temp=parent[x];
		while (temp!=-1){
			BANNED[temp]=true;
			temp=parent[temp];
		}

		for (auto &it:al[x]){
			dfs_mark(it,x,it);
		}
		
		for (auto &it:al[x]){
			stk.clear();
			stk.push_back(x);
			if (dfs_test(it,x,it)) return true;
		}
		
		temp=parent[x];
		while (temp!=-1){
			BANNED[temp]=false;
			temp=parent[temp];
		}
	}
	
	return false;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	rep(x,0,30) h[x]=rng.next()%MOD;
	rep(x,0,50005){
		powP[x]=qexp(P,x,MOD);
		invP[x]=qexp(powP[x],MOD-2,MOD);
	}
	
	cin>>n;
	cin>>s;
	s="$"+s;
	
	int a,b;
	rep(x,1,n){
		cin>>a>>b;
		al[a].push_back(b);
		al[b].push_back(a);
	}
	
	centroid_decomp(1,-1,n);
	
	int ans=0;
	
	int lo,hi,mi;
	
	lo=0,hi=25005;
	while (hi-lo>1){
		mi=hi+lo>>1;
		
		if (can(mi*2+1)) lo=mi;
		else hi=mi;
	}
	
	ans=max(ans,lo*2+1);
	
	lo=0,hi=25005;
	while (hi-lo>1){
		mi=hi+lo>>1;
		
		if (can(mi*2)) lo=mi;
		else hi=mi;
	}
	
	ans=max(ans,lo*2);
	
	cout<<ans<<endl;
}

Compilation message

lampice.cpp: In function 'int main()':
lampice.cpp:286:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mi=hi+lo>>1;
      ~~^~~
lampice.cpp:296:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mi=hi+lo>>1;
      ~~^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2304 KB Output is correct
2 Correct 37 ms 2432 KB Output is correct
3 Correct 78 ms 2432 KB Output is correct
4 Correct 99 ms 2508 KB Output is correct
5 Correct 17 ms 2304 KB Output is correct
6 Correct 17 ms 2304 KB Output is correct
7 Correct 18 ms 2304 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5067 ms 9340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5078 ms 8616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2304 KB Output is correct
2 Correct 37 ms 2432 KB Output is correct
3 Correct 78 ms 2432 KB Output is correct
4 Correct 99 ms 2508 KB Output is correct
5 Correct 17 ms 2304 KB Output is correct
6 Correct 17 ms 2304 KB Output is correct
7 Correct 18 ms 2304 KB Output is correct
8 Execution timed out 5067 ms 9340 KB Time limit exceeded
9 Halted 0 ms 0 KB -