Submission #223435

#	Time	Username	Problem	Language	Result	Execution time	Memory
223435		errorgorn	Matching (COCI20_matching)	C++14	0 / 110	27 ms	39808 KiB

matching

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define endl '\n'

const int INF=1000000000;

int lastused[300005][26];
int edges[300005][26];
int backedge[300005];
int len[300005];

int n;
string s;

vector<int> al[50005];
int parent[50005][15];
int level[50005]; //depth idk why i used to call it level

int in[50005];
int out[50005];

int DFS_TIME=0;

void dfs(int i,int p){
	in[i]=++DFS_TIME;
    int curr;
    for (auto it=al[i].begin();it!=al[i].end();it++){
        if (*it==p) continue;
        level[*it]=level[i]+1;
        parent[*it][0]=i;
        curr=i;
        for (int x=0;parent[curr][x]!=-1;x++){
            curr=parent[*it][x+1]=parent[curr][x];
        }
        dfs(*it,i);
    }
    out[i]=DFS_TIME;
}

int mov(int i,int j){
    for (int x=0;x<22;x++){
        if (j&1){
            i=parent[i][x];
        }
        j>>=1;
    }
    return i;
}

int lca(int i,int j){
    if (level[i]<level[j]) swap(i,j);
    i=mov(i,level[i]-level[j]);
    if (i==j) return i;
    for (int x=21;x>=0;x--){
        if (parent[i][x]!=parent[j][x]){
            i=parent[i][x];
            j=parent[j][x];
        }
    }
    return parent[i][0];
}

int dist(int i,int j){
    return level[i]+level[j]-2*level[lca(i,j)];
}


int memo[3005][3005];

int dp(int i,int j){
	if (memo[i][j]!=-1) return memo[i][j];
	
	if (s[i]!=s[j]) return -INF;
	
	if (level[i]>level[j]) swap(i,j); //i could be ancestor of j
	if (i==j) return memo[i][j]=1;
	else if (parent[j][0]==i) return memo[i][j]=2;
	else{
		if (in[i]<=in[j] && out[j]<=out[i]){
			return dp(mov(j,level[j]-level[i]-1),parent[j][0])+2;
		}
		else{
			return dp(parent[i][0],parent[j][0])+2;
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
    cin.tie(0);
	
	cin>>n>>s;
	
	bool ST2=true;
	
	int a,b;
	for (int x=1;x<n;x++){
		cin>>a>>b;
		a--,b--;
		al[a].push_back(b);
		al[b].push_back(a);
		
		if (a+1!=b) ST2=false;
	}
	
	memset(parent,-1,sizeof(parent));
	dfs(0,-1);
	
	if (n<=3000){
		int ans=0;
		
		memset(memo,-1,sizeof(memo));
		for (int x=0;x<n;x++)
			for (int y=0;y<n;y++)
				ans=max(ans,dp(x,y));
				
		cout<<ans<<endl;
	}
	else if (ST2){
		int ans=0;
		
		memset(edges,-1,sizeof(edges));
		backedge[0]=0,backedge[1]=0;
		len[0]=-1,len[1]=0;
		int PREV=0;
		int INDEX=1;

		for (int x=0;x<s.size();x++){
			while (s[x-len[PREV]-1]!=s[x]) 
				PREV=backedge[PREV];
			
			if (edges[PREV][s[x]-'a']==-1) 
				edges[PREV][s[x]-'a']=++INDEX;
			int curr=edges[PREV][s[x]-'a'];
			len[curr]=len[PREV]+2;
			
			ans=max(ans,len[curr]);
			
			if (len[curr]==1){
				backedge[curr]=1;
			}
			else{
				int b=backedge[PREV];
				while (s[x-len[b]-1]!=s[x]) b=backedge[b];
				backedge[curr]=edges[b][s[x]-'a'];
			}
			
			PREV=curr;
		}
		
		cout<<ans<<endl;
	}
	else{
		int ans=0;
		int counter=1;
		for (int x=0;x<n;x++){
			if (x && al[x].size()!=1) continue;
			for (int y=x+1;y<n;y++){
				if (al[y].size()!=1) continue;
				
				string a="";
				string b="";
				
				int i=x,j=y;
				
				while (level[i]>level[j]){
					a+=s[i];
					i=parent[i][0];
				}
				while (level[j]>level[i]){
					b+=s[j];
					j=parent[j][0];
				}
				while (i!=j){
					a+=s[i];
					i=parent[i][0];
					b+=s[j];
					j=parent[j][0];
				}
				
				reverse(b.begin(),b.end());
				
				string t=a+s[i]+b;
				
				//cout<<t<<endl;
				
				backedge[0]=0,backedge[1]=0;
				len[0]=-1,len[1]=0;
				int PREV=0;
				int INDEX=1;

				for (int x=0;x<t.size();x++){
					while (t[x-len[PREV]-1]!=t[x]) 
						PREV=backedge[PREV];
					
					if (lastused[PREV][t[x]-'a']!=counter) 
						edges[PREV][t[x]-'a']=++INDEX,lastused[PREV][t[x]-'a']=counter;
					int curr=edges[PREV][t[x]-'a'];
					len[curr]=len[PREV]+2;
					
					ans=max(ans,len[curr]);
					
					if (len[curr]==1){
						backedge[curr]=1;
					}
					else{
						int b=backedge[PREV];
						while (t[x-len[b]-1]!=t[x]) b=backedge[b];
						backedge[curr]=edges[b][t[x]-'a'];
					}
					
					PREV=curr;
				}
				counter++;
			}
		}
		
		cout<<ans;
	}
}

Compilation message (stderr)

matching.cpp: In function 'int main()':
matching.cpp:131:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int x=0;x<s.size();x++){
                ~^~~~~~~~~
matching.cpp:195:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int x=0;x<t.size();x++){
                  ~^~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 40
• Subtask 5: 0 / 52