oj.uz

Submission #233164

# Submission time Handle Problem Language Result Execution time Memory
233164 2020-05-19T18:22:48 Z errorgorn Lampice (COCI19_lampice) C++14
110 / 110
 1542 ms 55464 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[50005];
int val[50005];
int rval[50005];

vector<int> stk;

void dfs_mark(int i,int p,int id){ //this is to mark vertices during dfs
	if (BANNED[i]) return;
	
	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[ROOT].count(temp) && exists[ROOT][temp]!=id) exists[ROOT][temp]=-1;
	else exists[ROOT][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);
	
	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;
	
	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[ROOT].count(temp) && exists[ROOT][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){
		//cout<<"trying: "<<x<<endl;
		ROOT=x;
		
		depth[x]=0;
		val[x]=rval[x]=h[s[x]-'a'];
		
		int temp=parent[x];
		while (temp!=-1){
			BANNED[temp]=true;
			temp=parent[temp];
		}
		
		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);
	
	rep(x,1,n+1){
		ROOT=x;
		
		depth[x]=0;
		val[x]=rval[x]=h[s[x]-'a'];
	
		exists[x][ii(0,0)]=-1;
		
		int temp=parent[x];
		while (temp!=-1){
			BANNED[temp]=true;
			temp=parent[temp];
		}
		
		for (auto &it:al[x]){
			dfs_mark(it,x,it);
		}
		
		temp=parent[x];
		while (temp!=-1){
			BANNED[temp]=false;
			temp=parent[temp];
		}
		
		//cout<<sz(exists[x])<<endl;
	}
	
	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:310:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mi=hi+lo>>1;
      ~~^~~
lampice.cpp:320: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 31 ms 5504 KB Output is correct
2 Correct 35 ms 5624 KB Output is correct
3 Correct 43 ms 6136 KB Output is correct
4 Correct 50 ms 6136 KB Output is correct
5 Correct 30 ms 5496 KB Output is correct
6 Correct 30 ms 5496 KB Output is correct
7 Correct 30 ms 5504 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 47272 KB Output is correct
2 Correct 534 ms 49076 KB Output is correct
3 Correct 522 ms 49960 KB Output is correct
4 Correct 571 ms 52392 KB Output is correct
5 Correct 584 ms 55464 KB Output is correct
6 Correct 458 ms 36088 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1482 ms 48424 KB Output is correct
2 Correct 1124 ms 47012 KB Output is correct
3 Correct 1542 ms 47016 KB Output is correct
4 Correct 1501 ms 32888 KB Output is correct
5 Correct 1200 ms 43176 KB Output is correct
6 Correct 866 ms 38824 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5504 KB Output is correct
2 Correct 35 ms 5624 KB Output is correct
3 Correct 43 ms 6136 KB Output is correct
4 Correct 50 ms 6136 KB Output is correct
5 Correct 30 ms 5496 KB Output is correct
6 Correct 30 ms 5496 KB Output is correct
7 Correct 30 ms 5504 KB Output is correct
8 Correct 577 ms 47272 KB Output is correct
9 Correct 534 ms 49076 KB Output is correct
10 Correct 522 ms 49960 KB Output is correct
11 Correct 571 ms 52392 KB Output is correct
12 Correct 584 ms 55464 KB Output is correct
13 Correct 458 ms 36088 KB Output is correct
14 Correct 1482 ms 48424 KB Output is correct
15 Correct 1124 ms 47012 KB Output is correct
16 Correct 1542 ms 47016 KB Output is correct
17 Correct 1501 ms 32888 KB Output is correct
18 Correct 1200 ms 43176 KB Output is correct
19 Correct 866 ms 38824 KB Output is correct
20 Correct 666 ms 23136 KB Output is correct
21 Correct 731 ms 28712 KB Output is correct
22 Correct 1068 ms 39468 KB Output is correct
23 Correct 332 ms 12920 KB Output is correct
24 Correct 1090 ms 29496 KB Output is correct
25 Correct 1189 ms 26452 KB Output is correct
26 Correct 1263 ms 41004 KB Output is correct
27 Correct 1226 ms 40872 KB Output is correct
28 Correct 1167 ms 17272 KB Output is correct
29 Correct 980 ms 17528 KB Output is correct
30 Correct 923 ms 23928 KB Output is correct
31 Correct 983 ms 19960 KB Output is correct
32 Correct 1067 ms 35112 KB Output is correct
33 Correct 603 ms 30120 KB Output is correct